haskell - 这个发电机组发电功能是如何工作的

Question

在尝试为给定列表生成幂集时，我在互联网上遇到了这个函数。没有任何解释，但测试表明它似乎可以正常工作。我无法理解此功能是如何工作的。我将感谢任何此类解释。

generateSubset [] = [[]]
generateSubset (x:xs) = let p = generateSubset xs in p ++ map (x:) p

Answer 1

这是幂集的一个很容易证明的性质:P(A ∪ B) = {a ∪ b | a∈P(A)，b∈P(B)}。特别地，如果我们将一个特定的集合 S 分解为一个元素 s 和所有不是 s 的元素 S'，那么

P(S) = P({s} ∪ S')
     = {a ∪ b | a ∈ P({s}), b ∈ P(S')}.

现在，P({s}) 足够小，我们可以手动计算它:P({s}) = {{}, {s}}。利用这个事实，我们学习

P(S) = {a ∪ b | a ∈ {{}, {s}}, b ∈ P(S')}
     = {b | b ∈ P(S')} ∪ {{s} ∪ b | b ∈ P(S')}
     = P(S') ∪ {{s} ∪ b | b ∈ P(S')}
     = let p = P(S') in p ∪ {{s} ∪ b | b ∈ p}

也就是说，计算非空集的幂集的一种方法是选择一个元素，计算余数的幂集，然后将元素添加或不添加到每个子集。您展示的函数只是将其转换为代码，使用列表作为集合的表示:

-- P         ({s} ∪ S') = let p = P(S')             in p  ∪ {{s} ∪ b | b ∈ p}
generateSubset (x:xs)   = let p = generateSubset xs in p ++     map (x:) p

唯一剩下的就是给出递归的基本情况，这直接来自于幂集的定义:

-- P          ({}) = {{}}
generateSubset []  = [[]]