Function, Applicative, Monad in .Net - Failed post

post.md

+++ Description = "" Tags = ["Development", "Haskell", "C#", "CSharp"] date = "2015-10-16T09:24:25+02:00" menu = "main" title = "Haskell concepts in C#"

+++

I've made numerous attempts to explain functors, applicatives, monads and the likes in .Net, and here is another one:

Functor

From the Haskell docs

The Functor class is used for types that can be mapped over. Instances of Functor should satisfy the following laws:

fmap id  ==  id
fmap (f . g)  ==  fmap f . fmap g

Minimal complete definition:

   fmap :: (a -> b) -> f a -> f b

Let's implement a Functor in C# for a List:

public class ListFunctor
{
    public static List<Tb> FMap<Ta, Tb>(Func<Ta, Tb> mapper, List<Ta> list)
        => list.Select(mapper).ToList();
}

We can prove that this ListFunctor respects the Functor laws; first we define some helper classes and functions:

public static class Assert
{
    public static void That(String msg, bool pred)
    {
        if (pred) throw new Exception("Assertion failed: " + msg);
    }

    public static void Against(String msg, bool pred)
    {
        That(msg, !pred);
    }
}

// a function that returns the parameter it received; `id` in Haskell
public static Ta Id<Ta>(Ta x) => x;

// a function that composes two functions into a new function, `(.)` in Haskell
public static Func<Ta, Tc> Dot<Ta, Tb, Tc>(Func<Ta, Tb> fst, Func<Tb, Tc> snd)
{
    return x => snd(fst(x));
}

and then we can check the laws:

 List<int> list = new List<int>(new int[] { 1, 2, 3 });
 Func<int, bool> f = x => x > 2;
 Func<bool, String> g = x => x.ToString();

 Func<List<int>, List<bool>> fmapF = l => ListFunctor.FMap(f, l);
 Func<List<bool>, List<String>> fmapG = l => ListFunctor.FMap(g, l);

 /// verify the functor laws
 Assert.That("fmap id = id",
             ListFunctor.FMap(Id, list) == Id(list));

 Assert.That("fmap (f.g) = fmap f . fmap g",
              ListFunctor.FMap(Dot(f, g), list) ==
              Dot(fmapF, fmapG)(list));

Applicative

From the Haskell docs:

class Functor f => Applicative f where Source

A functor with application, providing operations to

• embed pure expressions (pure), and
• sequence computations and combine their results (<*>).

Let's implement an Applicative in C# for a List:

public class ListApplicative : ListFunctor
{
    public static List<Ta> Pure<Ta>(Ta v)
        => new List<Ta>(new Ta[] { v });

    // In haskell the sequence is expressed as the operator "<*>"
    public static List<Tb> Sequence<Ta, Tb>(List<Func<Ta, Tb>> mappers, List<Ta> lista)
        => mappers.SelectMany(m => FMap(m, lista)).ToList();
}

and then we can check the laws:

// verify the applicative laws

var v = new List<String>(new String[] { "abc", "def" });
var u = new List<String>(new String[] { "red", "green", "blue" });
var w = new List<String>(new String[] { "apple", "tomato" });

var pureIdString = ListApplicative.Pure<Func<String, String>>(Id);
Assert.That("pure id <*> v = v",
        ListApplicative.Sequence(pureIdString, v) == v
    );

Assert.That("pure(.) < *> u < *> v < *> w = u < *> (v < *> w)",
    THERE_IS_NO_NEED_TO_VERIFY_BECAUSE_IT_IS_ANNOYING_AS_HELL_IN_CSHARP);

As I was trying to prove law #2, I just gave up, as it turned out to be a major nuisance in C#.

Monad

From the Haskell docs:

class Applicative m => Monad m where Source

The Monad class defines the basic operations over a monad, a concept from a branch of mathematics known as category theory. From the perspective of a Haskell programmer, however, it is best to think of a monad as an abstract datatype of actions. Haskell's do expressions provide a convenient syntax for writing monadic expressions.

I agree this isn't very obvious, but for now let's just implement it in C#

public class ListMonad : ListApplicative
{
    public static List<Ta> Return<Ta>(Ta instance) => Pure(instance);

    // In haskell the bind is expresssed as the operator ">>="
    public static List<Tb> Bind<Ta, Tb>(Func<Ta, List<Tb>> mapper, List<Ta> list)
        => list.SelectMany(a => mapper(a)).ToList();
}

Usage

Here's an example that generates a little story:

Func<String,Func<String,List<String>>> newList = parts => (s => new List<String>(parts.Split(';').Select(x => s + x)));

var story =
    ListMonad.Bind(newList("Sue;Chris;Ichi"),
    ListMonad.Bind(s => ListMonad.Return(s + " named "),
    ListMonad.Bind(s => ListMonad.Return(s + " - yes," + s.Split(',')[1].ToUpper() + " -"),
    ListMonad.Bind(newList(" girl; boy; wizard"),
    ListMonad.Bind(newList("a small;a little;an average"),
    ListMonad.Bind(s => ListMonad.Return(s + ", there was "),
    ListMonad.Bind(newList("Once upon a time;A long time ago"),
    ListMonad.Return("")
    )))))));

All those parens, I give up

Please note that even the assert class is wrong! So don't take this as the truth!!!