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

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;
  }
}

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

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:

• Functor
• Applicative
• Monad

1. Functor

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

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);
}

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

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.

(<$>) :: (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)

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

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

-- Do see the similarity? ^

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

meh :: Int -> Maybe Int

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

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!");
    }
}

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());
    }
}

3. Monad

(>>=) :: 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

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

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);
}

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

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.