请用最简单，最不含术语的英语解释，即“折叠的通用属性”？

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，这没关系！）

Answer 4

我刚刚在维基百科（Wikipedia）的“通用财产”中找到了一个新的（对我来说）。它为这个问题提供了大量的启示。 这是链接： 从中，我（十次）得出以下结论：

1. 尽管您可能会想到100种不同的方式来浏览列表，一路计算并从列表中产生一个最终价值，但所有100种方法都是 同构 （这意味着最终它们是一样的）。实际上，只有一种将列表减少到一个值的方法，那就是折叠。
2. 折叠也是如何将列表减少到单个值的“最有效的解决方案”。或者，您可能会说，最“有方面的”或最“简化”的解决方案。

看来，这两个点共同捕获了“通用属性”一词的含义。

Answer 5

尽管如果不阅读本系列中的先前帖子来解释通用属性，这可能很难遵循，但该帖子对fold的通用属性以及地图和滤镜提供了详细的类别说明。

http://jeremykun.com/2013/09/30/the-universal-properties-of-map-fold-and-filter/

尽管我尚未编写它，但后续内容将概括（尽管更简单地理解，尽管更加抽象）对一般数据结构进行了“类似折叠的”操作。

请参阅此帖子以获取有关什么是通用财产的更多信息： http://jeremykun.com/2013/05/24/universal-properties/

并在此处链接到该系列中的所有帖子： http://jeremykun.com/main-content/

实际上，当前接受的答案是了解普遍财产对折叠所说的最简单方法。与上述相关的文章简单地通过类别理论提供了更详细的技术描述，而这些论文中没有所讨论的论文。但是，我不同意接受答案中的说法，即普遍财产比无行话的声明要深得多。折叠的通用属性完全是相同的陈述，只是根据分析类别理论分析事物的性质，将其装入初始对象和最终对象的语言。该分析是有价值的，正是由于其自然概括。