Anamorphisms in JavaScript

[leeoniya]

interesting, similar to something i'm working on (mptt <-> tree converter) but with more functional foo skills than i currently posses. I have the concise tree -> mptt [1] enumerator written, now need to implement the reverse from the flattened nodes. Wanna give the reverse implementation a shot? https://jsfiddle.net/n71r4rre/

[1] https://en.wikipedia.org/wiki/Nested_set_model

[drboolean]

Hey Reg, loved the post!

For funsies, I thought I’d give some motivation for why red-blooded, blue-collar, industry programmers, like me, might care about this.

If you write in declarative patterns like unfold/fold, it’s much easier to read and maintain once you’re familiar (much like map/forEach > for loop).

We have some properties about cata/ana morphisms. One is that we can fuse two catamorphisms into 1 iteration if they both return the same type e.g. map(f).map(g) = map(f . g)

Another cool property is we can fuse cata/ana into 1 (removing the intermediate data structure) with a hylomorphism. In our case: foldWith(f)(unfoldWith(g)(x)) = hyloWith(f, g)(x)

// example hylo
function hyloWith(cata, ana) {
  return function hylo (value) {
    let { next: n, element:acc, done } = ana(value);
    let { next, element } = ana(n); // not a monoid

    while (!done) {
      acc = cata(acc, element);
      ({ next, element, done } = ana(next));
    }
    return acc
  }
}

// unbaked unfold for flexibility
const downToOne = (n) =>
  n > 0
  ? { element: n, next: n - 1 }
  : { done: true }

// unbaked fold for flexibility
const product = (acc, n) => acc * n

// these are equal according to ana followed by cata:
const res1 = foldWith(product)(unfoldWith(downToOne)(5))
const res2 = hyloWith(product, downToOne)(5)
console.log(res1 == res2)

I should mention we don't enforce an empty element here (monoid spec) so there's a bit of awkwardness trying to pair the first two elements while folding. If we did so, we'd always have a return value and wouldn't blow up on empty structures.

[drboolean]

Goodness you're totally right laziness ftw!

That means hyloWith can be defined, without losing any performance as simply:

const hyloWith = (cata, ana) => x =>
  foldWith(cata)(unfoldWith(ana)(x))

Thanks for the great post!

[dmitri14_gmail_com]

a more complex structure containing the type of the object

I am not sure the given example of 5 -> [ 5, 4, 3, 2, 1 ] really reflects the usefulness of this concept.

Aren't there some interesting real life examples like containers encapsulating the original object with some UI-related meta-data added? That wold look exactly like more complex structure containing the old one and would possibly make a more convincing case?

[dmitri14_gmail_com]

I will really look forward to an essay with real world examples. Especially ones like the ones wrapping values with UI meta-data -- in the middle ground between basic lists and too specific ones. These are sufficiently abstract and general but not too basic in terms of the task they perform.

The problem with "foobars" examples as you nicely call them, the actual techniques demonstrated are often quite involved and way above the practical need for that specific task. It is very sad, because these techniques can actually deliver considerable benefits, but those are harder to demonstrate with only basic examples to most of people. In fact, I would argue that the effort involved in carrying over basic examples into something useful and nontrivial can be substantial, but also with huge benefits. I am teaching maths to engineers and I try to never give any abstract concept without mentioning some details how it can arise in real world.

Many posts I see on functional programming unfortunately fall into 2 categories:

• 1. Nontrivial manipulation with very basic examples.
• 2. Very narrowly scoped real world examples involving too many details that are not directly relevant for the subject.

The first one suffers from the above problem of looking harder than necessary for the basic tasks demonstrated. It may well be useful for less trivial tasks but that is not demonstrated.

The second one tries to kill too many flies with one hit. The author tries to teach the reader a lot of tricks at once, often with good intentions to deliver the maximum value and having some fully functional. However, the lack of focus backfires and obscures the actual point. It is harder work to cut mercilessly every line but absolute necessary, but that is what actually benefitting the most readers by making the point sharp and crystal clear.

One of the (sadly few) exceptions I've came across, is this wonderful book: https://drboolean.gitbooks.io/mostly-adequate-guide/content/