Category Theory via C# (22) More Monad: Continuation Monad

826 words

4 minutes

Category Theory via C# (22) More Monad: Continuation Monad

2018-12-23

.NET

/

.NET Core

/

.NET Standard

/

C#

/

LINQ

[LINQ via C# series]#

[Category Theory via C# series]#

Latest version: https://weblogs.asp.net/dixin/category-theory-via-csharp-8-more-linq-to-monads#

Continuation and continuation-passing style#

In C#, callback is frequently used. For example, a very simple Add function, without asynchrony:

1
// [Pure]
2
public static partial class Cps
3
{
4
    // Add = (x, y) => x + y
5
    public static int Add
6
        (int x, int y) => x + y;
7
}

With a callback, it becomes:

1
// AddWithCallback = (x, y, callback) => callback(x + y)
2
public static TCallback AddWithCallback<TCallback>
3
    (int x, int y, Func<int, TCallback> callback) => callback(x + y);

In functional programming, a continuation is like a callback. Continuation-passing style (CPS) is a style of programming to pass the control to a continuation, just like in above example, (x + y) is calculated then passed to the callback.

For convenience, AddWithCallback can be curried a little bit:

1
// AddWithCallback = (x, y) => callback => callback(x + y)
2
public static Func<Func<int, TCallback>, TCallback> AddWithCallback<TCallback>
3
    (int x, int y) => callback => callback(x + y);

So that all the apperances of TCallback are in the return type Func<Func<int, TCallback>, TCallback>, then an alias Cps can be defined to make the code shorter:

1
// Cps<T, TContinuation> is alias of Func<Func<T, TContinuation>, TContinuation>
2
public delegate TContinuation Cps<out T, TContinuation>(Func<T, TContinuation> continuation);

Now a continuation-passing style function AddCps can be defined, which is exactly the same as above:

1
// AddCps = (x, y) => continuation => continuation(x + y)
2
public static Cps<int, TContinuation> AddCps<TContinuation>
3
    (int x, int y) => continuation => continuation(x + y);

Other examples are the SquareCps and SumOfSquareCps functions:

1
// SquareCps = x => continuation => continuation(x * x)
2
public static Cps<int, TContinuation> SquareCps<TContinuation>
3
    (int x) => continuation => continuation(x * x);
4

5
// SumOfSquaresCps = (x, y) => continuation => SquareCps(x)(xx => SquareCps(y)(yy => AddCps(xx)(yy)(continuation)));
6
public static Cps<int, TContinuation> SumOfSquaresCps<TContinuation>
7
    (int x, int y) => continuation =>
8
        SquareCps<TContinuation>(x)(xx =>
9
            SquareCps<TContinuation>(y)(yy =>
10
                AddCps<TContinuation>(xx, yy)(continuation)));

In this case, CPS makes code and algorithms harder to understand and maintain.

Continuation monad#

SelectMany can be implemented for Cps<T, TContinuation>:

1
[Pure]
2
public static partial class CpsExtensions
3
{
4
    // Required by LINQ.
5
    public static Cps<TResult, TContinuation> SelectMany<TSource, TSelector, TResult, TContinuation>
6
        (this Cps<TSource, TContinuation> source,
7
         Func<TSource, Cps<TSelector, TContinuation>> selector,
8
         Func<TSource, TSelector, TResult> resultSelector) =>
9
            continuation => source(sourceArg =>
10
                selector(sourceArg)(selectorArg =>
11
                    continuation(resultSelector(sourceArg, selectorArg))));
12

13
    // Not required, just for convenience.
14
    public static Cps<TResult, TContinuation> SelectMany<TSource, TResult, TContinuation>
15
        (this Cps<TSource, TContinuation> source, Func<TSource, Cps<TResult, TContinuation>> selector) =>
16
            source.SelectMany(selector, Functions.False);
17
}

so that:

1
// [Pure]
2
public static partial class CpsExtensions
3
{
4
    // η: T -> Cps<T, TContinuation>
5
    public static Cps<T, TContinuation> Cps<T, TContinuation>
6
        (this T arg) => continuation => continuation(arg);
7

8
    // φ: Lazy<Cps<T1, TContinuation>, Cps<T2, TContinuation>> => Cps<Lazy<T1, T2>, TContinuation>
9
    public static Cps<Lazy<T1, T2>, TContinuation> Binary<T1, T2, TContinuation>
10
        (this Lazy<Cps<T1, TContinuation>, Cps<T2, TContinuation>> binaryFunctor) =>
11
            binaryFunctor.Value1.SelectMany(
12
                value1 => binaryFunctor.Value2,
13
                (value1, value2) => new Lazy<T1, T2>(value1, value2));
14

15
    // ι: TUnit -> Cps<TUnit, TContinuation>
16
    public static Cps<Unit, TContinuation> Unit<TContinuation>
17
        (Unit unit) => unit.Cps<Unit, TContinuation>();
18

19
    // Select: (TSource -> TResult) -> (Cps<TSource, TContinuation> -> Cps<TResult, TContinuation>)
20
    public static Cps<TResult, TContinuation> Select<TSource, TResult, TContinuation>
21
        (this Cps<TSource, TContinuation> source, Func<TSource, TResult> selector) =>
22
            // continuation => source(sourceArg => continuation(selector(sourceArg)));
23
            // continuation => source(continuation.o(selector));
24
            source.SelectMany(value => selector(value).Cps<TResult, TContinuation>());
25
}

Cps< , > is a monad, monoidal functor, and functor.

Monad laws, and unit tests#

2 helper functions can be created:

1
// [Pure]
2
public static partial class CpsExtensions
3
{
4
    public static Func<T, TContinuation> NoCps<T, TContinuation>
5
        (this Func<T, Cps<TContinuation, TContinuation>> cps) => arg => cps(arg)(Functions.Id);
6

7
    public static T Invoke<T>
8
        (this Cps<T, T> cps) => cps(Functions.Id);
9
}

So the unit test becomes easy:

1
public partial class MonadTests
2
{
3
    [TestMethod()]
4
    public void ContinuationTest()
5
    {
6
        bool isExecuted1 = false;
7
        Func<int, Func<int, Func<string, string>>> f = x => y => z =>
8
            {
9
                isExecuted1 = true;
10
                return (x + y + z.Length).ToString(CultureInfo.InstalledUICulture);
11
            };
12
        Cps<string, int> query = from x in 1.Cps<int, int>()
13
                                    from y in 2.Cps<int, int>()
14
                                    from z in "abc".Cps<string, int>()
15
                                    select f(x)(y)(z);
16
        Assert.IsFalse(isExecuted1); // Laziness.
17
        Assert.AreEqual((1 + 2 + "abc".Length).ToString(CultureInfo.InstalledUICulture).Length, query(x => x.Length)); // Execution.
18
        Assert.IsTrue(isExecuted1);
19

20
        // Monad law 1: m.Monad().SelectMany(f) == f(m)
21
        Func<int, Cps<int, int>> addOne = x => (x + 1).Cps<int, int>();
22
        Cps<int, int> left = 1.Cps<int, int>().SelectMany(addOne);
23
        Cps<int, int> right = addOne(1);
24
        Assert.AreEqual(left.Invoke(), right.Invoke());
25
        // Monad law 2: M.SelectMany(Monad) == M
26
        Cps<int, int> M = 1.Cps<int, int>();
27
        left = M.SelectMany(CpsExtensions.Cps<int, int>);
28
        right = M;
29
        Assert.AreEqual(left.Invoke(), right.Invoke());
30
        // Monad law 3: M.SelectMany(f1).SelectMany(f2) == M.SelectMany(x => f1(x).SelectMany(f2))
31
        Func<int, Cps<int, int>> addTwo = x => (x + 2).Cps<int, int>();
32
        left = M.SelectMany(addOne).SelectMany(addTwo);
33
        right = M.SelectMany(x => addOne(x).SelectMany(addTwo));
34
        Assert.AreEqual(left.Invoke(), right.Invoke());
35
    }
36
}

And following is unit test for continuation functor, which also demonstrate the CPS version of factorial:

1
public partial class FunctorTests
2
{
3
    [TestMethod()]
4
    public void ContinuationTest()
5
    {
6
        Func<int, Cps<int, int>> factorialCps = null; // Must have.
7
        factorialCps = x => x == 0
8
            ? 1.Cps<int, int>()
9
            : (from y in factorialCps(x - 1)
10
               select x * y);
11
        Func<int, int> factorial = factorialCps.NoCps();
12
        Assert.AreEqual(3 * 2 * 1, factorial(3));
13

14
        // Functor law 1: F.Select(Id) == Id(F)
15
        Assert.AreEqual(factorialCps(3).Select(Functions.Id).Invoke(), Functions.Id(factorialCps(3)).Invoke());
16
        // Functor law 2: F.Select(f2.o(f1)) == F.Select(f1).Select(f2)
17
        Func<int, int> addOne = x => x + 1;
18
        Func<int, int> addTwo = x => x + 2;
19
        Cps<int, int> cps1 = factorialCps(3).Select(addTwo.o(addOne));
20
        Cps<int, int> cps2 = factorialCps(3).Select(addOne).Select(addTwo);
21
        Assert.AreEqual(cps1.Invoke(), cps2.Invoke());
22
    }
23
}