Rob*_*een 82 recursion haskell functional-programming recursion-schemes
我正在寻找一些非常简单,易于掌握的递归方案和核心运动方案(catamorphisms,anorporphisms,hylomorphisms等)的解释,这些解释不需要跟随大量的链接,或者打开类别理论教科书.我确信我已经无意识地重新设计了许多这些方案,并在编码过程中将它们"应用"在我的头脑中(我相信我们很多人都有),但我不知道(共同)递归方案我是什么使用被称为.(好吧,我撒了谎.我刚刚读了一些这些,这引发了这个问题.但在今天之前,我一无所知.)
我认为这些概念在编程社区中的传播受到了令人生畏的解释和例子的阻碍 - 例如在维基百科上,而且在其他地方.
它们的名字也可能受到阻碍.我认为有一些替代的,较少的数学名称(关于香蕉和带刺铁丝网的东西？)但是我不知道我使用的递归方案的名称是什么.
我认为使用表示简单实际问题的数据类型的示例,而不是抽象数据类型(如二叉树)会有所帮助.
scl*_*clv 43
非常松散地说,一个变形只是一种轻微的概括fold,而一个变形是一种轻微的概括unfold.(并且一个hylomorphism只是一个展开,然后是折叠.).它们通常以更严格的形式呈现,以使与类别理论的联系更加清晰.更密集的形式使我们能够区分数据(初始代数的必然有限乘积)和codata(最终余代数的可能无限乘积).这种区别让我们保证永远不会在无限列表中调用折叠.通常编写catamorphisms和anamorphisms的有趣方式的另一个原因是,通过操作F-algebras和F-coalgebras(从仿函数生成),我们可以一劳永逸地写出它们,而不是一次在列表上,这反过来有助于明确为什么它们都是一样的.
但是从纯粹的直觉角度来看,你可以把cata和ana想象为减少和产生,而这就是它.
编辑:多一点
变形现象(Gibbons)就像一个由里而外的hylo - 它是一个折叠,然后展开.因此,您可以使用它来拆除流并构建一个具有可能不同结构的新流.
Ekmett为文献中的各种方案发布了一个很好的"现场指南":http://comonad.com/reader/2009/recursion-schemes/
然而,虽然"直观"的解释很简单,但链接的代码却不那么简单,其中一些博客文章可能在复杂/令人生畏的方面有点不足.
也就是说,除了组织形态学之外我不认为动物园的其他部分一定是大多数时候你想要直接思考的东西.如果你"得到"hylo和meta,你几乎可以用它们来表达任何东西.通常情况下,其他态射更具限制性,而不是更少(但因此"免费"为您提供更多属性).
hui*_*ker 23
一些参考文献,从大多数类别理论(但相关的给出"领土地图",将让你避免"点击大量的链接")到更简单和更自包含:
至于"香蕉和带刺铁丝网"的词汇,这来自Meijer,Fokkinga和Patterson的原始论文(以及其他作者的续集),总而言之,与不那么可爱的替代品一样重要: "名称"(香蕉等)只是它们被挂钩的结构的ascii表示法的图形外观的快捷方式.例如,catamorphisms(即folds)用(| _ |),并且par-with-parenthesis看起来像"香蕉",因此得名.这篇论文最常被称为"难以理解",因此,如果我是你,那么我不会首先看到它.
这些递归方案的基本参考(或者更确切地说,对于那些递归方案的关系方法)是Bird&de Moor的编程代数(除了作为打印请求之外,这本书是不可用的,但是有二手可用的副本它应该在图书馆里).它包含了对无点编程的更加节奏和详细的解释,如果仍然是"学术性的":本书介绍了一些类别理论词汇,尽管是以自足的方式.然而,练习(你在纸上找不到)有帮助.
Lex Augustjein 对态射进行排序,在各种数据结构上使用排序算法来解释递归方案.通过构造它几乎是"傻瓜的递归方案 ":
这个演示文稿提供了以简单的方式介绍各种态射的机会,即作为函数式编程中有用的递归模式,而不是通过类别理论的通常方法,这对于普通程序员来说往往是不必要的恐吓.
以使无符号,呈现另一种方法是杰里米·吉本斯一章折纸编程的编程的乐趣,与前一个有些重叠.其参考书目介绍了该主题的介绍.
编辑:Jeremy Gibbons只是让我知道他在阅读完这个问题之后在本书的网页上添加了整本书的参考书目链接.享受!
我担心这最后两篇参考文献只能对(cata | ana | hylo | para)态射有一个可靠的解释,但我希望这足以破解你在更多符号重的出版物中可以找到的代数形式.我不知道除了那四个之外的(共)递归方案的任何严格的非类别理论解释.
Ben*_*ord 16
蒂姆·威廉姆斯昨晚在伦敦Haskell的用户组提供了关于每个你所提到的那些中的激励例子递归方案辉煌的谈话.查看幻灯片:
http://www.timphilipwilliams.com/slides.html
在幻灯片的末尾有所有常见的嫌疑人(镜头,香蕉,铁丝网等),你也可以谷歌"折纸编程",这是一个很好的介绍,我以前没有遇到过.
当视频上传时,视频会在这里:
http://www.youtube.com/user/LondonHaskell
编辑大多数相关链接都在上面的huitseeker的答案中.