Recursion schemes in TS

recursion.ts

import { Functor1 } from "fp-ts/lib/Functor";
import { URIS, Kind } from "fp-ts/lib/HKT";
import { pipeable } from "fp-ts/lib/pipeable";
import { flow } from "fp-ts/lib/function";

interface Algebra<F extends URIS, A> {
  (_: Kind<F, A>): A;
}

interface Fix<F extends URIS> {
  unfix: Kind<F, Fix<F>>;
}

const fix = <F extends URIS>(unfix: Kind<F, Fix<F>>): Fix<F> => ({
  unfix
});

const unFix = <F extends URIS>(_: Fix<F>): Kind<F, Fix<F>> => _.unfix;

type ConstF = {
  _tag: "ConstF";
  d: number;
};
type VarF = {
  _tag: "VarF";
  s: string;
};
type TimesF<R> = {
  _tag: "TimesF";
  l: R;
  r: R;
};
type PlusF<R> = {
  _tag: "PlusF";
  l: R;
  r: R;
};

type ExprF<R> = ConstF | VarF | TimesF<R> | PlusF<R>;

const URI = "RS/ExprF";
type URI = typeof URI;

declare module "fp-ts/lib/HKT" {
  interface URItoKind<A> {
    [URI]: ExprF<A>;
  }
}

type Ex = Fix<URI>;

const cataT = <F extends URIS>(F: Functor1<F>, FP = pipeable(F)) => <A>(
  alg: Algebra<F, A>
): ((_: Fix<F>) => A) => flow(unFix, FP.map(cataT(F)(alg)), alg);

const functor: Functor1<URI> = {
  URI,
  map: (fa, f) => {
    switch (fa._tag) {
      case "ConstF":
        return {
          _tag: "ConstF",
          d: fa.d
        };
      case "VarF":
        return {
          _tag: "VarF",
          s: fa.s
        };
      case "PlusF":
        return {
          _tag: "PlusF",
          l: f(fa.l),
          r: f(fa.r)
        };
      case "TimesF":
        return {
          _tag: "TimesF",
          l: f(fa.l),
          r: f(fa.r)
        };
    }
  }
};

const cata = cataT(functor);

const prettyFalg: Algebra<URI, string> = (_) => {
  switch (_._tag) {
    case "ConstF":
      return `${_.d}`;
    case "PlusF":
      return `${_.l} + ${_.r}`;
    case "TimesF":
      return `${_.l} * ${_.r}`;
    case "VarF":
      return _.s;
  }
};

const v = (s: string): Ex =>
  fix({
    _tag: "VarF",
    s
  });

const num = (d: number): Ex =>
  fix({
    _tag: "ConstF",
    d
  });

const mul = (l: Ex, r: Ex): Ex =>
  fix({
    _tag: "TimesF",
    l,
    r
  });

const add = (l: Ex, r: Ex): Ex =>
  fix({
    _tag: "PlusF",
    l,
    r
  });

const ex = add(mul(v("x"), v("x")), add(mul(num(3), v("x")), num(4)));

console.log(cata(prettyFalg)(ex)); // x * x + 3 * x + 4