Lisp lectures IIa - Higher-order functions

I'm done with lesson IIa. That one was pretty hard. In Lisp it would be probably quite easy, but not in C#.
First thing, you need to switch from delegates to expression trees. There is no major problem to wrap delegates from my last article using Expression<>. Only problem is funtion folding. Consider this:

Expression<Func<double, double, double>> average = (y, x) => (x + y) / 2;
Expression<Func<double, double, double>> newGuess = 
  (guess, x) => average(guess, x / guess);

It will not work, compiler will say: "'average' is a 'variable' but is used like a 'method'". I believe that C# is missing some sugar here, does anyone know why ? And there is quick and ugly solution to the problem:

Expression<Func<double, double, double>> average = (y, x) => (x + y) / 2;
Expression<Func<double, double, double>> newGuess =
  (guess, x) =>  average.Compile().Invoke(guess, x / guess);

I implemented smart trick for expression folding. Let's have static helper class ExComp and this folding method Fold() with this signature:

public static TResult Fold<T1, TResult>(Expression<Func<T1, TResult>> expr, T1 param1)

Of course it could be implemented with Compile().Invoke(), but instead I'm post-processing the expression tree to get rid of method call and folding inner tree in place using InvocationExpression. So whole usage looks like this:

Expression<Func<double, double>> abs = (a) => a < 0 ? -a : a;
Expression<Func<double, double, double>> distance = 
    (a, b) => ExComp.Fold(abs, a - b);
double dist = distance.Process().Compile().Invoke(9,1);

And the tree after processing looks like this:

(a, b) => Invoke(a => IIF((a < 0), -a, a),(a - b))

Next we will hit problem with recursion, which works perfectly for delegates. This is factorial as simpler example of it :

Func<int, int> fact = null;
fact = (y) => y > 1 ? (y) * fact(y - 1) : 1;

Now serious troubles starting with expression trees. Emphasis on TREES. So, there is no good way how to turn expression tree into oriented graph of expressions. Only thing you could do is to use some external variable which has pointer back to root of the tree. For this I'm using similar trick as with folding above, fake method Self() and post-processing.

Back to the Lisp lecture. Now there is introduced idea of higher-order function. The function which creates and returns function, or could compose given function and return composition. Now when we have friendly expression folding, it's a piece of cake.

Expression<Func<double, double>> abs = (a) => a < 0 ? -a : a;
//folding function
Expression<Func<
    Expression<Func<double, double>>, //absFn
    Expression<Func<double, double, double>> //resultFn
    >> foldFn = ( absFn ) => ( a, b ) => ExComp.Fold(absFn, a - b);
//we are passing abs to get abs(a-b)
Expression<Func<double, double, double>> 
  distance = foldFn.Process().Compile().Invoke(abs);
double dist = distance.Compile().Invoke(9, 25);

So now we have foundation for completing square root function using reusable functions.

Expression<Func<double, double, double>> average = (a, b) => (a + b) / 2;
Expression<Func<double, double>> abs = (a) => a < 0 ? -a : a;
Expression<Func<double, double, double>> distance = (a, b) => ExComp.Fold(abs, a - b);

Expression<Func<
    Expression<Func<double, double, double>>, //stepFn
    Expression<Func<double, double, double>> //resultFn
>> avgDamp = (stepFn) =>
    (old, data) =>
        ExComp.Fold(average, old, ExComp.Fold(stepFn, old, data));

Expression<Func<
    Expression<Func<double, double>>, //testFn
    Expression<Func<double, double, double, bool>> //resultFn
>> test = (testFn) =>
    (guess, data, tolerance) =>
        ExComp.Fold(distance, ExComp.Fold(testFn, guess), data) < tolerance;

Expression<Func<double, double, double, double>> sqrtFixedPoint = null;

Expression<Func<
    Expression<Func<double, double, double, bool>>, //goodEnough
    Expression<Func<double, double, double>>, //newGuess
    Expression<Func<double, double, double, double>> //resultFn
>> fixedPoint =
   (goodEnough, newGuess) =>
        (oldGuess, data, tolerance) =>
                (ExComp.Fold(goodEnough, oldGuess, data, tolerance)) ? oldGuess
                    : ExComp.Self(sqrtFixedPoint,
                          ExComp.Fold(newGuess, oldGuess, data), data, tolerance);


Expression<Func<double, double>> square = a => a * a;
Expression<Func<double, double, double>> step = (old, data) => data / old;

sqrtFixedPoint =
    fixedPoint.Process().Compile().Invoke(
        test.Process().Compile().Invoke(square),
        avgDamp.Process().Compile().Invoke(step)
    );


Expression<Func<double, double>> squareRoot = 
  (x) => ExComp.Fold(sqrtFixedPoint, 1, x, 0.000000000000001);

double root = squareRoot.Invoke(25);

Code as well as post-processing helper class could be downloaded here