Recursive Combinators

using System;
using System.Collections.Generic;

class Flattening {

    // This Tree type will be used in the mirror example.

    class Tree<T> {
	public T Value { get; private set; }
	public Tree<T> Left { get; private set; }
	public Tree<T> Right { get; private set; }

	public Tree(T value, Tree<T> left, Tree<T> right) {
	    Value = value;
	    Left = left;
	    Right = right;
	}
    }


    static void Main(string[] args) {
	var makeOdd = Tail((int x) => x / 2, x => x % 2 == 1);

	var factorial = Linear(
	    (int n) => m => n * m,
	    n => n - 1,
	    n => n == 0,
	    zero => 1);

	Console.WriteLine("remove the 2's from 24 and you get {0}",
	    makeOdd(24));
	Console.WriteLine("7! = {0}", factorial(7));

	// reverses a binary tree, maintaining structure
	var mirror = Binary<Tree<int>, Tree<int>>(
	    t => {
		var val = t.Value;
		return (l, r) => new Tree<int>(val, r, l);
	    },
	    t => t.Left,
	    t => t.Right,
	    t => t == null,
	    nullT => null);

	// Draws a binary tree.
	var draw = Binary<Tree<int>, string>(
	    t => (l, r) => "<" + l + t.Value + r + ">",
	    t => t.Left,
	    t => t.Right,
	    t => t == null,
	    t => "");

	Func<int, Tree<int>, Tree<int>, Tree<int>> mk
	    = (n, l, r) => new Tree<int>(n, l, r);

	var tree = mk(4,
	    mk(1, mk(0, null, null),
	    mk(2, null, null)), mk(5, null, mk(7, null, null)));

	Console.WriteLine("Unmirrored: {0}", draw(tree));
	Console.WriteLine("Mirrored:   {0}", draw(mirror(tree)));
    }

    // For each of our combinators, we define the behavior of the
    // function f (the returned function) in terms of the argument
    // functions.

    // Tail recursion:
    // f(x) | bc(x)     = x
    //      | otherwise = f(g(x))
    static Func<T, T> Tail<T>(Func<T, T> g, Func<T, bool> bc) {
	return (T x) => {
	    while (!bc(x)) {
		x = g(x);
	    }
	    return x;
	};
    }


    // For linear recursion, we could write g(x, f(h(x))) instead
    // of g(x)(f(h(x))), but the latter form lets the value of x
    // be garbage collected sooner. We could also write
    // g(ha(x), f(hr(x))) to allow the garbage collection of x --
    // which would make our mirror definition in Main nicer but
    // some other code less nice.


    // Linear recursion:
    // f(x) | bc(x)     = b(x)
    //      | otherwise = g(x)(f(h(x)))
    static Func<TIn, TOut> Linear<TIn, TOut>(
	Func<TIn, Func<TOut, TOut>> g, Func<TIn, TIn> h,
	Func<TIn, bool> bc, Func<TIn, TOut> b) {

	return (TIn x) => {
	    var stack = new Stack<Func<TOut, TOut>>();

	    while (!bc(x)) {
		stack.Push(g(x));
		x = h(x);
	    }
	    TOut y = b(x);
	    while (stack.Count != 0) {
		y = stack.Pop()(y);
	    }
	    return y;
	};
    }


    // Binary recursion is brutal. The function 'computer' makes an
    // action that takes an x and places the return value f(x) into
    // the variable y, without any net modification to the stack. 


    // Binary recursion:
    // f(x) | bc(x)     = b(x)
    //      | otherwise = g(x)(f(hl(x)),f(hr(x)))
    static Func<TIn, TOut> Binary<TIn, TOut>(
	Func<TIn, Func<TOut, TOut, TOut>> g, Func<TIn, TIn> hl,
	Func<TIn, TIn> hr, Func<TIn, bool> bc, Func<TIn, TOut> b) {

	return (TIn x) => {
	    TOut y = default(TOut);
	    var stack = new Stack<Action>();

	    Func<TIn, Action> computer = null;
	    computer = (TIn value) => () => {
		if (bc(value)) {
		    y = b(value);
		}
		else {
		    var combiner = g(value);
		    var left = hl(value);
		    var right = hr(value);
		    stack.Push(() => {
			var leftOutput = y;
			stack.Push(() => { y = combiner(leftOutput, y); });
			stack.Push(computer(right));
		    });
		    stack.Push(computer(left));
		}
	    };

	    stack.Push(computer(x));

	    while (stack.Count != 0) {
		stack.Pop()();
	    }
	    return y;
	};
    }
}