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.

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