Convert decimal to binary in Haskell

Question

I found this piece of code that works, but I don’t understand why it does it. It converts Int to its binary representation.

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

I know what div and mod . However, how does it put every number that comes from mod together?

Answer 1

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

To get a clearer picture of what is going on, we can split your function into two simpler ones. The first converts the integer to a list of binary digits. Another will do exactly what bothers you: concat a list of binary digits to 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 (\ab -> a + b * 10) 0 

As you can see, we simply add up a list multiplying the battery by 10 at each step and adding each digit to it.

Then your original function will become just like this:

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

The department now allows us to test and reuse the finer parts of our program, giving us more flexibility. For example, adding another simple function, you can now convert an integer to a string at a time:

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

Answer 2

Let's look at an example, then:

 repBinario 5 

Replace the definition of repBinario 5 :

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

Reduce div and mod :

 10 * repBinario 2 + 1 ^ 

Here we produced the first digit, marked ^ .

Replace definition of repBinario 2 :

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

Reduce div and mod :

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

Replace the 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 ^ ^ ^ 

Replace definition of repBinario 0 :

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

Decrease:

 101 

At each step (`mod` 2) gets the least significant binary digit, and (`div` 2) shifts the number to the right, 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 to the left, 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 a count of the number - the number of bits 1 in its binary representation:

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

Answer 3

I think it would be best to calculate this function for a small value manually - this is possible, since it is a pure function, so you can replace the left side with its definition (that is, the right side) - a fantastic computer science. The word for this function is "reference transparency".

 repBinario 24 = 10 * repBinario (24 `div` 2) + 24 `mod` 2 = 10 * repBinario 12 + 0 = 10 * (10 * repBinario (12 `div` 2) + 12 `mod` 2) = 100 * repBinario 6 + 0 = 100 * (10 * repBinario (6 `div` 2) + 6 `mod` 2) = 1000 * repBinario 3 + 0 = 1000 * (10 * repBinario (3 `div` 2) + 3 `mod` 2) = 10000 * repBinario 1 + 1000 * 1 = 10000 (10 * repBinario (1 `div` 2) + 1 `mod` 2) + 1000 = 10000 (10 * repBinario 0 + 1) + 1000 = 10000 (10 * 0 + 1) + 1000 = 10000 * 1 + 1000 = 11000 

at these stages, I simply evaluated the function by its definition and used the fact that the integer complement / multiplication obeys the distribution law.