Hacker News Reader

Comment by aaron-santos | Hacker News Reader

Recursion shouldn't be difficult, but we write recursive programs using one tool: self-referential functions. That's like trying to write structured programs using one tool - goto.

Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire[1] pioneered generalized recursion schemes and influenced work in Haskell[2] and Scala[3]. It's great having the vocabulary to describe recursion and the tools to elegantly recurse, but anamorphism tends to shut down conversations faster than mentioning the m-word.

[1] - https://maartenfokkinga.github.io/utwente/mmf91m.pdf

[2] - https://hackage.haskell.org/package/recursion-schemes

[3] - https://github.com/slamdata/matryoshka

View on HN

> It's great having the vocabulary to describe recursion and the tools to elegantly recurse, but anamorphism tends to shut down conversations faster than mentioning the m-word.

Consider nudging the library authors to write a few words first [1]

[1] - https://hackage.haskell.org/package/recursion-schemes-5.0.2/...

I dunno.

I spent some time with that paper awhile back, implementing hylo-, ana-, and cata-morphisms in Python and Joy to be sure I was following along.

I loved it, but I was ultimately convinced that Category Theory et. al. isn't quite as useful for the working programmer as it should be.

What I did find useful is the treatment of recursion in the Joy language. http://www.kevinalbrecht.com/code/joy-mirror/j05cmp.html

Joy is interesting: I never programmed in it, but I had a lot of fun reading it and learning how it works from the documents.

To me it seems like it might be a kind of "silver bullet" for programming, due to a number of factors: simplicity and elegance, suitability for partial evaluation and super-compilation, and for parallelization.

I haven't tried to implement a large system in it yet though. If I get the time I hope to re-implement the Oberon OS using Joy.

> Bananas, Lenses, Envelopes and Barbed Wire

> It's great having the vocabulary...

Right...

Catamorphism, anamorphism, hylopmorphism, as opposed to something like fold/unfold, foldAndUnfold. There are of course, many more[1]. Meijer et al just chose a goofy name for their paper.

[1] - https://raw.githubusercontent.com/slamdata/matryoshka/master...

These are just combinators [1] with long names, right?

[1] https://www.npmjs.com/package/combinators-js

Nope. Example of recursion schemes:

You have a binary tree

    data Tree a = Branch (Tree a) (Tree a) | Leaf a

This is a recursive structure since a Tree can be made up of other Tree's. We can take a slice of the tree:

    data TreeNode a child = Branch child child | Leaf a
    data Fix f = F (f (Fix f))
    type Tree a = Fix (TreeNode a)

    sumTree :: Tree Int -> Int
    sumTree = cata algebra
      where
        algebra (Branch a b) = a + b
        algebra (Leaf a) = a

You might notice that we didn't do any recursion in sumTree because cata captures how to traverse the tree. Catamorphisms are the simplest recursion schemes, there are variants that keep track to our position in relation to the rest of the tree or memoize computations and so on.

I see. You might pass a combinator into a catamorphism, but the morphism itself isn't a combinator?

I agree a lot with the first point. Writing recursion algo using C/C++ or any other imperative language I've tried is like crawling through minefield, from one StackOverflow to another. I found that's because we've learned to write imperative programs from the entry problem to support all the cases.

I've changed my mind about recursion after I've learned to start writing the recursive algos backwards - starting from the ending condition and then moving to add support for basic recursion and adding real entry point at the end. That way instead of waiting for next segfault you try and implement each important step, one at a time. I've learned this thanks to how Erlang makes you write recursion (from "Learn you some Erlang" book).

In C design and problem/solution recognition is everything. That takes years of experimentation and working through test cases. Otherwise you can assign C to the minefield category and you will jump on another bandwagon.

My dream team composition is 3 15 year C programmers and a core lisper.

I didn't completely grok the white paper you linked. Is it basically suggesting that we remove the capability for arbitrary recursion and limit it to a set of recursive primitives (folds, filters, zips, etc)? And the motivation for this is comes from the idea that arbitrary recursion is as dangerous as go tos?

The big contribution of the paper is providing a vocabulary for describing generalized recursive patterns. The vocabulary Meijer et al chose (un)fortunately didn't stick; we now know these operators as catamorphism = fold/reduce, anamorphism = generators, hylomorphism = streams.

There's a fair bit of unexplored territory surrounding these operators, with some intriguing possibilities. For one, replacing arbitrary recursion with ana/cata/hylomorphisms lets you prove termination (or at least forward progress) of a fairly large subset of programs, including servers, GUIs, and event-driven programs! See eg. the research on total functional programming for this.

Also, folds and unfolds generalize to any algebraic data type, not just lists. Basically, a fold on lists means replacing the Nil constructor with a value and the Cons constructor with a binary operation. The same analogy holds for any ADT: given a sum-of-products types with N alternatives, the fold function for it is an N-argument function where each argument is a function from that alternative to the new accumulator value. This opens up the possibility of auto-generating fold functions from data type declarations, meaning the programmer would never have to write a loop or recursive function again, only specify the transformation at each stage of the recursion.

So, in other words, a language needs general recursion in order for library authors to implement map/fold/reduce etc. However, everyday programmers shouldn’t use general recursion, but rather stick to these library constructs (for the sake of correctness)?

By that definition a while loop is general recursion. Neither map, fold nor reduce require recursion to implement. All are either for or while loops and this is how the actual computer is going to execute them. Our Von Neumann machines execute lists of instructions and not functions. They are inherently stateful.

If-statements and all loops are all some form of "jump if zero/not zero" at the assembly level - so you could (and under the hood have to) implement all control structures used in higher level languages with conditional gotos, and probably even come up with a few more exotic control structures that might be better in rare situations.

But despite that flexibility we prefer to use the abstractions we're familiar with, as it makes it much easier to reason about the code (when you're using when you read a for loop or an if statement you know what it does, you don't have to spend extra time figuring out what a particular conditional goto construction does).

The idea is that plain recursion is like goto: a fundamental building block to the implementation, but not the abstraction level you want to work with if you can avoid it.

monad?

Reply on news.ycombinator.com