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

Answer 2

您提供的代码使用了很多 Haskell 的语法糖。（因为其他人已经涵盖了语义，我将省略它。）这是我在代码中注意到的主要语法：

• 缺少类型注释。Haskell 使用类型推断，这使得类型注释是可选的（但推荐）。使用 GHCi 确定类型：

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

• 模式匹配。请参阅LYAH以获得很好的介绍。

• 让表达式。再次，参见LYAH。

• 部分应用—— (x:)。 LYAH为了胜利！

• 操作员部分 -(x:)再次。这允许部分应用中缀函数（在本例中为:）。它与以下内容相同：

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

• 使用函数/运算符优先级 - p ++ map (x:) p。这被解析为(p) ++ (map (x:) p)，因为函数应用程序总是比中缀运算符应用程序具有更高的优先级。

Answer 3

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

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