Haskell无依赖实现allCombinations无限组合列表函数

直接上无导入的纯Haskell实现：

allCombinations :: [a] -> [[a]]
allCombinations xs = concat $ iterate nextLevel [[]]
  where
    nextLevel ss = [x : s | s <- ss, x <- xs]

思路解释 #

这个实现按组合长度分层生成结果：

• 起始层只有空列表[]（对应长度为0的唯一组合）
• 每一层的组合由上一层的所有组合，分别前置输入列表xs中的每个元素得到：
  • 比如输入[True,False]，第一层是[[]]，第二层就是[True: [], False: []]即[[True],[False]]
  • 第三层则是把第二层的每个列表分别前置True和False，得到[[True,True],[False,True],[True,False],[False,False]]
• iterate会无限重复这个生成下一层的操作，得到一个包含各层组合的无限列表（[[[]], [[True],[False]], [[True,True],...], ...]）
• 最后用concat把所有层的组合平铺成一个无限列表，就得到了题目要求的顺序

验证一下，调用take 10 (allCombinations [True,False])会返回你给出的预期结果：

[[],[True],[False],[True,True],[False,True],[True,False],[False,False],[True,True,True],[False,True,True],[True,False,True]]

如果输入是空列表[]，函数会返回[[]]，这是合理的——空列表只有空组合这一种可能。

内容的提问来源于stack exchange，提问作者Robert