These patterns might seem abstract and obscure at first, but have proven tremendously powerful in practice to me.
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)
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:
type tree = Leaf int | Node tree tree
type tree' x = Leaf int | Node x x
Then one can easily write a `fold` over trees with type
fold: tree -> (tree' x -> x) -> x
where the second parameter (called an algebra) evaluates the result over a tree' assuming recursive subtrees have been replaced with the result of their evaluation (this is the key).
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.
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?
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.
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.
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).
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" )
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 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.
[+] [-] sfvisser|3 years ago|reply
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)
[+] [-] charleskinbote|3 years ago|reply
[+] [-] chas|3 years ago|reply
[+] [-] chombier|3 years ago|reply
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:
Then one can easily write a `fold` over trees with type where the second parameter (called an algebra) evaluates the result over a tree' assuming recursive subtrees have been replaced with the result of their evaluation (this is the key).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.
[+] [-] jimbokun|3 years ago|reply
From some of the sibling comments, seems like there is a strong connection between these recursion schemes and iterator strategies?
[+] [-] platz|3 years ago|reply
if so how is that different from Observable streams or event emitters.
[+] [-] nextos|3 years ago|reply
https://themattchan.com/docs/algprog.pdf
https://www4.di.uminho.pt/~jno/ps/pdbc.pdf
[+] [-] kccqzy|3 years ago|reply
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.
[+] [-] ebingdom|3 years ago|reply
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).
[+] [-] sfvisser|3 years ago|reply
It’s an abstract concept that you can implement in many different ways.
[+] [-] vishnugupta|3 years ago|reply
http://worrydream.com/AlligatorEggs/
[+] [-] carapace|3 years ago|reply
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?
[+] [-] dang|3 years ago|reply
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)
[+] [-] kelseyfrog|3 years ago|reply
[+] [-] unknown|3 years ago|reply
[deleted]