The Maybe applicative functor by Mark Seemann

An introduction to the Maybe applicative functor for object-oriented programmers.

This article is an instalment in an article series about applicative functors. Previously, in a related series, you got an introduction to Maybe as a functor. Not all functors are applicative, but some are, and Maybe is one of them (like list).

In this article, you'll see how to make a C# Maybe class applicative. While I'm going to start with F# and Haskell, you can skip to the C# section if you'd like.

F# #

A few years ago, I did the Roman numerals kata in F#. This is an exercise where you have to convert between normal base 10 integers and Roman numerals. Conversions can fail in both directions, because Roman numerals don't support negative numbers, zero, or numbers greater than 3,999, and Roman numerals represented as strings could be malformed.

Some Roman numbers are written in a subtractive style, e.g. "IV" means subtract 1 (I) from 5 (V). It's easy enough to subtract two numbers, but because parsing isn't guaranteed to succeed, I didn't have two numbers; I had two number options (recall that in F#, Maybe is called option).

How do you subtract one int option from another int option?

Both of these values could be Some, or they could be None. What should happen in each case? With Maybe, only four combinations are possible, so you can put them in a table:

You can do this with regular pattern matching, but it's hardly the most elegant solution:

// int option
let difference =
    match minuend, subtrahend with
    | Some m, Some s -> Some (m - s)
    | _              -> None

You could attempt to solve this with a specialised helper function like this:

module Option =
    // ('a -> 'b -> 'c) -> 'a option -> 'b option -> 'c option
    let map2 f xo yo =
        match xo, yo with
        | Some x, Some y -> Some (f x y)
        | _              -> None

which you could use like this:

let difference = Option.map2 (-) minuend subtrahend

It doesn't, however, generalise well... What if you need to operate on three option values, instead of two? Or four? Should you add map3 and map4 functions as well?

Making option an applicative functor addresses that problem. Here's one possible implementation of <*>:

// ('a -> 'b) option -> 'a option -> 'b option
let (<*>) fo xo =
    match fo, xo with
    | Some f, Some x -> Some (f x)
    | _              -> None

This enables you two write the subtraction like this:

let difference = Some (-) <*> minuend <*> subtrahend

For a detailed explanation on how that works, see the previous explanation for lists; it works the same way for Maybe as it does for List.

In the end, however, I didn't think that this was the most readable code, so in the Roman numeral exercise, I chose to use a computation expression instead.

Haskell #

In Haskell, Maybe is already Applicative as part of the language. Without further ado, you can simply write:

difference = pure (-) <*> minuend <*> subtrahend

As is the case with the F# code, I don't consider this the most readable way to express the subtraction of two integers. In F#, I ultimately decided to use a computation expression. In Haskell, that's equivalent to using do notation:

difference :: Maybe Integer
difference = do
  m <- minuend
  s <- subtrahend
  return $ m - s

While more verbose, I think it's clearer that one number is being subtracted from another number.

This works for Maybe because not only is Maybe Applicative, it's also a Monad. It's its monadness that enables the do notation. Not all applicative functors are monads, but Maybe is.

C# #

In a previous article you saw how to implement the Maybe functor in C#. You can extend it so that it also becomes an applicative functor:

public static Maybe<TResult> Apply<T, TResult>(
    this Maybe<Func<T, TResult>> selector,
    Maybe<T> source)
{
    if (selector.HasItem && source.HasItem)
        return new Maybe<TResult>(selector.Item(source.Item));
    else
        return new Maybe<TResult>();
}
 
public static Maybe<Func<T2, TResult>> Apply<T1, T2, TResult>(
    this Maybe<Func<T1, T2, TResult>> selector,
    Maybe<T1> source)
{
    if (selector.HasItem && source.HasItem)
    {
        Func<T2, TResult> g = x => selector.Item(source.Item, x);
        return new Maybe<Func<T2, TResult>>(g);
    }
    else
        return new Maybe<Func<T2, TResult>>();
}

As was the case for making sequences applicative in C#, you need overloads of the Apply method, because C#'s type inference is inadequate for this task.

If you have two Maybe<int> values, minuend and subtrahend, you can now perform the subtraction:

Func<int, int, int> subtract = (x, y) => x - y;
Maybe<int> difference = subtract.ToMaybe().Apply(minuend).Apply(subtrahend);

Like in F# and Haskell, applicative style is hardly the most readable way to express subtraction. It'd be nice if you could write it like Haskell's do notation. You can, but to do that, you must make Maybe a monad, and this isn't a monad tutorial. Mike Hadlow has a good monad tutorial for C# developers, the gist of which is that you must implement SelectMany in order to turn your generic type into a monad. For now, I'll leave this as an exercise for you, but if you add an appropriate SelectMany method, you'd be able to write the subtraction like this:

Maybe<int> difference =
    from m in minuend
    from s in subtrahend
    select m - s;

Again, I think this is more readable, but it does require that the type in question is a monad, and not all applicative functors are (but Maybe is).

Summary #

This article demonstrates that lists or sequences aren't the only applicative functors. Maybe is also an applicative functor, but more exist. The next article will give you another example.

Next: Applicative validation.

Comments

fun<string, string, string, string, string, string, string>(concat)

• ← Previous
• Archive
• Next →