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

Question

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

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

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"中，Characters '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"]