Haskell 子集递归

Question

我是堆栈溢出和 Haskell 的新手，所以请让我知道是否有其他方法可以做到这一点！

这很大程度上是这个堆栈溢出问题的重复，Haskell Recursion Subsets，但是这个问题得到的答案并没有真正帮助我，我仍然对这个问题中的递归如何工作感到困惑。这是我尝试重新开始针对这个问题的对话。

这是问题：

我对以下代码片段中的递归如何工作感到困惑：

subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = [zs | ys <- subsets xs, zs <- [ys, (x:ys)]]

这段代码的输出是：

*Main> subsets [1,2,3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

我了解如何递归调用子集以及如何获取子集[] = [[]]，但我对它如何返回列表列表以及如何返回诸如 、 和 之类的列表[1]感到[1,3]困惑[2,3]。

再说一次，我是堆栈溢出的新手，所以请让我知道除了重复这个问题之外是否还有更好的方法。

Answer 1

我们先澄清一下subsets [3]。请记住，ys <- [ [] ]meanys接受列表 中的每个元素，[ [] ]该列表仅包含一个元素[]。

   subsets (3:[])
=> [zs | ys <- subsets [] ...
=> [zs | ys <- [ [] ] ...
=> [zs | ys <- [ [] ], zs <- [[], (3:[])]]
= [[], [3]] -- zs takes on each element of [[], (3:[])]

现在让我们忽略“实际”发生的事情并将逻辑用语言表达出来。

subsets (x:xs) = [zs | ys <- subsets xs, zs <- [ys, (x:ys)]]

方法：

Aggregate all zs
  where ys takes on in turn each of the subsets of the list without x,
  and for each ys,
    zs takes on the subset ys, and the subset ys and x together

例如：

   subsets [2,3]
=> ys takes on in turn each of the subsets of the list without 2
=> [[], [3]]

=> for each ys,
     zs takes on the subset ys, and the subset ys and 2 together
=> [[], [2], [3], [2,3]]