HaskellでDecimalをBinaryに変換する

Question

このコードスニペットはうまくいきましたが、それはなぜわかりません。これは、Intをバイナリ表現に変換します。

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

私は何をすべきかdivとmod知っています。しかし、modから来る各番号はどのように配置されますか？

Answer 1

要するに、累積結果に各繰り返しで10を乗算します。

何が起こっているのかをより明確に理解するために、関数を2つの簡単な関数に分けることができます。最初のものは、整数をバイナリ数字のリストに変換します。もう一方はあなたを悩ますことを正確に行います：バイナリ数字のリストを整数に連結します。

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の削減：repBinario 1の

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

代替定義：

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

をdivとの削減：repBinario 0の

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

代替定義：

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

削減：各ステップ

101 

を(`mod` 2)が最下位のバイナリ桁を取得し、(`div` 2)が右数をシフト、数字を破棄して残りの数字を再帰的に渡すt o divBinario。最後に、逆の処理を行います。(+ d)は現在の桁を結果に加算し、(* 10)は数字を左ににシフトし、桁数を増やすことができます。

あなたが得るのは、がの元の入力と同じに見える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 

私はちょうどその定義によって機能を評価し、整数加算/乗算は、分布の法則に従うという事実を使用していました。