考虑一个单链表.它看起来像
data List x = Node x (List x) | End
定义折叠函数是很自然的
reduce :: (x -> y -> y) -> y -> List x -> y
从某种意义上说,reduce f x0替代每一个Node有f一位End用x0.这就是Prelude所说的折叠.
现在考虑一个简单的二叉树:
data Tree x = Leaf x | Branch (Tree x) (Tree x)
定义诸如的函数同样很自然
reduce :: (y -> y -> y) -> (x -> y) -> Tree x -> y
请注意,这种减少具有完全不同的特征; 而基于列表的一个本质上是顺序的,这个新的基于树的一个具有更多的分而治之的感觉.你甚至可以想象par在那里扔几个组合器.(你会在列表版本中放置这样的东西？)
我的问题:这个功能是否仍被归类为"折叠",还是其他东西？(如果是的话,它是什么？)
基本上每当有人谈论折叠时,他们总是谈论折叠列表 …