Zainab Ali

Peeling the Banana: Recursion Schemes from First Principles

All Things Functional

Peeling the Banana: Recursion Schemes from First Principles

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'll use category theory to derive primitive recursion, briefly diving into folds, before deriving the catamorphism, a specific recursion scheme for the right fold. We shall see that there is a rich zoo of recursion schemes for different types of folds, unfolds and more.

Talk objectives:

To give attendees an appreciation of the mathematics behind functional programming, in particular category theory, a thirst for using unconventional techniques to solve problems and an understanding of recursion schemes.

Talk audience:

Anyone interested in functional programming, the concepts underlying recursion and reducing boilerplate through generic programming.

About Zainab

Zainab is a functional programmer who is interested in everything. By day, she codes in Scala, and by night she codes in Scala, Rust, Haskell, Idris and pretty much any other language which catches her eye. Zainab is always on the lookout for any interesting open source projects. When she is not absorbed in coding, she likes hiking in the English countryside, far away from civilization, yet close enough to a cup of tea.

Github: zainab-ali

Twitter: @_zainabali

Back to conference page