Category Theory via C# (16) More Monads: Lazy<>, Func<>, Nullable<>, ParallelQuery<> And IObservale<>

Again, Lazy<> is the simplest monad, it is just the lazy version of Tuple<>, and should be considered as the Id<> monad. This is the implementation of its SelectMany:

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

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

So that Lazy<> is a monad, a monoidal functor, and a functor:

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

8
    // η: T -> Lazy<T> is already implemented previously as LazyExtensions.Lazy.
9

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

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

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

Lazy<> is similar to the Haskell Id Monad. The usage will be demonstrated in unit tests later.

Func<> monad#

SelectMany can be implemented for Func<> too:

1
// [Pure]
2
public static partial class FuncExtensions
3
{
4
    // Required by LINQ.
5
    public static Func<TResult> SelectMany<TSource, TSelector, TResult>
6
        (this Func<TSource> source,
7
         Func<TSource, Func<TSelector>> selector,
8
         Func<TSource, TSelector, TResult> resultSelector) =>
9
            () =>
10
                {
11
                    TSource sourceValue = source();
12
                    return resultSelector(sourceValue, selector(sourceValue)());
13
                };
14

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

So that Func<> is a monad, a monoidal functor, and a functor:

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

8
    // η: T -> Func<T> is already implemented previously as FuncExtensions.Func.
9

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

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

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

Nullable<> monad#

And this is the SelectMany for Nullable<>:

1
// [Pure]
2
public static partial class NullableExtensions
3
{
4
    // Required by LINQ.
5
    public static Nullable<TResult> SelectMany<TSource, TSelector, TResult>
6
        (this Nullable<TSource> source,
7
         Func<TSource, Nullable<TSelector>> selector,
8
         Func<TSource, TSelector, TResult> resultSelector) =>
9
            new Nullable<TResult>(() =>
10
                {
11
                    if (source.HasValue)
12
                    {
13
                        Nullable<TSelector> selectorResult = selector(source.Value);
14
                        if (selectorResult.HasValue)
15
                        {
16
                            return Tuple.Create(true, resultSelector(source.Value, selectorResult.Value));
17
                        }
18
                    }
19

20
                    return Tuple.Create(false, default(TResult));
21
                });
22

23
    // Not required, just for convenience.
24
    public static Nullable<TResult> SelectMany<TSource, TResult>
25
        (this Nullable<TSource> source, Func<TSource, Nullable<TResult>> selector) =>
26
            source.SelectMany(selector, Functions.False);
27
}

So that Nullable<> is a monad, a monoidal functor, and a functor:

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

8
    // η: T -> Nullable<T> is already implemented previously as NullableExtensions.Nullable.
9

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

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

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

ParallelQuery<> monad#

Parallel LINQ provides ParallelQuery<> monad. This is its SelectMany:

1
[Pure]
2
public static class ParallelEnumerable
3
{
4
    public static ParallelQuery<TResult> SelectMany<TSource, TCollection, TResult>
5
        (this ParallelQuery<TSource> source,
6
         Func<TSource, IEnumerable<TCollection>> collectionSelector,
7
         Func<TSource, TCollection, TResult> resultSelector) =>
8
            new SelectManyQueryOperator<TSource, TCollection, TResult>(
9
                source, collectionSelector, null, resultSelector);
10
}

The implementation of System.Linq.Parallel.SelectManyQueryOperator<TLeftInput, TRightInput, TOutput> class is a big parallel computing topic and will be skipped in these category theory posts.

ParallelQuery<> can be used with laziness and purity:

1
ParallelQuery<int> query = from value in Enumerable.Range(0, 1000).AsParallel()
2
                           from repeat in Enumerable.Repeat(value, 2)
3
                           select repeat; // Laziness.
4

5
query.ForAll(Console.WriteLine); // Execution.

Above code is just an example of using ParallelQuery<> monad with LINQ syntax. In real world parallel query, some performance pitfalls has to be noticed.

IObservable<> monad#

IObservable<> is built-in in mscorlib. Then Rx (Reactive Extensions) makes IObservable<> a monad. In System.Reactive.Linq.dll, SelectMany is implemented for IObservable<>:

1
public static class Observable
2
{
3
    public static IObservable<TResult> SelectMany<TSource, TCollection, TResult>
4
        (this IObservable<TSource> source,
5
         Func<TSource, IObservable<TCollection>> collectionSelector,
6
         Func<TSource, TCollection, TResult> resultSelector) =>
7
            new SelectMany<TSource, TCollection, TResult>(
8
                source, collectionSelector, resultSelector);
9
}

System.Reactive.Linq.ObservableImpl.SelectMany<TSource, TCollection, TResult> class’s source code can be viewed on github here.

So IObservable becomes a monad andcan be used in LINQ with laziness and purity:

1
IObservable<int> query = from value in Observable.Range(0, 1000)
2
                         from repeat in Observable.Repeat(value, 2)
3
                         select repeat; // Laziness.
4
query = query.Do(value => Console.WriteLine("Do")); // Laziness.
5

6
query.Subscribe(Console.WriteLine); // Execution.

Another example is the MouseDrag event implementation in WPF:

1
[Pure]
2
public static class UIElementExtensions
3
{
4
    public static IObservable<EventPattern<MouseEventArgs>> MouseDrag
5
        (this UIElement element) =>
6
            from _ in Observable.FromEventPattern<MouseEventArgs>(element, nameof(element.MouseDown))
7
            from @event in Observable.FromEventPattern<MouseEventArgs>(element, nameof(element.MouseMove))
8
                .TakeUntil(Observable.FromEventPattern<MouseEventArgs>(element, nameof(element.MouseUp)))
9
            select @event;
10
}

The observing starts from MouseDown event, then keep taking MouseMove event, until MouseUp event is observed. So that:

1
element.MouseDrag()
2
    .Subscribe(@event => OnMouseDrag(@event.EventArgs));

Unit tests#

1
public partial class MonadTests
2
{
3
    [TestMethod()]
4
    public void LazyTest()
5
    {
6
        bool isExecuted1 = false;
7
        bool isExecuted2 = false;
8
        bool isExecuted3 = false;
9
        Lazy<int> one = new Lazy<int>(() => { isExecuted1 = true; return 1; });
10
        Lazy<int> two = new Lazy<int>(() => { isExecuted2 = true; return 2; });
11
        Func<int, Func<int, int>> add = x => y => { isExecuted3 = true; return x + y; };
12
        Lazy<int> query = from x in one
13
                            from y in two
14
                            from _ in one
15
                            select add(x)(y);
16
        Assert.IsFalse(isExecuted1); // Laziness.
17
        Assert.IsFalse(isExecuted2); // Laziness.
18
        Assert.IsFalse(isExecuted3); // Laziness.
19
        Assert.AreEqual(1 + 2, query.Value); // Execution.
20
        Assert.IsTrue(isExecuted1);
21
        Assert.IsTrue(isExecuted2);
22
        Assert.IsTrue(isExecuted3);
23

24
        // Monad law 1: m.Monad().SelectMany(f) == f(m)
25
        Func<int, Lazy<int>> addOne = x => (x + 1).Lazy();
26
        Lazy<int> left = 1.Lazy().SelectMany(addOne);
27
        Lazy<int> right = addOne(1);
28
        Assert.AreEqual(left.Value, right.Value);
29
        // Monad law 2: M.SelectMany(Monad) == M
30
        Lazy<int> M = 1.Lazy();
31
        left = M.SelectMany(LazyExtensions.Lazy);
32
        right = M;
33
        Assert.AreEqual(left.Value, right.Value);
34
        // Monad law 3: M.SelectMany(f1).SelectMany(f2) == M.SelectMany(x => f1(x).SelectMany(f2))
35
        Func<int, Lazy<int>> addTwo = x => (x + 2).Lazy();
36
        left = M.SelectMany(addOne).SelectMany(addTwo);
37
        right = M.SelectMany(x => addOne(x).SelectMany(addTwo));
38
        Assert.AreEqual(left.Value, right.Value);
39
    }
40

41
    [TestMethod()]
42
    public void FuncTest()
43
    {
44
        bool isExecuted1 = false;
45
        bool isExecuted2 = false;
46
        bool isExecuted3 = false;
47
        bool isExecuted4 = false;
48
        Func<int> f1 = () => { isExecuted1 = true; return 1; };
49
        Func<int> f2 = () => { isExecuted2 = true; return 2; };
50
        Func<int, int> f3 = x => { isExecuted3 = true; return x + 1; };
51
        Func<int, Func<int, int>> f4 = x => y => { isExecuted4 = true; return x + y; };
52
        Func<int> query1 = from x in f1
53
                            from y in f2
54
                            from z in f3.Partial(y)
55
                            from _ in "abc".Func()
56
                            let f4x = f4(x)
57
                            select f4x(z);
58
        Assert.IsFalse(isExecuted1); // Laziness.
59
        Assert.IsFalse(isExecuted2); // Laziness.
60
        Assert.IsFalse(isExecuted3); // Laziness.
61
        Assert.IsFalse(isExecuted4); // Laziness.
62
        Assert.AreEqual(1 + 2 + 1, query1()); // Execution.
63
        Assert.IsTrue(isExecuted1);
64
        Assert.IsTrue(isExecuted2);
65
        Assert.IsTrue(isExecuted3);
66
        Assert.IsTrue(isExecuted4);
67

68
        // Monad law 1: m.Monad().SelectMany(f) == f(m)
69
        Func<int, Func<int>> addOne = x => (x + 1).Func();
70
        Func<int> left = 1.Func().SelectMany(addOne);
71
        Func<int> right = addOne(1);
72
        Assert.AreEqual(left(), right());
73
        // Monad law 2: M.SelectMany(Monad) == M
74
        Func<int> M = 1.Func();
75
        left = M.SelectMany(FuncExtensions.Func);
76
        right = M;
77
        Assert.AreEqual(left(), right());
78
        // Monad law 3: M.SelectMany(f1).SelectMany(f2) == M.SelectMany(x => f1(x).SelectMany(f2))
79
        Func<int, Func<int>> addTwo = x => (x + 2).Func();
80
        left = M.SelectMany(addOne).SelectMany(addTwo);
81
        right = M.SelectMany(x => addOne(x).SelectMany(addTwo));
82
        Assert.AreEqual(left(), right());
83

84
        bool isExecuted5 = false;
85
        bool isExecuted6 = false;
86
        bool isExecuted7 = false;
87
        Func<int, int> f5 = x => { isExecuted5 = true; return x + 1; };
88
        Func<string, int> f6 = x => { isExecuted6 = true; return x.Length; };
89
        Func<int, Func<int, string>> f7 = x => y =>
90
        { isExecuted7 = true; return new string('a', x + y); };
91
        Func<int, Func<string, string>> query2 = a => b =>
92
            (from x in f5(a).Func()
93
                from y in f6(b).Func()
94
                from z in 0.Func()
95
                select f7(x)(y))();
96
        Assert.IsFalse(isExecuted5); // Laziness.
97
        Assert.IsFalse(isExecuted6); // Laziness.
98
        Assert.IsFalse(isExecuted7); // Laziness.
99
        Assert.AreEqual(new string('a', 1 + 1 + "abc".Length), query2(1)("abc")); // Execution.
100
        Assert.IsTrue(isExecuted5);
101
        Assert.IsTrue(isExecuted6);
102
        Assert.IsTrue(isExecuted7);
103
    }
104

105
    [TestMethod()]
106
    public void NullableTest()
107
    {
108
        bool isExecuted1 = false;
109
        Func<int, Func<int, string>> add = x => y =>
110
        { isExecuted1 = true; return (x + y).ToString(CultureInfo.InvariantCulture); };
111
        Nullable<int> nullable1 = new Nullable<int>();
112
        Nullable<int> nullable2 = new Nullable<int>();
113
        Nullable<string> query1 = from x in nullable1
114
                                    from y in nullable2
115
                                    from _ in nullable1
116
                                    select add(x)(y);
117
        Assert.IsFalse(isExecuted1); // Laziness.
118
        Assert.IsFalse(query1.HasValue); // Execution.
119
        Assert.IsFalse(isExecuted1);
120

121
        bool isExecuted3 = false;
122
        bool isExecuted4 = false;
123
        bool isExecuted5 = false;
124
        add = x => y =>
125
        { isExecuted3 = true; return (x + y).ToString(CultureInfo.InvariantCulture); };
126
        Nullable<int> one = new Nullable<int>(() =>
127
        { isExecuted4 = true; return Tuple.Create(true, 1); });
128
        Nullable<int> two = new Nullable<int>(() =>
129
        { isExecuted5 = true; return Tuple.Create(true, 2); });
130
        Nullable<string> query2 = from x in one
131
                                    from y in two
132
                                    from _ in one
133
                                    select add(x)(y);
134
        Assert.IsFalse(isExecuted3); // Laziness.
135
        Assert.IsFalse(isExecuted4); // Laziness.
136
        Assert.IsFalse(isExecuted5); // Laziness.
137
        Assert.IsTrue(query2.HasValue); // Execution.
138
        Assert.AreEqual("3", query2.Value);
139
        Assert.IsTrue(isExecuted3);
140
        Assert.IsTrue(isExecuted4);
141
        Assert.IsTrue(isExecuted5);
142

143
        // Monad law 1: m.Monad().SelectMany(f) == f(m)
144
        Func<int, Nullable<int>> addOne = x => (x + 1).Nullable();
145
        Nullable<int> left = 1.Nullable().SelectMany(addOne);
146
        Nullable<int> right = addOne(1);
147
        Assert.AreEqual(left.Value, right.Value);
148
        // Monad law 2: M.SelectMany(Monad) == M
149
        Nullable<int> M = 1.Nullable();
150
        left = M.SelectMany(NullableExtensions.Nullable);
151
        right = M;
152
        Assert.AreEqual(left.Value, right.Value);
153
        // Monad law 3: M.SelectMany(f1).SelectMany(f2) == M.SelectMany(x => f1(x).SelectMany(f2))
154
        Func<int, Nullable<int>> addTwo = x => (x + 2).Nullable();
155
        left = M.SelectMany(addOne).SelectMany(addTwo);
156
        right = M.SelectMany(x => addOne(x).SelectMany(addTwo));
157
        Assert.AreEqual(left.Value, right.Value);
158
    }
159
}