Lets build a monad library for C# - Introduction

I have done various C# pieces on monads and how C# LINQ is a monad engine. Thought I would put my money where my mouth is and build a monad library and explain the design decisions as I go.

In case you missed it I have covered what monads are and how they connect to LINQ Here.

In this introduction I will cover how the limitations of the C# Type system limit true generic abstractions for much of the code and also explain why I will be using Classes instead of Structs for the storage medium.

First up comes the limitations present in the C# type system. To cut to the chase, it lacks higher kinded types!

This digs into language theory a bit so I will cover the basics. C# has generics so you can do stuff like this.

public TResult CalculateResult<T, TResult>(T value) ...

This is a function that can perform a calculation on any type T and that results in a type TResult. The types are inferred when used.

Higher kinded types lift this abstraction a step further. Take the following signature.

public IEnumerable<TResult> 
    Map<T, TResult>(IEnumerable<T> toMap) ...

What if you wanted Map functionality on a range of wrapper types and the code was exactly the same for each of them. You might want to do something like.

public TWrapper<TResult> 
    Map<TWrapper, T, TResult>(TWrapper<T> toMap) ...

This is where C# falls down, you can't have TWrapper as a generic in this way. You can get close with huge hoop jumping but this makes the generic signature fugly as hell and kills a lot of the automatic type inference so that you need to specify all the generic types.

What does all this mean? It is simple really. You end up having to write functions like map and other common functions again and again even though they are exactly the same piece of code.

You just have to accept this, it is a limitation of the language.

Now we get to classes instead of structs for the monad container. I have been through this in my head so many times. Both have their advantages and problem.

Classes mean that when you have nested monads they are far more efficient when passing around as you are passing a reference instead of the entire monad stack. You can also use inheritance hierarchy to simulate union types. The problem is that until C# 8 (hopefully) reference types are nullable.

Structs make far more sense in this space. This is functional type code so the assumption is immutable state, more like value type semantics. They also can't be null so no mucking around with nulls, a good thing. The trouble is that once you nest monads you are blowing out the memory foot print and so passing them around can become an unacceptable cost.

I have battled with this in my head so much and have tried both paths in the past. In the end the class based approach wins. You just have to accept the contract that null monad references are invalid and will throw an exception. If you use LINQ then you already accept this sort of contract, just try using a null reference to a collection with LINQ. It uses an empty collection as nothing semantics instead.

If you are interested in the idea of the series let me know in the comment and also what experience you have with monadic abstractions. It will help to understand the level to aim at in the series :)

Happy coding

Woz