haskell

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

A basic for loop over the list can be done as follows.

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

We can now execute basic functions over our lists analogous to a loop.

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)

What right identity tells is that the result of binding the pure function yield is identical to the input (such a function is known as an identity function). To return to the world of C# the following should hold:

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

If we write down the steps we can derive what the pure function should yield:

-- 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)

So now the rather trivial implementation is the only thing that awaits us:

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

Also very interesting is the ease with which we can compute the Cartesian product of two list:

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

And while the syntax of both the application and its use may not be very appealing, I also present the list comprehension:

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

A function that has found popularity in many mainstream languages is zip: it takes to lists and returns one new list with tuples containing the respective elements of the two lists. for example:

-- 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)]

In haskell you could define zip yourself as follows:

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

But of course nothing can now stop us from doing the exact same in our C# project:

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)

Finally we have shortly seen how these functions can be utilized and combined to implement more complicated functions in an intuitive, bug resistant manner.

last modified: May 29, 2023 at 13:07