递归计划的傻瓜？ [英] Recursion schemes for dummies?
问题描述
我正在寻找一些非常简单，易于理解的递归方案和核心引力方案（变形，变形，变形等）的解释，它们不需要大量的链接或打开类别理论教科书。我确信我已经在无意识中重塑了这些方案中的许多，并且在编码过程中将它们应用在我的头脑中（我相信我们中的很多人都有），但我不知道（共）递归方案I使用被称为。 （好的，我说谎了，我刚刚读到了其中的一些，这引发了这个问题，但在今天之前，我没有任何线索。）
我认为这些概念在编程社区中的传播一直受到一些常见的解释和例子的阻碍 - 例如在维基百科上，但在其他地方也是如此。 可能也有可能被他们的名字阻碍了。我认为还有一些其他的数学名称（有关香蕉和铁丝网的东西？），但我不知道我使用的递归方案的名称是什么。
我认为这将有助于使用具有代表简单现实世界问题的数据类型的示例，而不是像二叉树这样的抽象数据类型。
解决方案非常松散地说，变形只是编辑：多一点
<变形（吉本斯）就像是一个内向外的人 - 它是一个折叠，然后展开。所以你可以用它来拆卸一个流，并建立一个具有不同结构的新流程。
Ekmett为各种方案发布了一个很好的现场指南文献： http://comonad.com/reader/2009/recursion-schemes/ I'm looking for some really simple, easy-to-grasp explanations of recursion schemes and corecursion schemes (catamorphisms, anamorphisms, hylomorphisms etc.) which do not require following lots of links, or opening a category theory textbook. I'm sure I've reinvented many of these schemes unconsciously and "applied" them in my head during the process of coding (I'm sure many of us have), but I have no clue what the (co)recursion schemes I use are called. (OK, I lied. I've just been reading about a few of them, which prompted this question. But before today, I had no clue.) I think diffusion of these concepts within the programming community has been hindered by the forbidding explanations and examples one tends to come across - for example on Wikipedia, but also elsewhere. It's also probably been hindered by their names. I think there are some alternative, less mathematical names (something about bananas and barbed wire?) but I have no clue what the cutsier names are for recursion schemes that I use, either. I think it would help to use examples with datatypes representing simple real-world problems, rather than abstract data types such as binary trees. Extremely loosely speaking, a catamorphism is just a slight generalization of But from a pure intuition standpoint, you can think of cata and ana as reducing and producing, and that's about it. Edit: a bit more A metamorphism (Gibbons) is like an inside-out hylo -- its a fold followed by an unfold. So you can use it to tear down a stream and build up a new one with a potentially different structure. Ekmett posted a nice "field guide" to the various schemes in the literature: http://comonad.com/reader/2009/recursion-schemes/ However, while the "intuitive" explanations are straightforward, the linked code is less so, and the blog posts on some of these might be a tad on the complex/forbidding side. That said, except perhaps for histomorphisms I don't think the rest of the zoo is necessarily something you'd want to think with directly most of the time. If you "get" hylo and meta, you can express nearly anything in terms of them alone. Typically the other morphisms are more restrictive, not less (but therefore give you more properties "for free"). 这篇关于递归计划的傻瓜？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！fold, and an anamorphism is a slight generalization of unfold. (And a hylomorphism is just an unfold followed by a fold.). They're presented in a more rigorous form usually, to make the connection to category theory clearer. The denser form lets us distinguish data (the necessarily finite product of an initial algebra) and codata (the possibly infinite product of a final coalgebra). This distinction lets us guarantee that a fold is never called on an infinite list. The other reason for the funny way that catamorphisms and anamorphisms are generally written is that by operating over F-algebras and F-coalgebras (generated from functors) we can write them once and for all, rather than once over a list, once over a binary tree, etc. This in turn helps make clear exactly why they're all the same thing.
