2026-09-13
Bits.hs
bins :: [String]
bins = "" : [b ++ [c] | b <- bins, c <- "01"]
main :: IO ()
main = print (take 7 bins)
binsは自分自身を使って定義されています。これは何を出力するでしょうか?
Answer
["","0","1","00","01","10","11"](その後に改行)。先頭の""は無条件に決まっているので、内包表記はb = ""から"0"と"1"を作れます。それがリストの2・3番目になり、今度はb = "0"から"00"、"01"、b = "1"から"10"、"11"……と、常に「すでに出来上がった要素」だけを読みながら次の要素を作っていきます。遅延評価なので、要素はtake 7が要求した分しか作られず、この無限リストの定義が止まらなくなることもありません。「長さn+1の文字列は、長さnの文字列の後ろに0か1を付けたもの」という再帰的な定義が、関数ではなくデータとしてそのまま書けています。