二進数表記に変換してみる

30分プログラム、その568。整数を'+'と' 'の二進数表記に変換してみる。
素数の二進法表記 - 西尾泰和のはてなダイアリーに

                                    +
                                    + +
                                  +   +
                                  + + +

というよく分からない記号が書いてあった。
最初はさっぱり意味が分からなかったけど、よくよく考えていみると、立っているビットを'+'で表現していることに気がついた。
というわけで、これをやってみよう。無駄にShowクラスを使ってしまった。

使い方

*Main> fixWidth 8 $ toBinary 3
      ++
*Main> mapM_ (putStrLn.show) $ map (fixWidth 8 . toBinary) [1..8]
       +
      +
      ++
     +
     + +
     ++
     +++
    +

ソースコード

import Data.Bits
newtype Binary = Binary [Bool]

toBinary :: Int -> Binary
toBinary n = Binary $ iter [] n
    where
      iter xs 0 = False:xs
      iter xs 1 = True:xs
      iter xs n = iter (testBit n 0 : xs) $ n `shiftR` 1

fixWidth :: Int -> Binary -> Binary
fixWidth n (Binary xs) = Binary $ replicate (n - length xs) False ++ xs

instance Show Binary where
    show (Binary xs) = map (\b -> if b then '+' else ' ') xs

参考

• 過去の30分プログラム