flâneur

adventures in uncertainty: An Introduction to Recursion Schemes

blog.sumtypeofway.com · 3,648 words · saved by 1 readers

In 1991, Erik Meijer, Maarten Fokkinga, and Ross Paterson published their now-classic paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. Though this paper isn’t widely known outside of the functional programming community, its contributions are astonishing: the authors use category theory to express a set of simple, composable combinators, called recursion schemes, that automate the process of traversing and recursing through nested data structures. Though recursion schemes predate Meijer et. al’s work, this paper brings the enormous abstractive power of category theory to bear on the subject of traversing data structures—it’s a magnificent example of how category-theoretical concepts can bring both rigor and simplicity to day-to-day programming tasks. Because nested structures appear in almost every problem domain and programming environment, from databases to 3D graphics to filesystems, the act of iterating through these structures is common, so common that

An Introduction to Recursion Schemes 2014-02-15 In 1991, Erik Meijer, Maarten Fokkinga, and Ross Paterson published their now-classic paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire . Though this paper isn’t widely known outside of the functional programming community, its contributions are astonishing: the authors use category theory to express a set of simple, composable combinators, called recursion schemes , that automate the process of traversing and recursing through nested data structures. Though recursion schemes predate Meijer et. al’s work, this paper bri

saved by

related reading