这个电源设置生成功能如何工作

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}

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

-- 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

唯一剩下的就是为递归提供一个基本案例,这只是来自powerset的定义:

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