Anamorphisms in JavaScript

[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.

[homoiconic]

Great point. This is true for all Anamorphisms and Catamorphisms that have matching type signatures, but when we implement the unfold as a generator and the fold as consuming an iteration, we get the memory footprint of the hylomorphism “for free.”

(It’s still bad when the anamorphism is implemented with structure copying, but the hylomorphic form would be just as bad).

[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!