recursion schemes in flow

recursion-schemes-flow.js

// @flow
import type {Expr, ExprF} from "./ast.js";

const fmap = <A, B>(fn: A => B, expr: ExprF<A>): ExprF<B> => {
    switch (expr.type) {
        case "number":
            return expr;
        case "variable":
            return expr;
        case "apply":
            switch (expr.operation) {
                case "add":
                    return {
                        type: "apply",
                        operation: "add",
                        args: expr.args.map(fn),
                    };
                case "mul":
                    return {
                        type: "apply",
                        operation: "mul",
                        args: expr.args.map(fn),
                    };
                case "div":
                    return {
                        type: "apply",
                        operation: "div",
                        args: [fn(expr.args[0]), fn(expr.args[1])],
                    };
                default:
                    return (expr: empty);
            }
        default:
            return (expr: empty);
    }
}

const print = (expr: ExprF<string>): string => {
    switch (expr.type) {
        case "number":
            return expr.value;
        case "variable":
            return expr.name;
        case "apply":
            switch (expr.operation) {
                case "add":
                    return expr.args.join(" + ");
                case "mul":
                    return expr.args.join(" * ");
                case "div":
                    return expr.args.join(" / ");
                case "exp":
                    return expr.args.join(" ^ ");
                case "neg":
                    return `-${expr.args}`;
                case "eq":
                    return expr.args.join(" = ");
                default:
                    return (expr: empty);
            }
        default:
            return (expr: empty);
    }
}

const add = (a: number, b: number) => a + b;
const mul = (a: number, b: number) => a * b;
const zero = 0;
const one = 1;
const sum = (args: number[]) => args.reduce(add, zero);
const prod = (args: number[]) => args.reduce(mul, one);
const div = (num: number, den: number) => num / den;

const evaluate = (varDict: {[key: string]: number}) => (expr: ExprF<number>): number => {
    switch (expr.type) {
        case "number":
            return parseFloat(expr.value);
        case "variable":
            if (expr.name in varDict) {
                return varDict[expr.name];
            } else {
                throw new Error("variables are not supported");
            }
        case "apply":
            switch (expr.operation) {
                case "add":
                    return sum(expr.args);
                case "mul":
                    return prod(expr.args);
                case "div":
                    return div(expr.args[0], expr.args[1]);
                case "exp":
                    return Math.pow(expr.args[0], expr.args[1]);
                case "neg":
                    return -expr.args;
                case "eq":
                    // TODO: handle multiple values
                    return expr.args[0] === expr.args[1];
                default:
                    return (expr: empty);
            }
        default:
            return (expr: empty);
    }
}


const ast: Expr = {
    type: "apply",
    operation: "add",
    args: [
        {
            type: "number",
            value: "1.23",
        },
        {
            type: "variable",
            name: "x",
        }
    ]
};

// There isn't an easy way to pass ExprF as a generic parameter
// const cata = <A>(map, transform: ExprF<A> => A, expr: ExprF<Expr>): A => {
//     return transform(map(x => cata(map, transform, x), expr));
// }

const exprCata = <A>(transform: ExprF<A> => A, expr: ExprF<Expr>): A => {
    return transform(fmap(x => exprCata(transform, x), expr));
}

const result1: string = exprCata(print, ast);

const varDict = {
    "x": 10,
};

const result2: number = exprCata(evaluate(varDict), ast);

console.log(`result1 = ${result1}`);
console.log(`result2 = ${result2}`);