2026-11-16
AllBools.hs
allBools :: Int -> [[Bool]]
2つの実装に同じ入力をすべて与えて結果を突き合わせるために、長さ n の Bool のリストをすべて並べたリストを返す allBools を書いてください。False を True より小さいとみなし、先頭の要素から順に比べた小さい順に並べます。n は 0 以上で、n が 0 なら長さ0のリスト、つまり空リストだけが1つ入ったリストを返します。
入力例 1
allBools 2
出力例 1
[[False,False],[False,True],[True,False],[True,True]]
入力例 2
allBools 1
出力例 2
[[False],[True]]
入力例 3
allBools 0
出力例 3
[[]]
Reference
Reference
allBools :: Int -> [[Bool]]
allBools 0 = [[]]
allBools n = [b : bs | b <- [False, True], bs <- allBools (n - 1)]
長さ n のリストは、先頭の要素1つと、長さ n - 1 の残りに分けられます。リスト内包表記で、先頭 b を False と True から選び、残り bs を allBools (n - 1) から選んで b : bs を作ると、すべての組み合わせが1回ずつ出てきます。左の生成器 b が外側のループになるので、先頭が False のものがすべて並んでから True のものが並び、問題の順序になります。掲載したのは参考実装で、唯一の正解ではありません。
再帰の止まる先の allBools 0 = [[]] は、長さ0のリストが空リスト1つだけあることを表します。ここを [] にすると、内包表記の bs が1つも選べないので、どの n でも結果が空になります。allBools 1 は [[]] の唯一の要素に False と True を付けて [[False],[True]]、allBools 2 はその2つにさらに先頭を付けて4つになり、長さ n では 2n 個のリストが並びます。Control.Monad の replicateM n [False, True] も同じリストを同じ順で返します。