Converting Decimal to Binary in Haskell

Question

I found out this snippet of code which works, but I do not understand why it does. It converts an Int to its representation in binary.

repBinario::Int -> Int
repBinario 0 = 0
repBinario x = 10 * repBinario (x `div` 2) + x `mod` 2

I know what div and mod do. However, how does it place each number that comes from mod together?

Answer 1

In short, it multiplies the accumulated result by 10 on each iteration.

To get a clearer understanding of what's going on we can divide your function into two simpler ones. The first one will convert an integer into a list of binary digits. The other will then do exactly the thing that bothers you: concat a list of binary digits into an integer.

extractBinDigits :: Int -> [Int]
extractBinDigits =
  unfoldr (\x -> if x == 0 then Nothing else Just (mod x 2, div x 2))

concatDigits :: [Int] -> Int
concatDigits =
  foldr (\a b -> a + b * 10) 0

As you see we simply fold the list multiplying the accumulator by 10 on each step and adding each digit to it.

Then your original function becomes just this:

repBinario :: Int -> Int
repBinario =
  concatDigits . extractBinDigits

Division now lets us inspect and reuse the finer pieces of our program providing us with greater flexibility. E.g., by adding another simple function you can now convert the integer into a string in one go:

showDigits :: [Int] -> String
showDigits =
  reverse . map (chr . (+ 48))

repStringyBinario :: Int -> String
repStringyBinario =
  showDigits . extractBinDigits

Answer 2

Let’s go through an example, then:

repBinario 5

Substitute definition of repBinario 5:

10 * repBinario (5 `div` 2) + 5 `mod` 2

Reduce div and mod:

10 * repBinario 2 + 1
                    ^

Here we have produced our first digit, marked with ^.

Substitute definition of repBinario 2:

10 * (10 * repBinario (2 `div` 2) + 2 `mod` 2) + 1
                                                 ^

Reduce div and mod:

10 * (10 * repBinario 1 + 0) + 1
                          ^    ^

Substitute definition of repBinario 1:

10 * (10 * (10 * repBinario (1 `div` 2) + 1 `mod` 2) + 0) + 1
                                                       ^    ^

Reduce div and mod:

10 * (10 * (10 * repBinario 0 + 1) + 0) + 1
                                ^    ^    ^

Substitute definition of repBinario 0:

10 * (10 * (10 * 0 + 1) + 0) + 1
                     ^    ^    ^

Reduce:

101

At each step, (`mod` 2) gets the least significant binary digit, and (`div` 2) shifts the number rightward, discarding the digit and passing the rest of the number recursively to divBinario. At the end, we do the opposite process: (+ d) adds the current digit to the result, and (* 10) shifts the number leftward so we can add more digits.

What you get is a decimal number that looks identical to the binary representation of the original input.

If you remove the multiplication by 10, you get popCount, a function that gives you the population count of a number—the number of 1 bits in its binary representation:

popCount 0 = 0
popCount x = popCount (x `div` 2) + x `mod` 2

popCount 5  ==  2