请用最简单,最无术语的英语解释"折叠的普遍属性"？

Question

我正在通过"真实世界Haskell"工作,这导致了一个免费的PDF,名为"关于折叠的普遍性和表现力的教程".它指出"折叠"是"普遍的".我正在与他对"普遍"的定义进行斗争,并希望听到那些已经投入时间消化的人:请用最简单,最无术语的英语解释"折叠的普遍属性"？什么是"普遍财产",为什么重要？

谢谢.

Answer 1

(术语模式关闭:-)

通用属性只是证明两个表达式相等的一种方式.(这就是术语"证明原则"的意思.)普遍属性说如果你能证明这两个方程式

g []     = v
g (x:xs) = f x (g xs)

那么你可以得出附加的等式

g = fold f v

反过来也是如此,但仅通过扩展定义来展示这一点是微不足道的fold.普遍属性是一个更深层次的属性(这是一种夸张的方式,说明为什么它是真的不太明显.)

这样做很有意思的原因是它可以让你通过归纳避免证据,这几乎总是值得避免.

Answer 2

该论文定义了两个属性:

g   []     = v
g (x : xs) = f x (g xs)

然后陈述fold不仅是满足这些属性的函数,而且是唯一满足这些属性的函数.它在这方面的独特之处在于它在纸张使用的意义上是"普遍的".

Answer 3

折叠的属性是它是一个列表递归函数,它等同于所有其他列表递归函数,只要你给它正确的参数.

它具有此属性,因为它接受将作为参数应用于列表中项目的函数.

例如,如果我们写了一个简单的求和函数:

sum []          = 0
sum (head:tail) = head + (sum tail)

那么我们实际上可以把它写成折叠函数,通过传入我们想要用来组合项目的(+)运算符:

sum list = foldl (+) 0 list

因此,任何简单地和递归地在列表上起作用的函数都可以被重写为折叠函数.等价是它拥有的财产.我相信他称这个属性是通用的,因为它适用于所有这些线性列表递归算法,毫无例外.

正如他解释的那样,这个属性如此有用的原因在于,因为我们可以显示所有这些其他算法实际上等同于折叠,通过证明折叠的某些东西,我们也证明了所有其他算法.

我个人发现折叠功能难以理解,所以有时我使用我自己的,看起来像这样:

-- forall - A kind of for next loop
-- list is list of things to loop through
-- f is function to perform on each thing
-- c is the function which combines the results of f
-- e is the thing to combine to when the end of the list is reached
forall :: [a] -> (a->b) -> (b->b->b) -> b -> b
forall [] f c e = e
forall (x:xs) f c e = c (f x) (forall xs f c e)

(这实际上比foldl更强大,因为它具有将函数f应用于列表中每个项目的额外功能.)

没有人证明我的功能.但这没关系,因为我可以证明我的函数实际上是折叠函数:

forall l f c e = foldl c e (map fn l)

因此,所有已被证明折叠的东西,也证明了我的forall功能,以及我整个程序中的所有用途.(注意我们甚至不需要考虑在forall和foldl的每个不同调用中提供什么类型的函数c,这没关系!)