conversion from decimal to binary in SML

Question

I have the following formula

fun foo 0 = [0] 
  | foo num = let val l =  (num mod 2)::foo(num div 2) in
           rev l
           end;

which is supposed to convert from decimal to binary.It has the following signature

val foo = fn : int -> int list

I am not sure where exactly I am getting things wrong as I am getting incorrect results.May someone help me figure out where I am making the error?

Answer 1

The problem seems to be that you reverse the resulting list in every recursive step, instead of just once at the end.

Also, you probably need to map 0 to the empty list, otherwise you'll have one 0 too many in the end.

Answer 2

Exactly what Andreas said. Now, the obvious way to get around this is to use a wrapper function:

fun f n =
let
  fun f' 0   = []
    | f' num = num mod 2 :: f' (num div 2)
in
  rev (f' n)
end

This works, but has the disadvantage of first building up the list, and then traversing it (the rev call). It also isn't tail-recursive. We can do better!

Instead of using reverse, we flip things around and use an accumulator:

fun g n =
let
  fun g' 0   acc = acc
    | g' num acc = g' (num div 2) (num mod 2 :: acc)
in
  g' n []
end

To understand the difference, let's see what happens if we run each of these on the number 4.

f 4 -> rev (f' 4)
    -> rev (4 mod 2 :: f' (4 div 2))
    -> rev (0 :: f' 2)
    -> rev (0 :: 2 mod 2 :: f' (2 div 2))
    -> rev (0 :: 0 :: f' 1)
    -> rev (0 :: 0 :: 1 mod 2 :: f' (1 div 2))
    -> rev (0 :: 0 :: 1 :: f' 0)
    -> rev (0 :: 0 :: 1 :: [])
    -> [1, 0, 0]

g 4 -> g' 4 []
    -> g' (4 div 2) (4 mod 2 :: [])
    -> g' 2 (0 :: [])
    -> g' (2 div 2) (2 mod 2 :: 0 :: [])
    -> g' 1 (0 :: 0 :: [])
    -> g' (1 div 2) (1 mod 2 :: 0 :: 0 :: [])
    -> g' 0 (1 :: 0 :: 0 :: [])
    -> [1, 0, 0]