这个功率集生成函数如何工作

Question

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

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

Answer 1

这是一个很容易证明的powersets属性：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

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

要计算非空列表的功率集，它首先计算尾部的功率集。然后它将该功率集合与头部已被预置到所有子集的功率集合的版本相连接。因此，如果尾部的功率集合是[[2,3],[2],[3],[]]且头部是1，则所得到的功率集合将是[[], [3], [2], [2,3], [1],[1,3],[1,2],[1,2,3]]。

Answer 3

你给的代码使用了很多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)，因为function application always has higher precedence than infix operator application。