C# Continuation Monad Implementation

Question

I have been working on allowing function chaining. I have created a class called continuationmonad which takes a value, and a function from a => b. This allows me to use fmap and bind to chain these together. I have also used lazy to allowed calls to be defered where possible.

Is this class really the continuation monad or is it something else. I am finding it hard to find good literature which is not is Haskell.

Also any comments on how to improve / correct this.

using NUnit.Framework;
using System;

namespace Monads
{

    public class Continuation<Input, Output>{
        public Continuation(Input value, Func<Input,Output> function){
            this.value = new Lazy<Input>( () => value);
            this.function = function;
        }

        public Continuation(Lazy<Input> value, Func<Input,Output> function){
            this.value = value;
            this.function = function;
        }

        public Continuation<Output, Result> FMap<Result>(Func<Output, Result> map){
            return new Continuation<Output, Result>(new Lazy<Output>( () => Run() ), x => map(x));
        }

        public Continuation<Output,Result> Bind<Result>(Func<Output, Continuation<Output, Result>> f){
            return f(Run());
        }

        public Output Run(){
            return function(value.Value);
        }

        private Func<Input, Output> function;
        private Lazy<Input> value;
    }

    public static class ContinuationExtension{
        public static Continuation<A,B> Unit<A,B>(this Func<A,B> f, A value){
            return new Continuation<A, B>(value,f);
        }

        public static Continuation<A,B> Unit<A,B>(this A value,Func<A,B> f){
            return new Continuation<A, B>(value,f);
        }
    }

    [TestFixture]
    public class MonadTests
    {

        public Continuation<int,int> Wrapped(int value){
            return new Continuation<int,int>(value, x => x * 10);
        }

        [Test]
        public void ContinuationMonadTests()
        {

            var number = 42;
            var result = number.Unit(x => x + 8).FMap(x => x * 2).Bind(Wrapped).Run();

            Console.WriteLine(result);
        }
    }
}

Answer 1

I have created a very comprehensive introduction to the Continuation monad that you can Find Here Discovering the Continuation Monad in C#

Also you can find a.Net Fiddle here

I Repeat it in summary here Starting from an initial Function

int Square(int x ){return (x * x);}

2. Use Callback and remove return type

    public static void Square(int x, Action<int> callback)
    {
    callback(x * x);
    }

3. Curry the Callback

    public static Action<Action<int>> Square(int x)
    {
     return (callback) => { callback(x * x); };
    }

4. Generalize the returned Continuation

    public static Func<Func<int,T>,T> Square<T>(int x)
    {
         return (callback) => { callback(x * x); };
    }

5. Extract the Continuation Structure Also Known As the Return Method of the monad. That is Give me a value and i will give you a Monad for this value

    //((U→ T) → T)

       delegate T Cont<U, T>(Func<U, T> f);

    public static Cont<U, T> ToContinuation<U, T>(this U x)
    {
       return (callback) => callback(x);
    }

    square.ToContinuation<Func<int, int>, int>()

6. Add The bind Monadic method and thus Complete the Monad.That is Give me a Two Monads and i will combine them to a new monad

((A→ T) → T)→( A→((B→ T) → T))→ ((B→ T) → T)

    public static Cont<V, Answer> Bind<T, U, V, Answer>(
    this Cont<T, Answer> m,
    Func<T, Cont<U, Answer>> k, 
    Func<T, U, V> selector)
    {
     return (Func<V, Answer> c) => 
    m(t => k(t)(y => c(selector(t, y))));
    }

Answer 2

This is not the continuation monad. You are much closer to the Haskell Monad instance for functions.

You aren't getting anything that you couldn't get just from using Lazy<>. Since you have provided the input when you build an instance of your class, you aren't building functions, you are building values that are determined by a computation that hasn't been evaluated yet. Lazy<> delays the evaluation of computation until the value is needed.

Let's put together something like the Haskell Monad instance for functions in c#. LINQ syntax has established the convention for Monads in c#. They should have:

• a Select extension method analogous to a Haskell Functor's fmap
• a SelectMany extension method analogous to Haskell's Monad's >>=
• an additional SelectMany that LINQ syntax uses. This takes an additional function that combines the value from two steps together.

Unfortunately, there's no convention for what the analog of a Monad's return should be called; we'll call ours Constant. Unfortunately, Constant won't be very convenient because c#'s type inference won't be able to figure out the types.

public static class Function
{
    public static Func<TIn, TOut> Constant<TIn, TOut>(TOut result)
    {
        return x => result;
    }

    public static Func<TIn, TOut> Select<TIn, TMid, TOut>(
        this Func<TIn, TMid> func,
        Func<TMid, TOut> proj)
    {
        return x => proj(func(x));
    }

    public static Func<TIn, TOut> SelectMany<TIn, TMid, TOut>(
        this Func<TIn, TMid> func,
        Func<TMid, Func<TIn, TOut>> proj)
    {
        return x => proj(func(x))(x);
    }

    public static Func<TIn, TOut> SelectMany<TIn, TMid1, TMid2, TOut>(
        this Func<TIn, TMid1> func,
        Func<TMid1, Func<TIn, TMid2>> proj1,
        Func<TMid1, TMid2, TOut> proj2)
    {
        return x => {
            var mid1 = func(x);
            var mid2 = proj1(mid1)(x);
            return proj2(mid1, mid2);
        };
    }
}

Note that defining these extension methods only lets you interact with something like it's a Monad, it doesn't let you write code that's generic over the specific Monad being used. There's a sketch of how to do that in the second half of this answer.

Answer 3

This might be a bit opinion based but I'll try to give you my 5ct anyway.

Let's have a look at your class and their instances:

It includes a value and a function where you (tried) to make it all a lazy. From a theoretical view I can see no difference to Lazy<T> on first glance:

You can surely convert one of your Continuation<Input,Output> to just a Lazy<Output>.

The same is true for the reverse: given some lazy value a you can make a instance with just

new Continuation(a, x => x)

So to me it seems that you just reinvented Lazy (which is an monad, in Haskell you would call it Identity.

The Cont monad is not really easy to crasp but it's really more related to .net-Events or .net-Observables. The datastructure itself would be like

Func<Func<Input,Output>, Output>

Where you pass in a continuation Func<Input,Output> to some internal calculation and then the struture than will call it when it has calculated an input Input to get the final result.

This might be a bit cryptic but one .net application are the Async workflows F# uses and which stood model for C#s async/await behaviour in some sense.

I have some material I used for a talk on a simpified version of this monad in C# on github maybe you'll find it interesting.