2026-08-30
Reflect.hs
gray :: Int -> [String]
gray 0 = [""]
gray n = map (++ "0") g ++ map (++ "1") (reverse g)
where
g = gray (n - 1)
main :: IO ()
main = putStrLn (unwords (gray 3))
これは何を出力するでしょうか?
Answer
Output
000 100 110 010 011 111 101 001
(++ "0") は右側の引数を埋めた演算子の部分適用で、受け取った文字列 s を s ++ "0" にします。gray n は、1つ前の列 g の各文字列の末尾に 0 を足したものを先に並べ、続けて g を逆順にした各文字列の末尾に 1 を足したものを並べます。
gray 1 は [""] から作るので ["0", "1"] です。gray 2 は前半が 00 10、後半が逆順の 1 0 に 1 を足した 11 01 で、00 10 11 01 になります。gray 3 の前半はこれに 0 を足した 000 100 110 010、後半は逆順の 01 11 10 00 に 1 を足した 011 111 101 001 です。
よく見る形は map ('0' :) g ++ map ('1' :) (reverse g) で、新しい桁を先頭に付けて 000 001 011 010 110 111 101 100 を作ります。その出力を思い出して答えると、末尾に足していることを読み落とします。末尾に足しても、前半と後半の境目では新しい桁だけが変わり、ほかの隣どうしは g の中で隣り合っていた組なので、隣り合う文字列が1文字ずつしか違わない性質は保たれます。実際の出力は、よく見る列の各文字列を左右反転したものになっています。