u/ocharlesin r/haskell • Recommends
Recursion Schemes @ London Haskell User Group video, March 2013 - Speaker: Tim Williams
0:00 / 0:00
#recursionschemes#haskell#catamorphism
Recursion Schemes
London Haskell
1.5K subscribers • 7 videos on Hallway
- Recommended by 2 people: 1 in engineering communities and 1 curated list.
- Presented by Tim Williams
Advanced. Deep dive for people who know the field.
9.4K views11 years ago2 recommendations
Programming languagesComputer scienceHaskellFunctional programmingAlgorithms
Tim Williams explains the theory and practice of recursion schemes in Haskell, demonstrating how to model recursive types as fixed points of functors.
Speaker: Tim Williams. London Haskell user group. 27th March 2013. The theory and practice of various recursion schemes applied to real world problems. Demonstrating compositional data-types and data-type generic programs by modelling recursive types as fixed points of functors. Code starts with simple list examples and moves quickly on to more problematic topics, such as program analysis, optimisation, memoization, templating and more.Why it's here
2 people recommend thisWhat people say. Highly recommended as one of the best and most comprehensive video introductions to recursion schemes in Haskell.
programming-talkscurated list on GitHubRecommends
Under “Java & Android”
Recursion Schemes 01:50:29 by **Tim Williams** (2014)
u/dolotoin r/haskell • Mentions
On “What are the hardest/most interesting, perhaps little known, but useful concepts that you know? I'm trying to broaden my horizons, but it's hard to google for "things I don't understand" so I'd appreciate any help.”
…all recursions schemes.
- You can say that the fusion laws^(aka, adjoint fold laws) are based on how those squares compose.
- `elgot` Algebras correspond to compositions of `cata; apo`, iirc.
King: http://comonad.com/reader/2009/recursion-schemes/
Slides: https://github.com/willtim/recursion-schemes/raw/master/slides-final.pdf
Video: link to this video
Similarly, the notion of _Promorphisms_, `prepro, postpro`, involve further concepts like _Natural Transformations_ (`f a -> g a`), namely, Natural _Endomorphisms_ (`f a -> f a`). As such they naturally compose verticallyNatComp, while composing promorphisms schemes happens somewhat _horizontally_, in the same context.
If you want an…
u/primarydavein r/compsci • Mentions
On “Unique and Useful Non-Obvious Properties and Tricks with Higher Order Functions”
Although this is probably not exactly what you're referring to, your question reminds me of "recursion schemes" -- a way of categorizing different types of recursive functions. Here's an amazing talk about the subject: link to this video . The talk is presented in Haskell, but I think the ideas behind the different recursion schemes (e.g. catamorphism, anamorphism, etc.) can be implemented in any language.
Here are some more references on the subject:
http://blog.sumtypeofway.com/an-introduction-to-recursion-schemes/
http://stackoverflow.com/questions/6941904/recursion-schemes-for-dummies
https://patternsinfp.wordpress.com/2010/09/18/story-so-far/
Field Guide: http://comonad.com/reader/2009/recurs…
u/darkroom--in r/haskell • Mentions
On “What happens when you apply length to an infinite list.”
Thanks man, and if you want to learn more on this subject check this talk out, I found it to be very enlightening: link to this video
Recursion schemes are the future of functional programming.