Thread by @YuriyBogomolov

Welcome to the thrid installment of #monadicmonday!
Today we'll talk about quite complicated topic – recursion schemes. Hold tight, as the ride won't be easy.

First of all, I would like to stress that I'm still grokking this topic, so if you spot a mistake, please ping me back!

Recursion schemes were popularized by a classical paper by Mejer, Fokkinga and Petterson called "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire": eprints.eemcs.utwente.nl/7281/01/db-utw…

Recursion schemes are powerful way to generalize various recursion algorithms and make them composable and easy to reason about. Importance of recursion schemes for FP is of the same scale as importance of design patterns for OOP.

I would like to give credit to @importantshock for his magnificent work on blog "Adventures in Uncertainty", which is the most thorough and detailed intro to recursion schemes I know: blog.sumtypeofway.com

There is a plethora of recursion schemes, to name a few:
- catamorphism tears down a structure layer by layer – you may think of it as a general `fold` operation;
- anamorphism builds up a (recursive) structure layer by layer – you probably know it under `unfold` name;

- para- and apomorphisms fold and unfold a structure while preserving the information about original strcuture. This is achieved by passing along the recursive calls not only the computed value itself, but also the original term;

- histo- and futumorphisms are dual morphisms which give you an access to previous (histo-) and future (futu-) results of the recursive computations. They are tremendously useful for solving dynamic programming problems, as we will see later;

- and many more: chrono-, dyna-, prepro-, postpro-, and so on, even the almighty zygohistomorphic prepromorphism, which has become a semi-joke in the functional programmer community.

As usual, I will illustrate my examples in Haskell-esque type definitions and TypeScript with fp-ts library for the solution itself.
Let's solve a problem: given a desired amount N, and an infinite supply S = { S1, S2, .. , Sm} of coins, how many ways can we make the change?

BTW, this problem is described in great details in various tutorial blogs (like geeksforgeeks.org/coin-change-dp…), so I won't be describing the solution approach here. Instead I will show you how to implement it using a histomorphism.

Let's recall histomorphism type:
histo :: Functor f => CVAlgebra f a -> Fix f -> a,
where
CVAlgebra f a = f (Cofree f a) -> a - a course-of-value algebra,
Cofree f a = Cofree { attribute :: a, hole :: f (Cofree f a) } - cofree comonad
and
Fix f = f (Fix f) - fixpoint of functor f

Well, I guess these parts require some additional explanation.
Course-of-value algebra allows us to access the additional payload (attribute) of current recursive term, as well as fall deeper into it's hole.

Cofree comonad is a good topic for another Monadic Monday, so today I will just say that it's a way to "mark" a recursive term with an additional marker of type `a`.

A Fix is an Y-combinator (fixpoint combinator) on the type-level, so it just represents an infinite sequence of type application:
type Fix t = t (t (t (t (t ...))))
For example, a singly-linked list can be described like so:
type List a = Fix (L a)
data L a b = Nil | Cons a b

To begin solving our coin change problem, let's define our auxillary types in TypeScript. We will need:
- `Fix` type;
- `Nat` type to represent Peano numbers;
- `Cofree` type for our comonad;
- instance `NatC` for Cofree<Nat, a>;
- `CVAlgebra`;
- and `match` for pattern-matching:

Definition of `Nat` type requires some boilerplate in TypeScript, compared to terse Haskell counterpart:

data Nat a = Zero | Succ a
deriving Functor

The implementation of `histo` itself is identical to it's Haskell original from blog.sumtypeofway.com/recursion-sche…:

To begin with the solution, we'll need to define two helper which convert a common JavaScript `number` into `Nat` and vice versa:

Finally, let's define `change` function, which differs from the one @importantshock described in his article. My implementation stores not just a number of ways given amount can be exchanged – this information is insufficient for the correct solution.

@importantshock Instead, I store the exact solutions for each amount. This gives me an additional bonus: I can print not only a number of ways, but the ways themselves! That's why my `NatC` instance for `Cofree` was holding not just a number, but an array of number arrays.

@importantshock And here's the result of running `change` for amounts of 15, 20 and 42 cents. We get not only valid sum, but all possible ways of change, too:

Fun fact: some of RecSch are so abstract that even legendary @kmett struggles with a practical example:

https://twitter.com/kmett/status/318410115101380608