Functional programming with bananas, lenses, envelopes and barbed wire [pdf] (1991)(ris.utwente.nl)
ris.utwente.nl
Functional programming with bananas, lenses, envelopes and barbed wire [pdf] (1991)
https://ris.utwente.nl/ws/portalfiles/portal/6142049/meijer91functional.pdf
29 comments
Is there any example code you'd be able to point to? I'd have thought this would be difficult without something like haskell's Fix
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!
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!
This is great, thanks for taking the time to flesh it out
This is a great paper, but I found it to be very challenging to read when I first ran into it, even though I had some experience programming in Haskell. As a one sentence pitch, this paper is to recursion what if and while are to goto. For a more detailed intro to the concepts see: https://blog.sumtypeofway.com/posts/introduction-to-recursio... If you are comfortable with Haskell, it should be relatively accessible. If you aren’t, but want a bit more flavor than my one sentence, the intro section in that blog post is still worth a read.
I also remember struggling with this paper quite a bit at first. This is how I would explain catamorphisms to past me:
Suppose you have a recursive `tree` data structure, and another one `tree' x` where `tree' x` is just like `tree`, but with recursive occurrences of `tree` replaced with type x. So maybe something like, in Haskell-ish syntax:
Now the beauty of recursion schemes is that whenever `tree'` is a functor, you can get `tree` (as a fixpoint: `tree = tree' tree`) and `fold` for free (generally called `cata`), which can be seen by rewriting `fold` above using just `map`.
This skips a fair amount of boilerplate code you no longer have to touch when modifying recursive types.
Suppose you have a recursive `tree` data structure, and another one `tree' x` where `tree' x` is just like `tree`, but with recursive occurrences of `tree` replaced with type x. So maybe something like, in Haskell-ish syntax:
type tree = Leaf int | Node tree tree
type tree' x = Leaf int | Node x x
fold: tree -> (tree' x -> x) -> x
Now the beauty of recursion schemes is that whenever `tree'` is a functor, you can get `tree` (as a fixpoint: `tree = tree' tree`) and `fold` for free (generally called `cata`), which can be seen by rewriting `fold` above using just `map`.
This skips a fair amount of boilerplate code you no longer have to touch when modifying recursive types.
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)`.
Isn’t toTreeF just ‘out’ as in ‘newtype Fix f = In { out :: f (Fix f) }’ ?
Sorry my last comment was sort of wrong because I neglected to mention Fix (I'm going to claim that I was tired :) ).
They say a picture is worth a thousand words, so hopefully this clears up the difference betwene `out` and `toTreeF`:
They say a picture is worth a thousand words, so hopefully this clears up the difference betwene `out` and `toTreeF`:
-- | Our basic binary tree type
data Tree a = Leaf a | Node (Tree a) (Tree a)
-- | A pattern functor for our binary tree
data TreeF a r = LeafF a | NodeF r r
-- | The fixed point of 'f'.
newtype Fix f = Fix { unfix :: f (Fix f) }
-- | Given an F-Algebra on 'f' we have a catamorphism on 'Fix f'
cata :: Functor f => Algebra f a -> Fix f -> a
cata alg fix = alg $ fmap (cata alg) $ unfix fix
-- | We can sum the elements of a 'Fix (TreeF Int)' using 'cata'
sumTreeF :: Fix (TreeF Int) -> Int
sumTreeF = cata $ \case
LeafF i x -> x + i
NodeF l r x -> x + l + r
-- | To operate our binary tree we need to map from 'Tree a' to 'TreeF
-- a'.
toTreeF :: Tree a -> Fix (TreeF a)
toTreeF = \case
Leaf a -> LeafF a
Node l r -> NodeF (toTreeF l) (toTreeF r)
sumTree :: Tree Int -> Int
sumTree = sumTreeF . toTreeF
out :: Fix (TreeF a) -> TreeF a (Fix (TreeF a))
toTreeF -> Tree a -> Fix (TreeF a)If you're going to introduce a generic functor fixpoint then you'll probably want to define
type Tree a = Fix (TreeF a)
Yeah you could do that but now you have thrown away the recursive `Tree` type and are always working in `TreeF`. This is totally fine but is a different design decision from where we started.
Thanks for explaining!
If I understand the idea of the linked article correctly, I sometimes do a similar thing in Java by defining an Iterator that implements some sort of traversal over a recursive data structure, then can apply any operations to the returned items using a for loop, applying an anonymous function to all the items, etc.
From some of the sibling comments, seems like there is a strong connection between these recursion schemes and iterator strategies?
From some of the sibling comments, seems like there is a strong connection between these recursion schemes and iterator strategies?
so its structured recursion i.e. it reifies recursion into variables that than be passed around and modified instead of being implicit/embedded in the control flow?
if so how is that different from Observable streams or event emitters.
if so how is that different from Observable streams or event emitters.
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.
> The GOF book came up with the "Observer" pattern, but failed to spot and exploit the duality with iterators.
That's an interesting insight - thanks
That's an interesting insight - thanks
I can't speak to Observable streams but one of the nicest things about recursion schemes is that they are guaranteed to terminate.
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:
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.
def sum(xs):
if xs == []:
return 0
else:
x = xs.pop(0)
return x + sum(xs)
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.
Related books from the same school of thought (very tough!):
https://themattchan.com/docs/algprog.pdf
https://www4.di.uminho.pt/~jno/ps/pdbc.pdf
https://themattchan.com/docs/algprog.pdf
https://www4.di.uminho.pt/~jno/ps/pdbc.pdf
(1991) needed
I must note that the notion of lenses meant by this paper is very different from what is commonly called lenses nowadays. The modern definition of a lens is a function p a (f b) -> p s (f t) where p is a profunctor and f is a functor. It's the functional programming equivalent of getters and setters, but composable.
I must note that the notion of lenses meant by this paper is very different from what is commonly called lenses nowadays. The modern definition of a lens is a function p a (f b) -> p s (f t) where p is a profunctor and f is a functor. It's the functional programming equivalent of getters and setters, but composable.
> The modern definition of a lens is
When you say "the modern definition of X is Y", it tends to suggest that the older definition is no longer relevant or useful, even though I know that's not what you mean. So to clarify for everyone here, and to reinforce your first sentence, these are just unrelated concepts that happen to use the same term "lens". The lenses in this paper are still as relevant as ever, but these days they are usually called "unfold" (or "anamorphism" for the category theorists).
When you say "the modern definition of X is Y", it tends to suggest that the older definition is no longer relevant or useful, even though I know that's not what you mean. So to clarify for everyone here, and to reinforce your first sentence, these are just unrelated concepts that happen to use the same term "lens". The lenses in this paper are still as relevant as ever, but these days they are usually called "unfold" (or "anamorphism" for the category theorists).
That definition is just one of the many possible definitions. And one of the obscurer ones tbh. :)
It’s an abstract concept that you can implement in many different ways.
It’s an abstract concept that you can implement in many different ways.
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).
Let me drop it here.
http://worrydream.com/AlligatorEggs/
http://worrydream.com/AlligatorEggs/
Very interesting, important, and useful stuff. The only problem, IMO, is that they go nuts with the notation. (They call it "Squiggol"! https://en.wikipedia.org/wiki/Squiggol "Bird–Meertens formalism" )
I worked out §2 in Joy (a concatinative language) if anyone's interested: https://joypy.osdn.io/notebooks/Recursion_Combinators.html
(I kind sorta started to approach §3 & §4 in https://joypy.osdn.io/notebooks/Treestep.html but I didn't get far, I got sick of grokking squiggol.)
The underlying ideas are interesting, important, and useful but I feel like the effort is kind of wasted if they can't "bring it down the mountain" to the average programmer, eh?
I worked out §2 in Joy (a concatinative language) if anyone's interested: https://joypy.osdn.io/notebooks/Recursion_Combinators.html
(I kind sorta started to approach §3 & §4 in https://joypy.osdn.io/notebooks/Treestep.html but I didn't get far, I got sick of grokking squiggol.)
The underlying ideas are interesting, important, and useful but I feel like the effort is kind of wasted if they can't "bring it down the mountain" to the average programmer, eh?
Related:
Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire - https://news.ycombinator.com/item?id=24056901 - Aug 2020 (18 comments)
Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (1991) [pdf] - https://news.ycombinator.com/item?id=9080933 - Feb 2015 (2 comments)
Functional programming with bananas, lenses, envelopes and barbed wire - https://news.ycombinator.com/item?id=6195603 - Aug 2013 (1 comment)
Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire - https://news.ycombinator.com/item?id=24056901 - Aug 2020 (18 comments)
Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (1991) [pdf] - https://news.ycombinator.com/item?id=9080933 - Feb 2015 (2 comments)
Functional programming with bananas, lenses, envelopes and barbed wire - https://news.ycombinator.com/item?id=6195603 - Aug 2013 (1 comment)
I dream of a language which forbids unstructured recursion in favor of first class support for structured recursion. It's not like I'm employing recursion very much, but it would be a fun experiment.
[deleted]
The current project I’m working on in Rust has a big recursive data type with quite some branches and different instantiations of recursive positions. Box/Vec/Option etc.
By parametrizing the enum with a type variable and tying the knot with a type level fixed point combinator gives you back the originally intended data type. But now suddenly you can put annotations in the recursive positions as well, use generic cata/para and other higher level combinators. Fun and powerful stuff!
(The lack of HKT in Rust can be challenging, but it’s mostly easy to work around it)