列表的所有可能的子列表

Question

我需要编写一个函数来生成一个列表，该列表包含列表中所有可能的子列表的列表。所以类型必须是：

partitions :: [a] -> [[[a]]]

它应该给出：

分区[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

正如你所期望的那样，这会出现类型错误，但我不知道如何修复。我觉得我错过了一些明显的东西，任何帮助都将不胜感激。

Answer 1

我将从直接递归开始。分解一下，在一个较长的列表中，第一个元素有什么可能性？

1. 它可以是其中一个分区列表的唯一元素
2. 它可以是包含多个元素的分区列表的一部分

在您的示例中，您似乎希望保持原始元素的顺序，因此每个分区的成员只能是连续的子列表，这使它更容易。

所以我们可以启动

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]

其中，我们需要明确区分空分区(在递归结束时)和非空分区的情况，这在上面是通过绑定到模式(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]]]

使用列表monad的绑定(>>=)是flip concatMap的事实，版本

partitions (x:xs) = concatMap insert (partitions xs)
where
insert [] = [[[x]]]
insert (ys:yss) = [[x]:ys:yss, (x:ys):yss]

可能更可读。