Hacker News Reader

Comment by zachrose | Hacker News Reader

I believe the fancy math word for this “building up” of a value from a “smaller” initial condition is “anamorphism.”

Most interview-style programming problems are catamorphisms, or “boiling down” an initial condition to “smaller” result. (For example, summing the numbers in a string.)

In, say, JavaScript, knowing that you’re implementing a catamorphism usually (or always?) means that you can convert your input to an array and use the aptly-named reduce method to write a reducer that works on one piece at a time to build your result. (Sometimes your reducer needs a sophisticated memo object to keep track of details, like whether you’re in the middle of multiple digits.)

If you know you’ll be dealing with an anamorphism in JavaScript, your two options are a while loop (for an imperative flavor) or a generator (for a functional flavor).

View on HN

Catamorphisms are more general than reducing an array, e.g. evaluating down a tree structure (or any other recursive datastructure) is also a catamorphism.

Indeed. Reduce is a catamorphism, but not all catamorphisms are reduce. On the other hand, it's generally underappreciated how useful unfold (ana) and refold (hylo) are, even if we're just talking about lists.

Recursion schemes are the FP way of doing the Visitor Pattern. You can get annotations with (coelgot, zygo) which are super useful for tupecheckers, allow the fold to accumulate effects (gana, gcata), or even look into the future of the recursion (futu).

They do get a bit much at times though, since you can compose them easily. Zygohistoprepromorphisms are one example of this.

True, but isn’t it also true that a catamorphism on any other data structure still operates one piece at a time? If so, I think this would imply that you _could_ concert your tree or whatever to an array and still get your result with Array#reduce. (Not saying you should, just speculating that it might be always possible.)

> True, but isn’t it also true that a catamorphism on any other data structure still operates one piece at a time? If so, I think this would imply that you _could_ concert your tree or whatever to an array and still get your result with Array#reduce.

No, the catamorphism operates on one part of the structure but that part of the structure is not necessarily (head, tail) like it is for reduce - rather it's the "base" shape of the recursive data structure.

E.g. it's easy to write a catamorphism on a tree that finds the maximum number of children any one node has. But if you flatten the tree into an array then it's obviously impossible to recover that information.

Reply on news.ycombinator.com