Haskell如何编写接收任意数量列表并生成所有元素组合的函数

嘿，我明白你遇到的问题了！你尝试的递归思路方向是对的，但嵌套调用的时候犯了一个小错误——你把前一次生成的列表的列表直接当成了下一次的输入，结果导致组合出来的是列表嵌套列表，而不是把元素追加到已有组合里。比如你调用foo (foo [0,1] [0,1]) [0,1]时，前一个foo返回的是[[0,0],[0,1],[1,0],[1,1]]，再和[0,1]组合就会生成[[[0,0],0], [[0,0],1], ...]，这显然不是你想要的扁平化组合结构。

解决方案1：先实现处理列表的列表的笛卡尔积函数 #

我们可以先写一个接受列表的列表的函数，递归生成所有元素组合：

cartesianProduct :: [[a]] -> [[a]]
cartesianProduct [] = [[]]  -- 递归基：空列表的列表返回包含空列表的列表
cartesianProduct (firstList:remainingLists) =
  [element : combo | element <- firstList, combo <- cartesianProduct remainingLists]

这个函数的逻辑很直观：

• 如果输入是空的列表集合，返回[[]]（保证递归能正常拼接后续元素）
• 如果输入有第一个列表firstList和剩下的列表集合remainingLists，就遍历firstList的每个元素，把它拼到remainingLists的每个组合前面，最终得到所有可能的组合。

测试一下：

cartesianProduct [[0,1], [0,1,2]]  -- 返回 [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2]]
cartesianProduct [[0,1], [0,1], [0,1]]  -- 返回所有8种三元组合

解决方案2：实现支持任意数量参数的foo函数 #

如果想让foo直接接受任意数量的列表参数（而不是先把列表打包成列表的列表），可以用Haskell的类型类来实现可变参数的函数：

class CartesianResult r where
    foo :: [a] -> r

-- 当最后一个参数是列表时，返回单个元素的列表的列表
instance CartesianResult [[a]] where
    foo xs = [[x] | x <- xs]

-- 当还有后续列表参数时，递归拼接组合
instance (CartesianResult r) => CartesianResult ([a] -> r) where
    foo currentList nextList =
        [elem : combo | elem <- currentList, combo <- foo nextList]

这样你就可以像预期那样调用：

foo [0,1] [0,1,2]  -- 正确返回目标组合
foo [0,1] [0,1] [0,1]  -- 正确返回所有三元组合

小彩蛋：用标准库函数直接实现 #

其实Haskell标准库的sequence函数已经实现了这个功能！它的作用就是把一个列表的列表转换成所有可能的元素组合的列表，完全符合你的需求：

sequence [[0,1], [0,1,2]]  -- 和你要的结果一致
sequence [[0,1], [0,1], [0,1]]  -- 同样返回正确的组合

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