7

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?

3
  • 2
    I don't understand the question. Commented Oct 20, 2016 at 22:52
  • @melpomene I wanted to know what happend each time repBinario was being called, this recursion was a little bit confusing for a newbie like me. The answers below we're really useful though. Commented Oct 21, 2016 at 10:39
  • The answers we're very helpful, I did not choose just one because some people might not be looking for the same thing that I was, anyway, I decided to upvote each reply since all of them structured the problem in a different way and so the question resulted in diversed solutions, all equally interesting. Thank you. Commented Oct 21, 2016 at 10:46

3 Answers 3

6

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
Sign up to request clarification or add additional context in comments.

Comments

5

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

Comments

5

I think it would be best to calculate this function for a small value by hand - this is possible since this is a pure function therefore you can replace left hand side with its definition (i.e. right hand side) - the fancy computer science word for this feature is "referential 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

in those steps I just evaluated the function by its definition and used the fact that integer-addition/multiplication obey the law of distribution.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.