我需要编写一个函数来生成一个列表,其中包含列表的所有可能子列表的列表。所以类型必须是:
partitions :: [a] -> [[[a]]]
它应该给出:
partitions [1..4] = [[[1],[2],[3],[4]], [[1,2],[3],[4]], [[1],[2,3],[4]], [[1,2,3],[4]], [[1],[2],[3,4]], [[1,2],[3,4]], [[1],[2,3,4]], [[1,2,3,4]]]
我认为列表理解是最好的方法。到目前为止,我有:
partitions :: [a] -> [[[a]]]
partitions (x:xs) = foldr insert [[]] (x:xs)
where insert ys zs = ys:x:zs
如您所料,这会引发类型错误,但我不知道如何修复它。我觉得我遗漏了一些明显的东西,任何帮助将不胜感激。
最佳答案
我将从直接递归开始。分解一下,较长列表中的第一个元素有什么可能性?
从您的示例中,您似乎希望保持原始元素有序,因此每个分区的成员只能是连续的子列表,这使得它更容易一些。
所以我们可以开始
partitions :: [a] -> [[[a]]]
partitions [] = [[]] -- only one partition of an empty list, an empty partition
partitions (x:xs) = [[x]:part | part <- partitions xs] ++ [(x:ys):yss | (ys:yss) <- partitions xs]
产生
*Partitions> partitions [1,2,3,4]
[[[1],[2],[3],[4]],[[1],[2],[3,4]],[[1],[2,3],[4]],[[1],[2,3,4]],[[1,2],[3],[4]],[[1,2],[3,4]],[[1,2,3],[4]],[[1,2,3,4]]]
不是所需的顺序。如果这很重要,我们必须重写。期望的顺序直接连续列出第一个元素的两个选项,所以我们可以写它
partitions (x:xs) = partitions xs >>= \zs -> case zs of
[] -> [[[x]]]
(ys:yss) -> [[x]:ys:yss, (x:ys):yss]
我们需要明确区分空分区(在递归结束时)和非空分区的情况,这在上面是通过绑定(bind)到模式
(ys:yss)
隐式完成的。 .这会产生所需的顺序*Partitions> partitions [1,2,3,4]
[[[1],[2],[3],[4]],[[1,2],[3],[4]],[[1],[2,3],[4]],[[1,2,3],[4]],[[1],[2],[3,4]],[[1,2],[3,4]],[[1],[2,3,4]],[[1,2,3,4]]]
使用绑定(bind)
(>>=)
的事实对于列表单子(monad)是flip concatMap
, 版本partitions (x:xs) = concatMap insert (partitions xs)
where
insert [] = [[[x]]]
insert (ys:yss) = [[x]:ys:yss, (x:ys):yss]
可能更具可读性。
关于list - 列表的所有可能子列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13443237/