(root)/Notes/Notes/notes/recursion.md RSS

Recursion

see y ‹combinator

#stub

Recursion Scheme

resource the PNLC prelude, makes use of recursion› schemes throughout --- https://github.com/Bricktech2000/PNLC/blob/master/prelude.pnlc

resource Recursion Schemes by Tim Williams at London Haskell, with implementations for everything and lots of real-world use-cases --- https://youtu.be/Zw9KeP3OzpU and slides-final.pdf http://www.timphilipwilliams.com/slides.html

resource An Introduction to Recursion Schemes by Patrick Thomson

  1. adventures in uncertainty_ An Introduction to Recursion Schemes.pdf --- https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html
  2. adventures in uncertainty_ Recursion Schemes, Part II_ A Mob of Morphisms.pdf --- https://blog.sumtypeofway.com/posts/recursion-schemes-part-2.html
  3. adventures in uncertainty_ Recursion Schemes, Part III_ Folds in Context.pdf --- https://blog.sumtypeofway.com/posts/recursion-schemes-part-3.html
  4. adventures in uncertainty_ Recursion Schemes, Part IV_ Time is of the Essence.pdf --- https://blog.sumtypeofway.com/posts/recursion-schemes-part-4.html
  5. adventures in uncertainty_ Recursion Schemes, Part 4½_ Better Living Through Base Functors.pdf --- https://blog.sumtypeofway.com/posts/recursion-schemes-part-4-point-5.html
  6. adventures in uncertainty_ Recursion Schemes, Part V_ Hello, Hylomorphisms.pdf --- https://blog.sumtypeofway.com/posts/recursion-schemes-part-5.html

resource The Hitchhiker's Guide to Morphisms by Jonathan Brachthäuser, terse summaries of several construction and destruction morphisms --- guide-to-morphisms.pdf --- https://b-studios.de/assets/guide-to-morphisms.pdf

resource Recursion Schemes for Mathematicians by Iago Leal de Freitas, an explanation of catamorphisms, anamorphisms and hylomorphisms with no prerequisite knowledge but a little category theory --- Recursion Schemes for Mathematicians _ Iago Leal de Freitas.pdf --- https://iagoleal.com/posts/recursion-schemes/

resource F-Algebras by Bartosz Milewski, heavier on the category theory --- F-Algebras _   Bartosz Milewski's Programming Cafe.pdf --- https://bartoszmilewski.com/2017/02/28/f-algebras/

recursion› schemes let you factor recursion out of recursive algorithms. use a algebraic data ‹type to specify how to recurse, write a single layer of the recursive algorithm without using recursion, and out pops the recursive algorithm. the rigid structure of recursion› schemes makes it easier to reason about the resulting recursive algorithm

example foldr is the catamorphism for linked lists and unfold is their anamorphism, both recursion› schemes

example the lambda-calculus › church encoding encodes algebraic data ‹types as their own catamorphism

example divide and conquer algorithms lend themselves well to hylomorphisms (an anamorphism followed by a catamorphism)

one might say that recursion› schemes are to direct recursion what structured control-flow is to goto --- https://iagoleal.com/posts/recursion-schemes/ and https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html