algorithm - 在 Haskell 的列表推导中构建列表列表

Question

我在 wiki.haskell.org 上找到了一种算法，用于从给定列表中生成 n 个元素的组合。它构建[[a]]通过列表理解。

combos :: Int -> [a] -> [[a]]
combos 0 _  = [ [] ]
combos n xs = [ y:ys | y:xs' <- tails xs
                           , ys <- combos (n-1) xs']

假设我们执行 combos 2 [1,2,3] ，那么主要功能将如下所示:

combos 2 [1,2,3] = [ y:ys | y:xs' <- [[1,2,3],[2,3],[3],[]]
                           , ys <- combos 1 xs']

我假设在一个模式中 y:xs' y是一个列表(第一次运行时为 [1,2,3])和 xs'是列表的列表(第一次运行时为 [[2,3],[3],[]])。

我对这部分感到困惑，当 xs'作为递归 combos 的参数抛出调用 ( ys <- combos 1 xs') . ( combos 现在变成 [[a]] -> [[[a]]] ?)

一切进展如何？你能描述一下这个功能是如何工作的吗？

Answer 1

注意 … <- … 之间的区别和 let … = …这里。在列表理解中，x <- xs 的两边不能有相同的类型； x依次分配给 xs 的每个元素 .

在您的示例中，(y:xs') <- [[1,2,3],[2,3],[3],[]]意味着我们从该列表中获取 与模式 (y:xs') 匹配的元素.所以我们第一次在这里进行选择，y == 1和 xs' == [2,3] ;第二次我们进行选择，y == 2和 xs' == [3]等等。