Skip to content

Instantly share code, notes, and snippets.

@ToJans
Created Oct 16, 2015
Embed
What would you like to do?
Function, Applicative, Monad in .Net - Failed post

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

@ToJans

This comment has been minimized.

Copy link
Owner Author

@ToJans ToJans commented Oct 16, 2015

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment