Wednesday 16 December 2009

C# Continuation Monad



using System;


public static class ContinuationMonad
{
    public static Func<Func<V, R>, R> SelectMany<T, U, V, R>(
             this Func<Func<T, R>, R> m,
                  Func<T, Func<Func<U, R>, R>> f,
                  Func<T, U, V> p)
    {
        return c => m(a => f(a)(x => c(p(a, x))));
    }

    public static Func<Func<T, R>, R> Return<T, R>(this T x)
    {
        return k => k(x);
    }

}

public class Program
{
    public static void Main()
    {
        Func<int, Func<Func<int, int>, int>> facCont = null;
        facCont = n => n == 0 ? 1.Return<int, int>()
                          : from x in n.Return<int, int>()
                            from y in facCont(x - 1)
                            select x * y;

        Func<int, int> fac = n => facCont(n)(x => x);


        Console.WriteLine(fac(5));
    }
}

F# Continuation Monad (Tail Recursive Factorial)



// Continuation Monad in F#

type ContinuationMonad() =
    // ma -> (a -> mb) -> mb
    member this.Bind (m, f) = fun c -> m (fun a -> f a c)
    // a -> ma
    member this.Return x = fun k -> k x
    // ma -> ma
    member this.ReturnFrom m = m

let cont = ContinuationMonad()

let fac n =
    let rec loop n =
      cont {
              match n with
              | n when n = 0I -> return 1I
              | _ -> let! x = fun f -> f n
                     let! y = loop (n - 1I)
                     return x * y
           }
    loop n (fun x -> x)

printf "%A" (fac 100000I)

Monday 14 December 2009

C# QuickSort using Continuation Passing Style (As requested by a comment)



using System;
using System.Linq;
using System.Collections.Generic;

public static class ListExtensions
{
    public static Tuple<IEnumerable<T>, IEnumerable<T>> Partition<T>(
         this IEnumerable<T> items, Func<T, bool> p)
    {
        var xs = items.Where(p);
        var ys = items.Except(xs);
        return Tuple.Create(xs, ys);
    }

    public static IEnumerable<T> Loop<T>(
        IEnumerable<T> xs,
        Func<IEnumerable<T>, IEnumerable<T>> cont) where T : IComparable
    {
        if (!xs.GetEnumerator().MoveNext())
            return cont(new T[0]);
        else
        {
            var x = xs.First();
            var xsp = xs.Skip(1);
            var parts = xsp.Partition(y => y.CompareTo(x) > 0);
            return Loop<T>(parts.Item1, lacc =>
                   Loop<T>(parts.Item2, racc =>
                       cont(lacc.Concat(new[] { x }).Concat(racc))));
        }
    }

    public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> xs)
                                 where T : IComparable
    {
        return Loop<T>(xs, x => x);
    }
}