recursion计划的傻瓜?

我正在寻找一些非常简单,易于理解的recursionscheme和核心引力scheme(变形,变形,变形等)的解释,它们不需要大量的链接,也不需要打开类别理论教科书。 我确信我已经在无意识中重塑了许多这些scheme,并在编码过程中将它们“应用”在我的头脑中(我相信我们中的许多人都有),但是我不知道(共)recursionschemeI使用被称为。 (好的,我撒谎了,刚才我刚刚读到了其中的几个,这引发了这个问题,但在今天之前,我没有任何线索。

我认为这些概念在编程社区中的传播受到了可怕的解释和例子的阻碍,例如维基百科,还有其他地方。

也可能被他们的名字阻碍了。 我认为还有一些其他的math名称(有关香蕉和铁丝网的东西?),但我不知道我使用的recursionscheme的名字是什么。

我认为这将有助于使用代表简单现实世界问题的数据types的示例,而不是像二叉树这样的抽象数据types。

非常松散地说,一个变形只是一个fold的轻微泛化,而一个变形是一个稍微泛化的unfold 。 (而且一个hylomorphism只是一个展开,然后是一个折叠)。 它们通常以更严谨的forms呈现,以便与类别理论的联系更加清晰。 更密集的forms让我们区分数据(初始代数的必然有限乘积)和codata(最终余代数的可能无限乘积)。 这种区别让我们保证折叠永远不会在无限列表上被调用。 另一个有趣的变形和变形一般写成的方式的原因是,通过对F-代数和F-代数(由函数生成)进行操作,我们可以一劳永逸地写出它们,而不是一次一个地列出,二叉树等。这反过来有助于明确为什么他们都是一样的东西。

但是从纯粹的直觉angular度来看,你可以把cata和ana想成是减less和产生的,就是这样。

编辑:多一点

一个变形(吉本斯)就像是一个从内到外的人 – 它的一个折叠,然后展开。 所以你可以用它来拆卸一个stream,并build立一个有可能不同结构的新stream。

Ekmett为文献中的各种scheme发布了一个很好的“现场指南”: http : //comonad.com/reader/2009/recursion-schemes/

然而,虽然“直观”的解释是直截了当的,但是链接的代码却不那么简单,而且其中的一些博客文章可能在复杂的/禁止的方面是一时的。

这就是说,除了可能的组织形态,我不认为动物园的其他部分是你想要直接思考的东西。 如果你“变得”不起眼,你可以单独expression任何东西。 其他态射通常更具限制性,而不是更less(但是因此给你更多的属性“免费”)。

从最基本的类别理论(但相关的给一个“领土地图”,可以让你避免“点击大量的链接”)几个参考,更简单和更独立:

  • 就“香蕉和铁丝网”词汇而言,这是来自Meijer,Fokkinga&Patterson (以及其他作者的续集) 的原始文件,总的来说,就像不那么可爱的备选scheme一样: “名字”(香蕉等)只是一个捷径,它们所固定的结构的ASCII符号的graphics外观。 例如,变形(即折叠)用(| _ |) ,并且括号与括号看起来像“香蕉”,因此名字。 这是最常被称为“难以穿越”的论文,因此,如果我是你,我不会首先查找这些论文。

  • 这些recursionscheme的基本参考(或更确切地说,对于这些recursionscheme的关系方法)是Bird&de Moor的编程代数 (除了作为打印要求外,书是不可用的,但是有二手可用的副本它应该在图书馆)。 它包含了一个更加节奏和详细的点免费编程的解释,如果仍然是“学术”的话:本书引入了一些类别理论词汇,尽pipe是一个独立的方式。 然而,练习(你不会在一篇论文中find)有帮助。

  • Lex Augustjein 对态射进行sorting ,使用各种数据结构上的sortingalgorithm来解释recursionscheme。 这几乎是“ build模的recursionscheme ”:

    这个演示提供了以简单的方式介绍各种态射的机会,也就是作为function编程中有用的recursion模式,而不是通过类别理论的常用方法,这对于普通程序员来说往往是不必要的恐吓。

  • 另一种制作无符号演示的方法是Jeremy Gibbons的编程 乐趣 “ 折纸编程 ”一章 ,与前一章有所重叠。 其参考书目介绍了该主题的介绍。

    编辑: 杰里米·吉本斯(Jeremy Gibbons)只是让我知道他在阅读这个问题后在书的网页上添加了整本书的参考书目链接。 享受

恐怕这两个参考文献只是给出了(态)态射的一个可靠的解释,但是我希望这将足以摧毁在更多符号化的出版物中可以find的代数forms。 我不知道这四种以外的(共)recursionscheme的严格的非范畴论解释。

蒂姆·威廉斯(Tim Williams)昨晚在伦敦哈斯克尔用户组织(London Haskell User Group)发表了一个关于recursion计划的精彩演讲,并提供了你提到的每个人的激励范例。 看看幻灯片:

http://www.timphilipwilliams.com/slides.html

在幻灯片的末尾有所有常见的嫌疑人(镜头,香蕉,铁丝网等等),还可以谷歌“折纸编程”这是一个很好的介绍,我以前没有遇到过。

video将在这里上传时:

http://www.youtube.com/user/LondonHaskell

编辑大多数有问题的链接在上面的huitseeker的答案。