First part of Wadler's "Monads for funtional programming" translated to TypeScript

monads.ts

// Monads for functional programming in TypeScript

// Here's a basic evaluator
type Term = 
    | { tag: 'Con', n: number } 
    | { tag: 'Div', arg1: Term, arg2: Term }

const con = (n: number): Term => ({ tag: 'Con', n });
const div = (arg1: Term, arg2: Term): Term => ({ tag: 'Div', arg1, arg2 });

function evalTerm(t: Term): number {
    switch (t.tag) {
        case 'Con':
            return t.n;
        case 'Div':
            return evalTerm(t.arg1) / evalTerm(t.arg2);
    }
}

// 20 / (10 / 2) = 4
const ex1 = evalTerm(
    div(
        con(20),
         div(
            con(10), 
            con(2))))
console.log(ex1 === 4);

// Say it is desired to add error checking, so that divide by zero returns
// a sensible error message. In an impure language, this is easily achieved with the
// use of exceptions. But we have to do this:

type WithException<A> = { tag: 'Raise', error: string } | { tag: 'Return', a: A };

function raise<A>(error: string): WithException<A> { return ({ tag: 'Raise', error }); }
function ret<A>(a: A): WithException<A> { return ({ tag: 'Return', a }) }

// It is straightforward, but tedious, to adapt the evaluator to this representation
function evalWithException(t: Term): WithException<number> {
    switch (t.tag) {
        case 'Con':
            return ret(t.n);
        case 'Div':
            const a1 = evalWithException(t.arg1);
            switch (a1.tag) {
                case 'Raise':
                    return a1; // re-raise first arg
                case 'Return':
                    const a2 = evalWithException(t.arg2);
                    switch (a2.tag) {
                        case 'Raise':
                            return a2; // re-raise second arg
                        case 'Return':
                            if (a2.a === 0) {
                                return raise("divide by zero");
                            } else {
                                return ret(a1.a / a2.a);
                            }
                    }
                
            }
    }
}

// 20 / (10 / 2) = 4
const ex2 = evalWithException(
    div(
        con(20),
         div(
            con(10), 
            con(2))))
console.log(JSON.stringify(ex2) === JSON.stringify(ret(4)));

// 20 / (10 / 0) = divide by zero
const ex3 = evalWithException(
    div(
        con(20),
         div(
            con(10), 
            con(0))));
console.log(JSON.stringify(ex3) === JSON.stringify(raise("divide by zero")));

// Forgetting errors for the moment, say it is desired to count the number of divisions performed during evaluation. 
// In an impure language, this is easily achieved by the use of state. But we can:

// Accepts _initial_ state and returns _final_ state and computation result
type WithState<S, A> = (state: S) => readonly [A, S];

function evalWithState(t: Term): WithState<number, number> {
    switch (t.tag) {
        case 'Con':
            return (s) => [t.n, s];
        case 'Div':
            return (s) => {
                const [n1, s1] = evalWithState(t.arg1)(s);
                const [n2, s2] = evalWithState(t.arg2)(s);
                return [n1 / n2, 1 + s1 + s2];
            } 
    }
}

// 20 / (10 / 2) = 4 w/ 2 divisions
const ex4 = evalWithState(
    div(
        con(20),
         div(
            con(10), 
            con(2))))
const [answer, numDivisions] = ex4(0);
console.log(answer === 4);
console.log(numDivisions === 2);

// Finally, say it is desired to display a trace of execution. In an impure language,
// this is easily done by inserting output commands at appropriate points.
// In a pure language, output may be mimicked 
// by introducing a type to represent computations that generate output.

type WithOutput<A> = readonly [string, A];

function evalWithOutput(t: Term): WithOutput<number> {
    switch (t.tag) {
        case 'Con':
            return ["", t.n];
        case 'Div':
            const [o1, n1] = evalWithOutput(t.arg1);
            const [o2, n2] = evalWithOutput(t.arg2);
            const result = n1 / n2;
            const line = ` ${n1} / ${n2} = ${result};`;
            return [o1 + o2 + line, n1 / n2];
            
    }
}

// 20 / (10 / 2) = 4 
const ex5 = evalWithOutput(
    div(
        con(20),
         div(
            con(10), 
            con(2))))
const [output, ans] = ex5;
console.log(ans === 4);
console.log(output === " 10 / 2 = 5; 20 / 5 = 4;");

// 2.5 A monadic evaluator

// Each of the variations on the interpreter has a similar structure, which may be
// abstracted to yield the notion of a monad.

// Observe:
type OriginalEvaluator  = (t: Term) => number;
type ExceptionEvaluator = (t: Term) => WithException<number>;
type StateEvaluator     = (t: Term) => WithState<number, number>;
type OutputEvaluator    = (t: Term) => WithOutput<number>;

// Or generically for any M: type Evaluator = (t: Term) => M<number>
// (Note: we cannot express this type in TS due to lack of higher-kinded types,
// in other words: type variables cannot be _applied_ in type signatures like M<number>)

// If we wanted to generically write a single "evalM" fn for all these cases what would we need? 

// Recalling the `Con` case of all previous evaluators we would need
// function pure(t: Term): M<Term> 

// and then we need a way to take the nested responses of evalM in the `Div` case and 
// combine them 
// function bind(a: M<Term>, f: (t: Term) => M<number>): M<number> 

// A Monad is an instance of each of these functions for a given type

// What I would very much like to write here is:
// type Monad<M, A> = {
//   pure: (a: A) => M<A>;
//   bind: <B>(ma: M<A>, f: (a: A) => M<B>) => M<B>
// }
// but because of the afore-mentioned lack of higher-kinded types here are all our examples 
// individually, but they are all exactly the same with different M

type ExceptionMonad<A> = {
    pure: (a: A) => WithException<A>;
    bind: <B>(
        ma: WithException<A>, 
        f: (a: A) => WithException<B>
    ) => WithException<B>;
}

type StateMonad<S,A> = {
    pure: (a: A) => WithState<S,A>;
    bind: <B>(
        ma: WithState<S,A>, 
        f: (a: A) => WithState<S,B>
    ) => WithState<S,B>;
}

type OutputMonad<A> = {
    pure: (a: A) => WithOutput<A>;
    bind: <B>(
        ma: WithOutput<A>, 
        f: (a: A) => WithOutput<B>
    ) => WithOutput<B>;
}

// and their concrete implementations:

const ExceptionMonad = function<A>(): ExceptionMonad<A> {
    return {
        pure: (a) => ret(a),
        bind: (ma, f) => {
            switch (ma.tag) {
                case 'Raise':
                    return ma;
                case 'Return':
                    return f(ma.a);
            }
        }
    }
};

const StateMonad = function<S, A>(): StateMonad<S, A> {
    return {
        pure: (a) => (s) => [a, s],
        bind: (ma, f) => {
            return (s0) => {
                const [a, s1] = ma(s0);
                const [b, s2] = f(a)(s1);
                return [b, s2];
            }
        }
    }
}

function puts<S>(f: (s: S) => S): WithState<S, undefined> {
    return (s) => [undefined, f(s)];
}

const OutputMonad = function<A>(): OutputMonad<A> {
    return {
        pure: (a) => ["", a],
        bind: (ma, f) => {
            const [o1, a] = ma;
            const [o2, b] = f(a);
            return [o1 + o2, b];
        }
    }
}

function write(s: string): WithOutput<undefined> {
    return [s, undefined];
}

// Now we are able to write all three evaluators with a single function
// We also now pass in a side-effecting action (a, b) => M<undefined>

function evalM(m: ExceptionMonad<number>, t: Term, onDiv: (a: number, b: number) => WithException<undefined>): WithException<number>;
function evalM(m: StateMonad<number, number>, t: Term, onDiv: (a: number, b: number) => WithState<number, undefined>): WithState<number, number>;
function evalM(m: OutputMonad<number>, t: Term, onDiv: (a: number, b: number) => WithOutput<undefined>): WithOutput<number>;
function evalM(m: any, t: Term, onDiv: any): any {
    switch (t.tag) {
        case 'Con':
            return m.pure(t.n);
        case 'Div':
            // Here we get some sense of why this is called "bind"
            return m.bind(
                evalM(m, t.arg1, onDiv), // action -> eval arg1
                (a: number) => m.bind( // result -> a
                    evalM(m, t.arg2, onDiv), // action -> eval arg2
                    (b: number) => m.bind( // result -> b
                        onDiv(a, b),       // action -> onDiv(a, b)
                        () => m.pure(a / b) // result is ignored (undefined)
                    )
                )
            )
    }
}

const t6 = div(con(20), div(con(10), con(0)));
const ex6 = evalM(
    ExceptionMonad<number>(),
    t6,
    (_a, b) => b == 0 ? raise("divide by zero") : ret(undefined)
);

const validTerm = div(con(20), div(con(10), con(5)));
const ex7 = evalM(
    StateMonad<number, number>(),
    validTerm,
    () => puts(i => i + 1)
)

const ex8 = evalM(
    OutputMonad<number>(),
    validTerm,
    (a, b) => write(` ${a} / ${b} = ${a / b};`)
)