Functional programming with bananas, lenses, envelopes and barbed wire [pdf] (1991)

No open source code base I can point to right now unfortunately.

But this is fun stuff, so I couldn't help creating a simple gist to demonstrate the concept: https://gist.github.com/sebastiaanvisser/cd6ee46356e3ecc8945...

The trick is to keep all the combinators specific to your data type. In Haskell you can derive your functor (and applicative/foldable/traversable) and have a single cata to rule them all. In Rust you build them specifically for every datatype. Less neat, but could still be totally worth it!

The .NET RX Observable streams where designed by Erik Meijer the author of this paper. The GOF book came up with the "Observer" pattern, but failed to spot and exploit the duality with iterators. RX and LINQ both take ideas from functional programming.

While the first author of this paper went on to be heavily involved in Microsoft's Reactive Extensions (among many other things), I think it's better to think of it as making common recursive patterns explicit and introducing abstraction for those patterns. For example, a common use of goto is to run a certain block of code until a condition becomes true. This is abstracted into a pattern called "while" which takes a condition and a block of code to run. A common use of recursion is the reduce (also called fold) operation which, in the case of a list, computes a single value from a list by combining all of the values of the list with a binary function. As an example, this code sums all of the values in an integer list:

  def sum(xs):
    if xs == []:
      return 0
    else:
      x = xs.pop(0)
       return x + sum(xs)

This sort of reduction operation is very broadly useful, so it has been abstracted in frameworks like MapReduce as well as library functions like functools.reduce (https://docs.python.org/3/library/functools.html#functools.r...). Recursion schemes build on explicit reduce functions by being strongly typed (which, in addition to reducing bugs, enables a something like a super-powered visitor pattern), very orthogonal (which reduce redundancy and code duplication as a user of the abstraction), and very general (which let you solve a lot of problems with the same small set of programming tools without needing to remember special cases). In particular, the way that they look at data structures lets you interleave the recursion across nested data structures in a way that would be a huge pain in the butt with e.g. Python's __iter__ interface. There are some other nifty things that the approach brings to the table as well, but I think those are the major wins from the perspective of someone not already interested in strongly-typed functional programming.

While I covered the case of things that are sort of like reduce (called catamorphisms in the language of recursion schemes), this paper also has analogous abstractions for things that are sort of like itertools.accumulate (https://docs.python.org/3/library/itertools.html#itertools.a..., called anamorphisms in recursion schemes), as well as combinations thereof (called hylomorphisms). They all use a relatively small number of building blocks and combine in a quite beautiful and useful way, but it's hard to describe precisely without leaning quite heavily on the language of strongly-typed functional programming.

I can't speak to Observable streams but one of the nicest things about recursion schemes is that they are guaranteed to terminate.

Thanks for explaining!

Minor nitpick, you don't get `fold` as written for free. You would still need to provide a function `toTreeF :: tree -> tree'` then compose that with `cata`, which you do get for free: `fold t alg = cata alg (toTreeF t)`.

But lenses as functional references are very common in the Haskell world, whereas the only place I've heard of anamorphisms (unfolds) being referred to as lenses is in this paper. It also confused me quite a bit when I first ran into it, but the name just comes from the notation used in the paper. It is super hard to google for other references to anamorphisms being called lenses for short though because of yet another unrelated concept: https://en.wikipedia.org/wiki/Anamorphic_format

Explicit getter-setter lenses and profunctor lenses are not quite the same thing, although they happen to be equivalent in Haskell. For example: the getter-setter encoding only works when you have diagonals (~ copying data).