这个幂集生成函数是如何工作的？

Question

在尝试为给定的列表生成幂集时，我在网上找到了这个函数。没有解释，但测试表明它似乎工作正常。我无法理解这个函数是如何工作的。如果有任何解释，我将不胜感激。

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

- WeaklyTyped

---

我最喜欢的构建幂集的方法是：powerSet = filterM (const [False,True])（需要导入 Control.Monad (filterM)）。 - shang

不要重复造轮子：powerSet = subsequences - recursion.ninja

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 []  = [[]]

- Daniel Wagner

---

这段话的意思是，对于集合 A ∪ B 中的任何子集，都可以表示为 A 的一个子集和 B 的一个子集的并集。因此，为了计算集合 S 的幂集，我们可以将其分解为子集 A 和 B，分别计算它们的幂集 P(A) 和 P(B)，然后通过取并集来合并它们。 - Heatsink

@Heatsink 看起来像是分而治之！ - WeaklyTyped

Answer 2

您提供的代码使用了许多Haskell的语法糖（关于语义，其他人已经涵盖了，我将省略）。以下是我在代码中注意到的主要语法：

“您提供的代码使用了许多Haskell的语法糖（关于语义，其他人已经涵盖了，我将省略）。以下是我在代码中注意到的主要语法：”

• lack of type annotations. Haskell uses type inference, which makes type annotations optional (but recommended). Use GHCi to determine the type:

  *Main> :t generateSubset
  generateSubset :: [a] -> [[a]]
  

• pattern matching. See LYAH for a nice introduction.

• let expressions. Again, see LYAH.

• partial application -- (x:). LYAH for the win!

• operator sections -- (x:) again. This allows for partial application of an infix function (in this case, :). It's the same as:

  myCons :: a -> [a] -> [a]
  myCons e es = e : es
  
  myPartial :: [a] -> [a]
  myPartial = myCons x -- partial application
  

• use of function/operator precedences -- p ++ map (x:) p. This is parsed as (p) ++ (map (x:) p), because function application always has higher precedence than infix operator application.

- Matt Fenwick

Answer 3

空列表的幂集是一个仅包含空列表的列表。

要计算非空列表的幂集，首先需要计算尾部的幂集。然后将该幂集与一个版本的幂集连接起来，其中头部已经添加到所有子集中。因此，如果尾部的幂集是[[2,3],[2],[3],[]]，头部是1，则生成的幂集将是[[], [3], [2], [2,3], [1],[1,3],[1,2],[1,2,3]]。

- sepp2k

---

“generateSubset (x:xs)” 的语法意义是什么？既然函数只接受一个列表，为什么不直接使用“generateSubset x”呢？ - WeaklyTyped

(x:xs) 将 x 设为列表的头部，将 xs 设为尾部。这被称为模式匹配。在 http://learnyouahaskell.com/syntax-in-functions#pattern-matching 上了解更多相关信息。 - tauli

@tauli 所以，通过头尾连接，有效地给出了完整的列表。对吗？ - WeaklyTyped

好的。像 [1,2,3] 这样的列表也可以写成 1:2:3:[] 或者 1:[2,3] 的形式。最后一个例子符合 (x:xs) 的模式，因此 x 变成了 1，xs 变成了 [2,3]。 - tauli