Peeling the Banana: Recursion Schemes from First Principles - Zainab Ali

34:22 7649 views 96% Published 4 years ago

This presentation was given at Lambda World 2017 by Zainab Ali.

Follow:
-https://www.twitter.com/47deg
-https://www.twitter.com/lambda_world
-https://www.twitter.com/_zainabali_

Visit:
-https://www.47deg.com/events for more details
-http://www.lambda.world
___

Recursion is at the heart of every functional programmer's toolkit, but with it comes a lot of boilerplate. In the early 1990s, the seminal paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (Erik Meijer, M.M. Fokkinga, and Ross Paterson) introduced a little-known technique known as recursion schemes. This technique makes recursion generic, removing much of the boilerplate associated with it, and cleanly separating business logic from recursive traversal. It paved the way to many different schemes, each for their own kind of recursive traversal.

This talk explores the technique of recursion schemes and how to use it. We start with primitive recursion, briefly diving into folds, before deriving the catamorphism, a specific recursion schema for the right fold. We shall see that there is a rich zoo of recursion schemes for different types of folds, unfolds and more.



Watch on YouTube





Lambda World 2017


Lambda World 2017

From 26/10/2017 to 27/10/2017 in Cádiz, Spain