# C# can be functional pt2: Lists are Monads

## Preface: the story continues

I will start of with a warning that this post is the continuation of C# can be functional pt1: The Maybe Monad. That post explained numerous concepts of functional programming in great detail. Therefore I will refrain from the same endeavour in this post, and assume you already have a basic understanding of what a Functor, Applicative and a Monad is. The previous progress is captured by the overarching repository of this larger endeavour to explore functional concepts in C#: repo. Naturally the work of this post is also found there; as is denoted in the bottom right corner of relevant code snippets.## The basic class structure

Functional languages are keen on representing their lists as singly linked lists. This discourages the idea of accessing the list randomly since the lookup operation now requires linear time as opposed to constant time. The only sensible way of using such a list is by traversing it a from beginning to end.

An instance of such a list be one of two things: and empty list, containing nothing or a single element (which we will call the head) and another linked list as tail (which can be again one of the two). In C# we might write:

```
public abstract class SList<T>
{
}
public class Empty<T> : SList<T>
{
}
public class Cons<T> : SList<T>
{
public T Head { get; }
public SList<T> Tail { get; }
public Cons(T head, SList<T> tail)
{
this.Head = head;
this.Tail = tail;
}
}
```

full source

```
public static void PrintAll<T>(this SList<T> list)
{
for (var prev = list; prev is Cons<T> el; prev = el.Tail)
{
Console.WriteLine(el.Head.ToString());
}
}
```

full source## Basic list operations

To both make our lives a bit more easier down the road, as well as to get familiar with our newly found list type, we will define the basic concat operation, which simply concatenates two lists.

```
public static SList<T> concat<T>(this SList<T> one, SList<T> two)
{
// This is C# 8 syntax, of course it can be done in earlier
// versions as well but less elegantly.
switch ((one, two))
{
case (Empty<T> _, _): return two;
case (_, Empty<T> _): return one;
default:
var left = one as Cons<T>;
return new Cons<T>(
left.Head,
left.Tail.concat(two));
}
}
```

full source## Implementing the good stuff

As we know by now, the really interesting stuff is yet to be implemented. Let's start with all the specifications first, and then reason about their semantic meaning.

```
public static SList<TOut> fmap<TIn, TOut>(this SList<TIn> list, Func<TIn, TOut> func)
{
// TODO
}
public static SList<TOut> ab<TIn, TOut>(this SList<Func<TIn, TOut>> list, SList<TIn> arg)
{
// TODO
}
public static SList<TOut> bind<TIn, TOut>(this SList<TIn> list, Func<TIn, SList<TOut>> func)
{
// TODO
}
public static SList<T> pureSList<T>(T el)
{
// TODO
}
```

### Fmap makes Functors

"To apply a function over this object", that is the what fmap does. For maybe this could also mean silent rejection in the case of Nothing. With lists it is not much different; after all, we cannot apply a function over an empty list. For the non empty list we simply apply the function over the head and then apply fmap over the tail recursively to affect the all the elements in the list.

```
public static SList<TOut> fmap<TIn, TOut>(this SList<TIn> list, Func<TIn, TOut> func)
{
switch (list)
{
case Empty<TIn> _: return new Empty<TOut>();
case Cons<TIn> el: return new Cons<TOut>(
func(el.Head),
fmap(el.Tail, func));
default: return null;
}
}
// The very useful reflected version
public static SList<TOut> fmap<TIn, TOut>(this Func<TIn, TOut> func, SList<TIn> list)
=> list.fmap(func);
```

full source

```
public static SList<int> Double(SList<int> list)
{
return list.fmap(x => x + 1);
}
// Even changing the list's containing type
public static SList<string> ToWord(SList<int> list)
{
var words = new string[] {"one", "two", "three", "four"};
return list.fmap(x => x >= 0 && x < words.Length ? words[x] : "unknown number");
}
```

full source### Ab makes Applicatives

"To apply an argument wrapped in an object to an object containing a function." is the sentence that one ought to remember when implementing the function that ensures membership of the applicative typeclass. Just like with fmap, repetition is the key: we simply apply the given list of arguments to every function in the main list. There is however a nuance in the fact that instead of a single function we now get a lists of arguments for a lists of functions but there is no constraint that tells us that these lists are of equal size. To resolve this issue we simply consume only the items that have a respective element in the other list. Any excess is simply discarded.

```
public static SList<TOut> ab<TIn, TOut>(this SList<Func<TIn, TOut>> list, SList<TIn> arg)
{
switch ((list, arg))
{
// Base cases, either list is empty
case (Empty<Func<TIn, TOut>> _, _): return new Empty<TOut>();
case (_, Empty<TIn> _): return new Empty<TOut>();
// Recursive case, apply argument to function and continue with the tail.
default:
var funcs = list as Cons<Func<TIn, TOut>>;
var args = arg as Cons<TIn>;
return new Cons<TOut>(funcs.Head(args.Head), funcs.Tail.ab(args.Tail));
}
}
```

full source### Bind and pure and ye shall be a monad

"To apply a function to an object except the function returns an instance of that same object". Capturing in the workings of bind in that sentence highlights its similarity to fmap, except where fmap packages the result back into a functor, bind already gets a monad back from its provided function. For the maybe monad this was the end of the story, for lists we have a bit more complicated story. If we extrapolate the concept of applying the operation to every element in the list we end up with a list of lists. This would violate the definition of bind since its resulting type is not the same as that of the given function. To settle this discrepancy one can employ the help of concat to flatten the list of lists to a normal list again. Consider the following steps:

```
-- Function that returns a list with two copies of the argument
1. f = x => [x,x]
-- The input list l1
2. l1 = [1,2,3]
-- Mapping f over l1 to get l2
3. l2 = [[1,1],[2,2],[3,3]]
-- Concatenating l2 to get l3
4. l3 = [1,1,2,2,3,3]
```

I hear you pondering and yes you are absolutely correct: bind for lists is the same as concatenating after mapping, an operation also known as concatMap!

Us rests one final task before we may call SList a monad and that is to implement
pure. To complete our set of mnemonics: "To put an item inside an object". For lists
we could easily think to create a list with one item, a.k.a. a singleton. But we will
instead set out to derive this nonetheless correct idea from the holy *Monad Laws*.
We haven't touched on this before but there are 3 laws monads have to abide by regarding the
implementation of bind and pure. We will now only focus on 1, namely right identity:

```
1. Left Identity: (pure a) >>= f = f a
2. Right Identity: m >>= pure = m
3. Associativity: (m >>= f) >>= g = m >>= (\x -> f x >>= g)
```

```
public static void CheckRightAssociativity()
{
var input = new Cons<int>(
1, new Cons<int>(
2, new Cons<int>(
3, new Empty<int>())));
var output = input.bind(x => x.pureSList());
Debug.Assert(input == output);
}
```

full source

```
-- Input list
1. [1, 2, ..., n]
-- Apply the unknown function
2. [p(1), p(2), ..., p(n)]
-- Concatenating the result should yield
3. [1, 2, ..., n]
-- Reversing concatenation from 3 to 2 we find (among other possibilities)
4. [p(1), p(2), ..., p(n)] == [[1], [2], ..., [n]]
-- From that follows
5. forall x -> p(x) = [x]
-- Therefore is the singleton constructor valid under right identity
-- (Note that the other 2 laws should hold as well but I leave that as
-- an exercise)
```

```
public static SList<T> pureSList<T>(this T item)
{
return new Cons<T>(item, new Empty<T>());
}
```

full source## Yielding the power

If you got to this part you may congratulate yourself, it is quite a pill to swallow. In fact, lets celebrate our accomplishments by writing some useful transformations in terms of our powerful set of functions. First of all, let's write filter in terms of bind.

```
public static SList<T> filter<T>(this SList<T> list, Func<T, bool> predicate)
=> list.bind(x => predicate(x) ? x.pureSList() : new Empty<T>());
```

full source

```
public static SList<(T,T)> cartesianProduct<T>(SList<T> one, SList<T> two)
{
return one.bind(x =>
two.bind(y =>
new Cons<(T, T)>((x, y), new Empty<(T, T)>())));
}
```

full source

```
public static SList<TOut> listComprension<TIn, TOut>(
this SList<TIn> list,
Func<TIn, TOut> mapping,
Func<TIn, bool> predicate)
=> list.bind(x =>
{
if (predicate(x))
return new Cons<TOut>(
mapping(x),
new Empty<TOut>()) as SList<TOut>;
return new Empty<TOut>();
});
```

full source

```
-- Ideal case, lists are of equal size
1. zip [1,2,3] ['a','b', 'c'] = [(1, 'a'), (2, 'b'), (3, 'c')]
-- In case of different size lists, the excess is discarded
2. zip [1] [9,10,11] = [(1, 9)]
```

```
zip :: [a] -> [b] -> [(a,b)]
zip x y = (,) <$> x <*> y
-- Note that (,) is a function of type :: a -> b -> (a,b)
-- In other words this is the tuple constructor
```

```
public static SList<(T1, T2)> zip<T1, T2>(SList<T1> one, SList<T2> two)
{
Func<T1, Func<T2, (T1, T2)>> mkTuple = x => y => (x, y);
return mkTuple.fmap(one).ab(two);
}
```

full source## Summary

We have constructed the singly linked list in C# and made it no less than a Functor, Applicative, and a Monad. We did this using some newly established mnemonics:- fmap applies a given function to the contents of an object
- ab applies a given argument (wrapped in an object) to a function inside another object
- bind transforms the object by feeding its content to the given function
- pure wraps a regular value inside an object (whilst adhering to the 3 monad laws)