Category Theory via C# (17) Monad-like Tuple<>, Task<>, IQueryable<> And IQbservable<>

[LINQ via C# series]#

[Category Theory via C# series]#

Latest version: https://weblogs.asp.net/dixin/category-theory-via-csharp-7-monad-and-linq-to-monads#

Tuple<>: lack of laziness#

Theoretically, Tuple<> should be counted as the Id<> monad. However, it is lack of laziness. In the context of C# and LINQ, it is only monad-like.

This is its SelectMany:

1
// [Pure]
2
public static partial class TupleExtensions
3
{
4
    // Required by LINQ.
5
    public static Tuple<TResult> SelectMany<TSource, TSelector, TResult>
6
        (this Tuple<TSource> source,
7
         Func<TSource, Tuple<TSelector>> selector,
8
         Func<TSource, TSelector, TResult> resultSelector) =>
9
            new Tuple<TResult>(resultSelector(source.Item1, selector(source.Item1).Item1));
10

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

which can implement μ, η, φ, ι, Select:

1
// [Pure]
2
public static partial class TupleExtensions
3
{
4
    // μ: Tuple<Tuple<T> => Tuple<T>
5
    public static Tuple<TResult> Flatten<TResult>
6
        (this Tuple<Tuple<TResult>> source) => source.SelectMany(Functions.Id);
7

8
    // η: T -> Tuple<T> is already implemented previously as TupleExtensions.Tuple.
9

10
    // φ: Lazy<Tuple<T1>, Tuple<T2>> => Tuple<Lazy<T1, T2>>
11
    public static Tuple<Lazy<T1, T2>> Binary2<T1, T2>
12
        (this Lazy<Tuple<T1>, Tuple<T2>> binaryFunctor) =>
13
            binaryFunctor.Value1.SelectMany(
14
                value1 => binaryFunctor.Value2,
15
                (value1, value2) => new Lazy<T1, T2>(value1, value2));
16

17
    // ι: TUnit -> Tuple<TUnit> is already implemented previously with η: T -> Tuple<T>.
18

19
    // Select: (TSource -> TResult) -> (Tuple<TSource> -> Tuple<TResult>)
20
    public static Tuple<TResult> Select2<TSource, TResult>
21
        (this Tuple<TSource> source, Func<TSource, TResult> selector) =>
22
            source.SelectMany(value => selector(value).Tuple());
23
}

Tuple<> is most close to the Haskell Id Monad.

Task<>: lack of purity#

Task<> also seems monadic, but is lack of purity. This is the SelectMany for Task<>:

1
// Impure.
2
public static partial class TaskExtensions
3
{
4
    // Required by LINQ.
5
    public static async Task<TResult> SelectMany<TSource, TSelector, TResult>
6
        (this Task<TSource> source,
7
         Func<TSource, Task<TSelector>> selector,
8
         Func<TSource, TSelector, TResult> resultSelector) =>
9
            resultSelector(await source, await selector(await source));
10

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

which can implement μ, η, φ, ι, Select:

1
// Impure.
2
public static partial class TaskExtensions
3
{
4
    // μ: Task<Task<T> => Task<T>
5
    public static Task<TResult> Flatten<TResult>
6
        (this Task<Task<TResult>> source) => source.SelectMany(Functions.Id);
7

8
    // η: T -> Task<T> is already implemented previously as TaskExtensions.Task.
9

10
    // φ: Lazy<Task<T1>, Task<T2>> => Task<Lazy<T1, T2>>
11
    public static Task<Lazy<T1, T2>> Binary2<T1, T2>
12
        (this Lazy<Task<T1>, Task<T2>> binaryFunctor) =>
13
            binaryFunctor.Value1.SelectMany(
14
                value1 => binaryFunctor.Value2,
15
                (value1, value2) => new Lazy<T1, T2>(value1, value2));
16

17
    // ι: TUnit -> Task<TUnit> is already implemented previously with η: T -> Task<T>.
18

19
    // Select: (TSource -> TResult) -> (Task<TSource> -> Task<TResult>)
20
    public static Task<TResult> Select2<TSource, TResult>
21
        (this Task<TSource> source, Func<TSource, TResult> selector) =>
22
            source.SelectMany(value => selector(value).Task());
23
}

Task<> and LINQ#

With above SelectMany, Task<> can be used in LINQ syntax:

1
Func<string, Task<string>> query = url =>
2
    from httpResponseMessage in new HttpClient().GetAsync(url) // Returns Task<HttpResponseMessage>
3
    from html in httpResponseMessage.Content.ReadAsStringAsync() // Returns Task<string>
4
    select html;
5
string result = await query("https://weblogs.asp.net/dixin");

Non-generic Task#

Task is a wrapper of Func and Task is a wrapper of Action. Actually Action can be viewed as Func, so that Task can be viewed as Task. Since C# compiler does not allow Void to be used in this way, Task can be just viewed as Task. In this way, Task become like monad too.

1
// Impure.
2
public static partial class TaskExtensions
3
{
4
    // Required by LINQ.
5
    public static async Task<TResult> SelectMany<TSelector, TResult>(
6
        this Task source,
7
        Func<Unit, Task<TSelector>> selector,
8
        Func<Unit, TSelector, TResult> resultSelector)
9
    {
10
        await source;
11
        return resultSelector(null, await selector(null));
12
    }
13

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

so that

1
// Impure.
2
public static partial class TaskExtensions
3
{
4
    // η: Unit -> Task.
5
    public static Task Task(Unit unit) => System.Threading.Tasks.Task.Run(() => { });
6

7
    // ι: TUnit -> Task is already implemented previously with η: Unit -> Task.
8

9
    // Select: (Unit -> TResult) -> (Task -> Task<TResult>)
10
    public static Task<TResult> Select<TResult>
11
        (this Task source, Func<Unit, TResult> selector) => source.SelectMany(value => selector(value).Task());
12
}

IQueryable<> is like a monad#

IQueryable<> has been discussed a lot in previous posts. It looks like monad, with laziness and purity:

1
using (NorthwindDataContext database = new NorthwindDataContext())
2
{
3
    var query = from category in database.Categories
4
                from product in category.Products
5
                select new { category.CategoryName, product.ProductName }; // Laziness
6

7
    query.ForEach(value => { }); // Execution.
8
}

Or equivalently:

1
using (NorthwindDataContext database = new NorthwindDataContext())
2
{
3
    var query = database.Categories.SelectMany(
4
        category => category.Products,
5
        (category, product) => new { category.CategoryName, product.ProductName }); // Laziness
6

7
    query.ForEach(value => { }); // Execution.
8
}

However, this is its SelectMany implementation:

1
// [Pure]
2
public static partial class QueryableExtensions
3
{
4
    public static IQueryable<TResult> SelectMany<TSource, TCollection, TResult>
5
        (this IQueryable<TSource> source,
6
         Expression<Func<TSource, IEnumerable<TCollection>>> collectionSelector,
7
         Expression<Func<TSource, TCollection, TResult>> resultSelector) =>
8
            source.Provider.CreateQuery<TResult>(Expression.Call(
9
                null,
10
                ((MethodInfo)MethodBase.GetCurrentMethod()).MakeGenericMethod(
11
                    new Type[] { typeof(TSource), typeof(TCollection), typeof(TResult) }),
12
                new Expression[]
13
                    {
14
                        source.Expression,
15
                        Expression.Quote(collectionSelector),
16
                        Expression.Quote(resultSelector)
17
                    }));
18

19
    public static IQueryable<TResult> SelectMany<TSource, TResult>
20
        (this IQueryable<TSource> source,
21
         Expression<Func<TSource, IEnumerable<TResult>>> selector) =>
22
            source.Provider.CreateQuery<TResult>(Expression.Call(
23
                null,
24
                ((MethodInfo)MethodBase.GetCurrentMethod()).MakeGenericMethod(
25
                    new Type[] { typeof(TSource), typeof(TResult) }),
26
                new Expression[] { source.Expression, Expression.Quote(selector) }));
27
}

As discussed before, when working with IQueryable, the lambda expressions are not functions but data structure - an abstract syntax tree. So that a lambda-like expression trees in the query can be compiled to something else - here a T-SQL query:

1
SELECT [t0].[CategoryName], [t1].[ProductName]
2
FROM [dbo].[Categories] AS [t0], [dbo].[Products] AS [t1]
3
WHERE [t1].[CategoryID] = [t0].[CategoryID]

This is a very powerful feature of C# language and LINQ.

IQbservable<> is also like a monad#

IQbservable<> is provided by System.Reactive.Interfaces, a part of Rx (Reactive Extensions). It is the queryable version of IObservable<>, works similarly with expression lambda-like expression trees.

Here are 2 samples of Qbservable providers:

Unit tests#

Following unit tests demonstrate the usage of monadic Tuple<> and Task<>. Notice Tuple is lack of laziness, and Task<>’s SelectMany extension method work for both cold tasks and hot tasks.

1
public partial class MonadTests
2
{
3
    [TestMethod()]
4
    public void TupleTest()
5
    {
6
        bool isExecuted = false;
7
        Tuple<int> one = new Tuple<int>(1);
8
        Tuple<int> two = new Tuple<int>(2);
9
        Func<int, Func<int, int>> add = x => y => { isExecuted = true; return x + y; };
10
        Tuple<int> query = from x in one
11
                            from y in two
12
                            from _ in one
13
                            select add(x)(y);
14
        Assert.IsTrue(isExecuted); // No laziness.
15
        Assert.AreEqual(1 + 2, query.Item1); // Execution.
16

17
        // Monad law 1: m.Monad().SelectMany(f) == f(m)
18
        Func<int, Tuple<int>> addOne = x => (x + 1).Tuple();
19
        Tuple<int> left = 1.Tuple().SelectMany(addOne);
20
        Tuple<int> right = addOne(1);
21
        Assert.AreEqual(left.Item1, right.Item1);
22
        // Monad law 2: M.SelectMany(Monad) == M
23
        Tuple<int> M = 1.Tuple();
24
        left = M.SelectMany(TupleExtensions.Tuple);
25
        right = M;
26
        Assert.AreEqual(left.Item1, right.Item1);
27
        // Monad law 3: M.SelectMany(f1).SelectMany(f2) == M.SelectMany(x => f1(x).SelectMany(f2))
28
        Func<int, Tuple<int>> addTwo = x => (x + 2).Tuple();
29
        left = M.SelectMany(addOne).SelectMany(addTwo);
30
        right = M.SelectMany(x => addOne(x).SelectMany(addTwo));
31
        Assert.AreEqual(left.Item1, right.Item1);
32
    }
33

34
    [TestMethod()]
35
    public void HotTaskTest()
36
    {
37
        Task<string> a = Task.Run(() => "a");
38
        Task<string> b = Task.Run(() => "b");
39
        Func<string, Func<string, string>> concat = x => y => x + y;
40
        Task<string> query1 = from x in a
41
                                from y in b
42
                                from _ in a
43
                                select concat(x)(y);
44
        Assert.AreEqual("a" + "b", query1.Result);
45

46
        // Monad law 1: m.Monad().SelectMany(f) == f(m)
47
        Func<int, Task<int>> addOne = x => (x + 1).Task();
48
        Task<int> left = 1.Task().SelectMany(addOne);
49
        Task<int> right = addOne(1);
50
        Assert.AreEqual(left.Result, right.Result);
51
        // Monad law 2: M.SelectMany(Monad) == M
52
        Task<int> M = 1.Task();
53
        left = M.SelectMany(TaskExtensions.Task);
54
        right = M;
55
        Assert.AreEqual(left.Result, right.Result);
56
        // Monad law 3: M.SelectMany(f1).SelectMany(f2) == M.SelectMany(x => f1(x).SelectMany(f2))
57
        M = 1.Task();
58
        Func<int, Task<int>> addTwo = x => (x + 2).Task();
59
        left = M.SelectMany(addOne).SelectMany(addTwo);
60
        right = M.SelectMany(x => addOne(x).SelectMany(addTwo));
61
        Assert.AreEqual(left.Result, right.Result);
62
    }
63

64
    [TestMethod()]
65
    public void ColdTaskTest()
66
    {
67
        bool isExecuted1 = false;
68
        bool isExecuted2 = false;
69
        bool isExecuted3 = false;
70
        Task<string> a = new Task<string>(() => { isExecuted1 = true; return "a"; });
71
        Task<string> b = new Task<string>(() => { isExecuted2 = true; return "b"; });
72
        Func<string, Func<string, string>> concat = x => y => { isExecuted3 = true; return x + y; };
73
        Task<string> query = from x in a
74
                                from y in b
75
                                from _ in a
76
                                select concat(x)(y);
77
        Assert.IsFalse(isExecuted1); // Laziness.
78
        Assert.IsFalse(isExecuted2); // Laziness.
79
        Assert.IsFalse(isExecuted3); // Laziness.
80
        a.Start(); // Execution.
81
        b.Start(); // Execution.
82
        Assert.AreEqual("a" + "b", query.Result);
83
        Assert.IsTrue(isExecuted1);
84
        Assert.IsTrue(isExecuted2);
85
        Assert.IsTrue(isExecuted3);
86

87
        // Monad law 1: m.Monad().SelectMany(f) == f(m)
88
        List<Task<int>> addOneTasks = new List<Task<int>>();
89
        Func<int, Task<int>> addOne = x =>
90
        {
91
            Task<int> task = (x + 1).Task(true);
92
            addOneTasks.Add(task);
93
            return task;
94
        };
95
        Task<int> one = 1.Task(true);
96
        Task<int> left = one.SelectMany(addOne);
97
        Task<int> right = addOne(1);
98
        one.Start();
99
        while (addOneTasks.Count < 2) { }
100
        addOneTasks.ForEach(task => task.Start());
101
        Assert.AreEqual(left.Result, right.Result);
102
        // Monad law 2: M.SelectMany(Monad) == M
103
        Task<int> M = 1.Task(true);
104
        left = M.SelectMany(TaskExtensions.Task);
105
        right = M;
106
        M.Start();
107
        Assert.AreEqual(left.Result, right.Result);
108
        // Monad law 3: M.SelectMany(f1).SelectMany(f2) == M.SelectMany(x => f1(x).SelectMany(f2))
109
        addOneTasks.Clear();
110
        List<Task<int>> addTwoTasks = new List<Task<int>>();
111
        M = 1.Task(true);
112
        Func<int, Task<int>> addTwo = x =>
113
        {
114
            Task<int> task = (x + 1).Task(true);
115
            addTwoTasks.Add(task);
116
            return task;
117
        };
118
        left = M.SelectMany(addOne).SelectMany(addTwo);
119
        right = M.SelectMany(x => addOne(x).SelectMany(addTwo));
120
        M.Start();
121
        while (addOneTasks.Count < 2) { }
122
        addOneTasks.ForEach(task => task.Start());
123
        while (addTwoTasks.Count < 2) { }
124
        addTwoTasks.ForEach(task => task.Start());
125
        Assert.AreEqual(left.Result, right.Result);
126
    }
127
}