Logo

C#
haskell

C# can be functional pt1: The Maybe Monad

Functional Programming? That's like map right?

The fact that people start reading blog posts about functional programming can nowadays no longer solely be attributed to being an enthusiastic type-theorist. Transformations like map, filter, or even reduce have found their way into many well known programming languages like python, javascript, C# or even C++. Look at the examples below showing how to increment every element in a list and filter out only the even numbers. oneMore will always be [2,3,4,5,6] and even [2,4].

const input = [1,2,3,4,5];
const oneMore = input.map(x => x+1);
const even = input.filter(x => x%2 == 0);

input = [1,2,3,4,5]
# we use list() to force evaluation since map and
# filter return generators.
oneMore = list(map(lambda x: x+1, input))
even = list(filter(lambda x: x%2 == 0, input))
# Can also be done with list comprehensions
oneMore = [x+1 for x in input]
even = [x for x in input if x%2==0]
# Notice how you could do map and filter
# in one list comprehension?

// Yes SQL is actually a simple functional language!
using System.Linq;
var input = new List<int> { 1, 2, 3, 4, 5 }
var oneMore = input.Select(x => x+1);
var even = input.Where(x => x%2 == 0);
// Do note that oneMore and even are both
// of type IEnumerable<int> are in fact
// lazy loaded. 

#include <vector>
#include <algorithm>

int main()
{
  auto input = std::vector<int> {1,2,3,4,5};
  auto oneMore = std::vector<int>(5);
  std::transform(
      input.begin(), // First element
      input.end(),   // Last element
      oneMore.begin(),  // First element of destination
      [](int x){return x+1;});

  // Notice how we had to guess that
  // the result had 2 elements?
  auto even = std::vector<int>(2);
  std::transform(
      input.begin(),
      input.end(),
      even.begin(),
      [](int x){return x%2==0;});
  return 0;
}

--This syntax only works in the interpreter
input = [1..5]
oneMore = map (+1) input
even = filter (\x -> x%2==0) input

But having witnessed the power of one the first truly functional languages: haskell, I wonder: "Is this all we can learn from it?" It has taken me many frustrating hour to finally grasp the concepts of Functors, Applicatives, and Monads. However, now that I do I find them so intuitive and useful, I miss them in my imperative world. Let's see if we can learn what they are whilst rebuilding them in C#.

Maybe: Security through insecurity

If you have ever written code you must have found yourself in situation were you wrote a function that pretty much always worked but there were a few edge cases. "Oh well lets just return None/null/.. and check for it later. I hope I don't have to remind you how that story ends, and yes, always.

Alright, so what do we do when we can't always obtain an answer? What can we say about the result? Imagine we have a function that converts the character of a digit to the actual integer, so 0-9. A beginning haskeller might find him or herself with the following dilemma: what if it is not a character of a digit? Should we return a standard value or throw an error. Perhaps leave a handy comment as well?

import Data.Char

--DON'T PUT IN CHARACTERS THAT ARE NOT DIGITS THANK YOU PLEASE!
toDigit :: Char -> Int
toDigit c
  | o >= 48 && o <= 57 = o-48
  --Do it like this?
  | otherwise = 0
  -- Mmm, what about this:
  | otherwise = error "Given char was not a digit"
    where o :: Int
          o = ord c

I hope I don't have to tell you that this is not good. Nobody will read your handy comments until the production server has crashed and nobody expected that such a simple function would ever throw an error. And if you were to return 0 you would likely be held liable for the psychiatry expenses of the poor fella who on the seventh day finally realised what was causing that damned damned bug.

Alright, so our function doesn't always work... How do we communicate that effectively to our fellow programmers? Well, if we also communicate it through the compiler they will know for sure; you can tell them directly but telling mommy is more effective. Enter Maybe, our lord and saviour who is wisest for not knowing.

--Put in whatever you want!
toDigit :: Char -> Maybe Int
toDigit c
  | o >= 48 && o <= 57 = Just (o-48)
  | otherwise = Nothing
    where o :: Int
          o = ord c

Okay, so our answer is wrapped in a Maybe, it is either Nothing or Just a value. But how do we get rid of it again when we want to do something with?

toDigitPlusOne :: Char -> Maybe Int
toDigitPlusOne c = case toDigit c of
    Nothing -> Nothing
    Just x -> Just (x+1)

Mmm, okay, but afterwards we stop it back in a Maybe. Does that mean we can never really get rid of it? Well kinda, perhaps higher up in the program it can be a good idea to choose functionality based on Nothing or Just, both leading to valid outcomes. In general however you will have to respect the fact that depending on a Maybe value, makes you a Maybe value. If you have seen a lot of NullReferenceExceptions in your C# programs you must be excited to have the compiler tell you where you can prevent this. (Huray, C# 8 now has types that are non-nullable by default, to lose nullable types you have to check for null, just like Maybe! documentation)

While C# 8 is a long way from being the standard, let's see if we can implement this in the C# environment of today. First, let's have a look at how Maybe is defined in haskell.

--Maybe is a called a datatype, Nothing and Just are
--called its instances. The 'a' refers to the type
--inside, which is not specified.
data Maybe a = Nothing | Just a

We can actually translate this quite well to C#. We can attribute the same type to Nothing and Just by letting them inherit from an abstract Maybe class. The generic type idea is also well known in C#:

abstract class Maybe<T>
{
}

class Nothing<T> : Maybe<T>
{
}

class Just<T> : Maybe<T>
{
  // Making this property public is not at all
  // a strange idea, if you can read the property means
  // you have already asserted that you're al dealing
  // with a just as opposed to a Nothing.
  public T Value { get; set; }

  public Maybe(T value)
  {
    Value = value;
  }
}
full source

In haskell, people have accustomed themselves to concept of pattern matching, basically a big if else if else chain to assert what we are dealing with:

getDigitDescription :: Char -> String
getDigitDescription c = case toDigit c of
    Nothing -> "Given character is not a digit"
    Just x  -> "Given character is the digit " ++ show x

Perhaps a bit less well known but this can be done pretty much verbatim in C# with the age old switch statement:

public string GetDigitDescription(char c) {
  Maybe<int> result = toDigit(c);
  switch(result)
  {
    case Nothing n: 
      return "Given character is not a digit"
    case Just<int> j: 
      return "Given character is the digit " + j.Value.toString();
  }
}

Maybe is so much more than that

This is the part where it gets really interesting and the use of complicated words increase. We're going to attribute 3 titles to Maybe that we later will learned are also attributed to many other Haskell datatypes:

We will go into great detail about what these properties mean, why we care and if we can reproduce them in C#.

1. Functor

You can already imagine that it will become quite cumbersome to constantly repeat that switch statement all throughout the codebase to gain back information about the result. This is were a functor can help you. Let me throw you in the deep by giving three equivalent functions, the first without using functors, the latter two with.

-- Let's assume we have this function, it cannot 
-- answer if the second argument is 0 and therefore 
-- returns a Maybe value.
isDivisbleBy :: Int -> Int -> Maybe Bool

isNotDivisbleBy :: Int -> Int -> Maybe Bool
isNotDivisbleBy a b = case isDivisbleBy a b of
    Nothing -> Nothing
    Just x  -> Just (not x)

isNotDivisbleBy' :: Int -> Int -> Maybe Bool
isNotDivisbleBy' a b = fmap not (isDivisbleBy a b) 

isNotDivisibleBy'' :: Int -> Int -> Maybe Bool
isNotDivisibleBy'' a b = not <$> isDivisbleBy a b

Alright, let's break it down. To be a Functor means nothing more than having implemented the function 'fmap' which can also be used as an operator under the alias '<$>', the only difference is the location of the arguments. Let's see what fmap's type tells us:

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

-- Let's translate that to the Maybe Functor specificially

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

So what fmap does is given a function from (a -> b) and a Maybe containing an 'a', it returns a new Maybe containing a 'b' (Explaining haskell orally is a tough experience). All it does is just wrap that strenuous switch statement. It is nothing more than syntax sugar! We can do this too in C#. Now it might seem obvious to implement this via inheritance and abstract methods, but I prefer to use extension methods, this will allow us to explicitly pattern match, just like we do in haskell. In the future it will also prove very useful for saving a lot of typing by having a catch clause if the behavior is the same for many instances.

public static Maybe<TOut> fmap<TIn, TOut>(
               this Maybe<TIn> maybe, 
               Func<TIn, TOut> func)
{
  switch(maybe)
  {
    case Nothing<TIn> _: 
      return new Nothing<TOut>();
    case Just<TIn> just: 
      return new Just<TOut>(func(just.Value));
    default: 
      throw new Exception("Don't inherit from Maybe yourself!!!");
  }
}

// Let's do it the other way around as well!
public static Maybe<TOut> fmap<TIn, TOut>(
               this Func<TIn, TOut> func)
               Maybe<TIn> maybe)
{
  return maybe.fmap(func);
}
full source

Now returning to our original function, we can do it like haskell:

public void Maybe<bool> IsNotDivisbleBy(int a, int b)
{
  return (x => !x).fmap(IsDivisbleBy(a, b));
}

2. Applicative

To be an applicative means, just like being a functor, nothing more that implementing a function. In this case 'liftA2'. A less general version, but much more commonly used is the operator <*> = liftA2 id. We will focus on <*> (called ab) for now.

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

--Again, let's tranlate that to specifically Maybe

(<*>) :: Maybe (a -> b) -> Maybe a -> Mabye b

This looks very familiar to fmap, the only difference is that the function is contained in the Maybe. You might ask yourself why anyone would put that function inside a Maybe. The reason for this is actually fmap. To understand how fmap does that we must first understand haskell's notion of partially applied functions:

plus :: Int -> Int -> Int
plus a b = a + b

-- Plus one is simply a weaker version of the more generic plus
plusOne :: Int -> Int
plusOne = plus 1

-- Giving a function it's non-last argument simply yields a 
-- new function with one argument less.

No let's look back at fmap:

(<$>) :: (a -> b) -> Maybe a -> Maybe b

plus <$> :: Maybe a -> Maybe b
plus <$> (Just 1) :: Maybe (Int -> Int)

-- (a -> b) means any a to any b. In our case:
-- a :: Int
-- b :: Int -> Int (Just like with plusOne)

And that is how our function ends up inside a Maybe. But if now want to supply the second argument to our function we cannot do that with fmap anymore. This is where our Applicative property comes in handy.

(<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b

plus <$> Just 1 :: Maybe (Int -> Int)

-- Do see the similarity? ^

plus <$> Just 1 <*> Just 2 :: Maybe Int

After fmap'ing one Maybe argument into a normal function we can use <*> to pipe in the other arguments. We now are able to perform what are known as compositions!

meh :: Int -> Maybe Int

getTwoNumbers :: Int -> Int -> Maybe (Int, Int)
getTwoNumbers a b = (,) <$> meh a <*> meh b

Let's see if we can do this in C#:

public static Maybe<TOut> ab<TArg, TOut>(
      this Maybe<Func<TArg, TOut>> maybe, 
      Maybe<TArg> maybe_arg)
{
    switch (maybe)
    {
        case Nothing<Func<TArg, TOut>> _: return new Nothing<TOut>();
        case Just<Func<TArg, TOut>> just:
            switch (maybe_arg)
            {
                case Nothing<TArg> _: return new Nothing<TOut>();
                case Just<TArg> arg:
                    return new Just<TOut>(just.Value(arg.Value));
                default: throw new Exception("Do not derive from Maybe yourself!");
            }
        default: throw new Exception("Do not derive from Maybe yourself!");
    }
}
full source

Now to top at all of, the plus with composition function in C#!

public static class PlusDemo
{
    /// <summary>
    /// Returns a nested function, this way we can apply
    /// arguments one by one.
    /// </summary>
    public static Func<int, Func<int, int>> Plus()
    {
        return x => y => x + y;
    }

    public static Maybe<int> SometimesValue()
    {
        return new Just<int>(5);
    }

    public static Maybe<int> Demo()
    {
        return Plus().fmap(SometimesValue()).ab(SometimesValue());
    }
}
full source

3. Monad

And for our grand finale... The most complicated thing in our known universe, harder than quantum mechanics: Monads! Actually that's not true, just like Functor and Applicative, to be a Monad just means having implemented a function, or 2 in this case. Let's meet them:

(>>=) :: Monad m => m a -> (a -> m b) -> m b
(return) :: Monad m => a -> m a
pure = return

-- Again, specifically for Maybe
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
(return) :: a -> Maybe a

Now this is where it gets confusing for most people. First let's acknowledge the fact that we have muddied the waters by using the word return. So let's be loud and clear about the following:

return in haskell has absolutely nothing to do with the return in C#!!!

With the damage already done, I can also say that haskell has an operator named 'pure' which does exactly the same thing. In our C# implementation we will use that word to make things less ambigious.

So this weird (>>=) operator, what does it do? First all, that operator is called bind and many would say is the most powerful operator in functional languages. What it does is again not that complicated. Give it a function and it will decide for you whether it can actually execute it. This very similar to fmap except that the function we provide already returns an instance of that same monad, i.e. Maybe. This allows us to go in, evaluate the value and return a new instance of that monad.

destroyIfEven :: Maybe Int -> Maybe Int
destroyIfEven input = case input of
    Nothing -> Nothing
    Just x -> if (even x) then Just x else Nothing

-- But now much shorter with bind!

destroyIfEven' :: Maybe Int -> Maybe Int
destroyIfEven' input = input >>= \x ->
    if (even x) then Just x else Nothing

Alright, that's all cool and dandy, but where does 'pure' or 'return' come in? Well, just like its type signature reveals, it simply takes a normal value in puts in a monad. For Maybe that operation is not that hard to imagine... We can just put it in a Just! And yes, that is what happens, pure for Maybe is simply the Just constructor. We could have more generally written:

destroyIfEven'' :: Maybe Int -> Maybe Int
destroyIfEven' input = input >>= \x ->
    if (even x) then pure x else Nothing

A keen reader may recognize that this is actually very similar to Promises in javascript. And indeed that is very correct! In haskell we even have something similar to callback hell. Luckily there is more syntax sugar for that, but that's for another time. Let's do it in C#:

public static Maybe<TOut> bind<TIn, TOut>(
    this Maybe<TIn> maybe,
    Func<TIn,Maybe<TOut>> func)
{
    switch (maybe)
    {
        case Nothing<TIn> _: return new Nothing<TOut>();
        case Just<TIn> just: return func(just.Value);
        default: 
          throw new Exception("Do not derive from Maybe yourself!");
    }
}

public static Maybe<T> pure<T>(this T value)
{
    return new Just<T>(value);
}
full source

No let's see what our 'destroyIfEven' were to look like:

public static Maybe<int> DestroyIfEven(Maybe<int> input)
{
    return input.bind(x => x % 2 == 0 
        ? new Nothing<int>() 
        : x.pure());
}
full source

Pretty gnarly no?

Functions are not methods

When OO programmers talk to each other, these words are often used interchangeably. This is understandable because in languages as C# there is not really a clear cut difference. You could argue that a function is something that depends only on it's input: something that is known as pure function. But hey, are all functions then pure? Then why was the word invented?

When people describe haskell they often say "Everything is function!". What they mean is that there no such thing as statements. You cannot say: "Execute this function right now." The only thing you can do is describe the transformation of objects. For example the DestroyIfEven function describes a transformation to something else. Whilst this all sounds very restrictive, it actually allows you to very intuitively compose larger and larger transformations until you can do something very useful. The great thing is that the compiler can help you way better with ensuring everything is working, allowing to build far less error prone code.

Summary and Conclusion

We looked at how we can port the concept of functions that may or may not succeed to C#. We then looked at what other properties the Maybe has in haskell to see if we can bring back more. As a result of that we now have a C# class that can arguably be called an Applicative Functor, as well as a Monad.

Of course we haven't made C# adhere to the same guarantees that haskell gives us, but I think it's interesting to see that are a lot more ingenious concepts to borrow from functional languages than is currently often done.

Despite the success, the main purpose of this experiment was not to improve C#, but to learn about Functors, Applicatives and Monads using tools we are already familiar with. In part 2 we will be looking at how we can create a linked list in C#, which is, just like Maybe, also an Applicative Functor and a Monad.

last modified: Aug 23, 2020 at 17:32