Functors and Monads

Functors are containers that have value(s) and if you apply a function to that value(s) you get the same kind of container with the value(s) inside of it transformed. Any type that has defined Map/Select function is a functor. We can generalize the signature of Map like:

Map: (C<T>, (T -> R)) -> C<R>

Map is a function that takes a generic container that wraps inner value of type T and a function f that transforms T to R and returns a container C<R> wrapping the value after applying f to the container's inner value.

List, Enumerable, Dictionary are just a few examples of functors in C#.

Functor laws:

• functors must preserve identity – if the values in the functor are mapped to themselves the result must be an unmodified functor.
  functor.Select(x => x) == functor
  
  [TestMethod]
public void PreserveIdentity()
{
Func<int, int> id = x => x;
IEnumerable<int> seq = Enumerable.Range(1, 10);

CollectionAssert.AreEqual(
seq.ToList(),
seq.Select(id).ToList());
}
• functors preserve composition – the result of two mapping operations performed one after the other should be the same as to applying the first function to the result of the second.
  functor.Select(x => f(g(x))) == functor.Select(g).Select(f)
  
  [TestMethod]
public void PreserveComposition()
{
Func<int, string> g = x => x.ToString();
Func<string, string> f = x => x.ToUpper();
IEnumerable<int> seq = Enumerable.Range(1, 10);

CollectionAssert.AreEqual(
seq.Select(g).Select(f).ToList(),
seq.Select(x => f(g(x))).ToList());
}

Advantage of using functors is that the value is abstracted away in container. Also, you can chain Map calls, because the Map function returns another functor.

Monad is just a generic container C<T> that has two particular functions defined on it – Return and Bind.

• Return: T -> M<T>
• Bind: (M<T>, (T -> C<R>)) -> C<R>

Return function wraps a normal value lifting it into monadic value. Normal values are int, bool, string, etc., while elevated values are Option<T>, Enumerable<T>, Observable<T> etc.

For example, we can define Return for IEnumerable like:

public static IEnumerable<T> Return<T>(params T[] ts)
=> ts.ToList();

Bind takes a monadic value and a function that can transform the value, and returns a new monadic value. Another way to think of Bind is that it is a two parameter function that takes an elevated value M<T> and a function T -> C<R> and returns a new elevated value C<R>. This is done by unwrapping the value and running the function T -> C<R> against it.

Resources:

• Functional Programming in C# - Enrico Buonanno
• Functor - HaskellWiki
• Understanding map and apply | F# for fun and profit