How to implement decimal to binary conversion

Question

I implemented a binary to decimal function in Haskell and am currently working on a function that would convert a decimal into a binary value. (I'm aware that these functionalities are available somewhere although they're not part of Prelude.hs)

I came up with the following code for a C-type procedural language, but I have trouble adapting it into the functional paradigm.

while (n > 0)
{
    if (n % 2 == 1)
        str = str + "1";
    else
        str = str + "0";
    n = n / 2;
}

I ventured into functional programming in Haskell only recently so I'm quite new to the functional way of thinking. I attempted the above using both recursion and list comprehension, but I'm not sure on how to place the guards and the logic properly since this involves multiple conditions. I use an Int list to hold the separate binary bits.

--Decimal to binary
toBin:: Int -> [Int]
toBin 0 = [0]
toBin n | (n % 2 == 1) =
        |(n % 2 == 0) = 

I've understood that the above pattern would let the program choose either guard and end evaluating the function. Am I on the wrong track here?

Below is what I came up with primitive recursion to convert any base (less than 10, in place of the 2) to decimal.

toDecimal :: [Int] -> Int
toDecimal [] = 0
toDecimal (x:xs) = (x * 2 ^(length xs)) + bin xs

Answer 1

There's no % operator; you're probably looking for `mod` instead:

toBin 0 = [0]
toBin n | n `mod` 2 == 1 = ...
        | n `mod` 2 == 0 = ...

Guards let you choose between multiple branches of a function. In this case, each ... will be the result of toBin n if its corresponding condition is true. To append two lists together, you can use the ++ operator, and `div` corresponds to integer division:

toBin 0 = [0]
toBin n | n `mod` 2 == 1 = toBin (n `div` 2) ++ [1]
        | n `mod` 2 == 0 = toBin (n `div` 2) ++ [0]

However, this has a few problems. For a start, it always starts the result with 0, which is redundant; additionally, using ++ [1] is slow, since it has to go through the entire list to add an element on to the end; it would be better to prepend each element as we go, and then reverse the result at the end.

To fix both these things, we'll split toBin up into a main function and a helper function:

toBin 0 = [0]
toBin n = reverse (helper n)

helper 0 = []
helper n | n `mod` 2 == 1 = 1 : helper (n `div` 2)
         | n `mod` 2 == 0 = 0 : helper (n `div` 2)

In this version, we use the : operator, which takes a value and a list, and returns the list with the value prepended to the beginning. We also return an empty result for 0 in our helper, and handle the 0 case in toBin instead, so that there's no more 0s than necessary in the result.

We can simplify helper's code by skipping the guards altogether, since we just write the result of n `mod` 2 again on the right-hand side:

helper 0 = []
helper n = (n `mod` 2) : helper (n `div` 2)

Finally, there's a function that does a div and a mod in one go, which can be more efficient:

helper 0 = []
helper n = let (q,r) = n `divMod` 2 in r : helper q

As an additional note, this doesn't really convert decimal to binary, it converts an integer to binary; Haskell implementations are unlikely to store integers in decimal format, although they are written and printed in that format. To write a full conversion of decimal to binary, a function that parses a decimal string into an integer would be required.

Answer 2

toBinary :: Int -> [ Int ]

toBinary 0 = [ 0 ]

toBinary n = toBinary ( n `quot` 2 ) ++ [ n `rem` 2 ]