Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Recursion schemes in 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.