Преобразование десятичного разряда в двоичный файл в Haskell

Question

Я обнаружил этот фрагмент кода, который работает, но я не понимаю, почему он это делает. Он преобразует Int в его представление в двоичном формате.

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

Я знаю, что div и mod делать. Однако, как он помещает каждый номер, который приходит от mod вместе?

Answer 1

Короче говоря, он умножает накопленный результат на 10 на каждой итерации.

Чтобы получить более четкое представление о том, что происходит, мы можем разделить вашу функцию на две более простые. Первый преобразует целое число в список двоичных цифр. Другой будет делать именно то, что вас беспокоит: concat список двоичных цифр в целое число.

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 

Как вы видите, мы просто сложите список умножения аккумулятора на 10 на каждый шаг и добавляя каждую цифру к нему.

Тогда ваша оригинальная функция становится только это:

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

Отдел теперь позволяет нам проверять и повторно использовать тонкие кусочки нашей программы, обеспечивающие нам большую гибкость. Например, путем добавления еще одной простой функции теперь вы можете преобразовать число в строку на одном дыхании:

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

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

Answer 2

Давайте рассмотрим пример, то:

repBinario 5 

определение Заменитель repBinario 5:

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

Уменьшить div и mod:

10 * repBinario 2 + 1 
        ^

Здесь мы выпустили нашу первую цифру, обозначенную ^.

Заменитель определение repBinario 2:

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

Уменьшить div и mod:

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

Заменитель определение repBinario 1:

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

Уменьшить div и mod:

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

Заменитель определение repBinario 0:

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

Сокращение:

101 

На каждом шаге (`mod` 2) получает значащий двоичный разряд, и (`div` 2) сдвигает число вправо , отбрасывая цифру и передавая остальную часть числа рекурсивно t o divBinario. В конце мы делаем противоположный процесс: (+ d) добавляет текущую цифру в результат, а (* 10) сдвигает число влево, поэтому мы можем добавить больше цифр.

Что вы получаете, это десятичное число, которое выглядит, идентичное двоичному представлению исходного ввода.

Если удалить умножение на 10, вы получаете popCount, функцию, которая дает Вам количество населения из ряда-число 1 битов в его двоичном представлении:

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

popCount 5 == 2 

Answer 3

Я думаю, что это было бы лучше всего вычислить эту функцию для небольшого значения вручную - это возможно, так как это чистая функция, поэтому вы можете заменить левую сторону своим определением (то есть правой стороной) - фантастическое информационное слово для этой функции - референциальная прозрачность ».

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 

в тех шагах, которые я только оценку функции по определению и использовал тот факт, что число-сложение/умножение подчиняется закону распределения.