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

Solution 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.

Solution 2

toBinary :: Int -> [ Int ]

toBinary 0 = [ 0 ]

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

Solution 3

Sooo i've been thinking about it lately and i came up with a great solution, the code is in Haskell and is simple yet very effective buut works only on positive numbers since i'm not yet advanced enough to calculate say 2's complement or other things klike that connected to the binary code.

binarz :: Int -> [Int]
binarz 0 = []
binarz n = binarz (div n 2) ++ [(mod n 2)] 

Solution 4

toBin :: Int -> [Int]
toBin 0 = [0]
toBin 1 = [1]
toBin n
    | n `mod` 2 == 0 = toBin (n `div` 2) ++ [0]
    | otherwise = toBin (n `div` 2) ++ [1]

0 and 1 are trivial cases. if n is even then you should append zero to the end, otherwise you append one. It's good practise to catch everything in your last guard expression (that's why I used otherwise which is the same as True)

View more solutions

Comments

[Daniel Fischer]

"a function that parses a decimal string into an integer would be required" - like, erm, read?

[ehird]

@DanielFischer: Yes, but presumably the OP is trying to implement this from scratch :) After all, showIntAtBase exists too.

[Matthew Piziak]

toBinary 1 returns [0, 1] rather than [1].

[Abhijit Sarkar]

While clever, this is the most difficult to read solution posted so far on this question.