Haskell で Kleene閉包

与えられた集合 A の要素よりなるすべての有限リストが欲しい場合があります．このようなリスト集合はしばしば A のクリーネ閉包( http://ja.wikipedia.org/wiki/クリーネ閉包 ）と呼ばれ, A* と書かれます．A のクリーネ閉包から空リストを取り除いたものを A+ と書くことがあります．Aが空でなければ A* は無限集合ですが Haskell では無限リストとして表現できます．

kleene.hs

kleeneStar :: [a] -> [[a]]
kleeneStar xs = [[], xs] ++ [ y:zs | zs <- kleeneStar xs, y <- xs]

kleenePlus = tail . kleeneStar

使用例

Prelude> :l kleene.hs
[1 of 1] Compiling Main             ( kleene.hs, interpreted )
Ok, modules loaded: Main.
*Main> take 30 $ kleeneStar "ab"
["","ab","a","b","aab","bab","aa","ba","ab","bb","aaab","baab","abab","bbab","aa
a","baa","aba","bba","aab","bab","abb","bbb","aaaab","baaab","abaab","bbaab","aa
bab","babab","abbab","bbbab"]
*Main> take 30 $ kleenePlus "ab"
["ab","a","b","aab","bab","aa","ba","ab","bb","aaab","baab","abab","bbab","aaa",
"baa","aba","bba","aab","bab","abb","bbb","aaaab","baaab","abaab","bbaab","aabab
","babab","abbab","bbbab","aaaa"]
*Main> take 50 $ kleeneStar "abc"
["","abc","a","b","c","aabc","babc","cabc","aa","ba","ca","ab","bb","cb","ac","b
c","cc","aaabc","baabc","caabc","ababc","bbabc","cbabc","acabc","bcabc","ccabc",
"aaa","baa","caa","aba","bba","cba","aca","bca","cca","aab","bab","cab","abb","b
bb","cbb","acb","bcb","ccb","aac","bac","cac","abc","bbc","cbc"]
*Main>

幾らか重複が見られますが，そこそこ使えるのではないかと思います．

面白い点
１．kleeneStar xs の定義には再び kleeneStar xs が現れています．
２． リスト内包表記の順番を間違えると大変なことに…．

二番目の点についての具体例．

kleeneBad :: [a] -> [[a]]
kleeneBad xs = [[], xs] ++ [ y:zs | y <- xs, zs <- kleeneBad xs]

のように定義するとまったく使い物になりません：

*Main> take 30 $ kleeneBad "ab"
["","ab","a","aab","aa","aaab","aaa","aaaab","aaaa","aaaaab","aaaaa","aaaaaab","
aaaaaa","aaaaaaab","aaaaaaa","aaaaaaaab","aaaaaaaa","aaaaaaaaab","aaaaaaaaa","aa
aaaaaaaab","aaaaaaaaaa","aaaaaaaaaaab","aaaaaaaaaaa","aaaaaaaaaaaab","aaaaaaaaaa
aa","aaaaaaaaaaaaab","aaaaaaaaaaaaa","aaaaaaaaaaaaaab","aaaaaaaaaaaaaa","aaaaaaa
aaaaaaaab"]