Namaran

Code daily. Without assist.

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] も同じリストを同じ順で返します。