2026-08-26
Words.hs
wordsOf :: Int -> [a] -> [[a]]
wordsOf 0 _ = []
wordsOf n xs = [x : w | x <- xs, w <- rest]
where
rest = wordsOf (n - 1) xs
main :: IO ()
main = print (wordsOf 2 "ab")
文字の候補 xs を使って作れる長さ n の文字列をすべて返すつもりの wordsOf です。wordsOf 2 "ab" は ["aa","ab","ba","bb"] になるはずが、いまは [] が返ります。
Answer
Wrong
wordsOf 0 _ = []
wordsOf n xs = [x : w | x <- xs, w <- rest]
where
rest = wordsOf (n - 1) xs
wordsOf 1 "ab" は、rest の要素 w ごとに、その前に x を付けたものを並べます。rest は wordsOf 0 "ab" で、いまは空リストです。w <- で取り出せる要素が1つも無いので、x を何にしても文字列は作られず、wordsOf 1 "ab" も [] になります。wordsOf 2 "ab" はこの空リストを rest にするので、同じ理由で [] です。基底ケースが空なので、どの n でも結果は空になります。
Right
wordsOf 0 _ = [[]]
wordsOf n xs = [x : w | x <- xs, w <- rest]
where
rest = wordsOf (n - 1) xs
長さ0の文字列は、空文字列のちょうど1つです。基底ケースを、空文字列1つだけを持つ [[]] にすると、wordsOf 1 "ab" では w がその空文字列になり、"a" と "b" が作られます。それを rest にした wordsOf 2 "ab" は、各 x と各 w を組み合わせて ["aa","ab","ba","bb"] を返します。
候補が k 文字なら、長さ n の文字列は k の n 乗個あります。n = 0 のとき k の0乗は1なので、結果の個数で考えても基底ケースは1要素のリストです。標準の replicateM 0 xs も [[]] を返します。