haskell - Haskell - 列表列表中元素组合的列表

Question

假设我有一些列表列表[[a, b], [c], [d, e, f], ...]，列表中的列表可以是任意长度。我已经对列表进行了排序，使得最短的列表排在第一位，并且我想生成列表中所有元素组合的列表，以便我得到一个列表[[a, c, d, ...], [a, c, e, ...], [a, c, f, ...], [b, c, d, ...], ...]，即通过更改从最后一个列表中选择的元素来生成组合首先，向上移动列表以更改类似于计数的元素。

使用这个列表，我将在列表的头部使用惰性评估，因为我只需要 1 个满足谓词的列表。如何生成列表？

标签： haskellfunctional-programminglist-comprehensionnested-listscombinatorics

Answer 1

是的，这是一个特例sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)：

Prelude> sequenceA ["ab", "c", "def"]
["acd","ace","acf","bcd","bce","bcf"]

在这里，我们因此设置f ~ [],t ~ []和a ~ Char例如。SequenceA因此在这里等同于：

-- sequenceA for f ~ [] and t ~ []
sequenceAList [] = [[]]
sequenceAList (c:cs) = (:) <$> c <*> sequenceAList cs

因此，对于单个项目sequenceA ["def"]等价于：

sequenceA ["def"] = (:) <$> "def" <*> [[]]

因此，它获取"def"、Char演员和的所有元素'd'，然后将其与列表的所有元素（仅）组合，从而产生、和。'e''f'[[]][]"d""e""f"

那么因为sequenceA ["c", "def"]它相当于：

sequenceA ["c", "def"] = (:) <$> "c" <*> ["d", "e", "f"]

因此产生：["cd", "ce", "cf"]，最后：

sequenceA ["ab", "c", "def"] = (:) <$> "ab" <*> ["cd", "ce", "cf"]

将产生：

sequenceA ["ab", "c", "def"] = ["acd", "ace", "acf", "bcd", "bce", "bcf"]