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:

Some x None
Some y Some (x - y) None
None None None
Only if both values are Some cases should you return a Some case with the result of the subtraction; in all other cases, you should return None.

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 fSome 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<TTResult>(
    this Maybe<Func<TTResult>> 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<T2TResult>> Apply<T1T2TResult>(
    this Maybe<Func<T1T2TResult>> selector,
    Maybe<T1> source)
{
    if (selector.HasItem && source.HasItem)
    {
        Func<T2TResult> g = x => selector.Item(source.Item, x);
        return new Maybe<Func<T2TResult>>(g);
    }
    else
        return new Maybe<Func<T2TResult>>();
}

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

Tyson Williams
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.

I think we agreed that the issue is not C#'s weak type inference but its lack of default function currying? My guess is that you wrote this quoted part of this article before my comment on your previous article.

2018-11-06 02:44 UTC

Tyson, thank you for writing.

"My guess is that you wrote this quoted part of this article before my comment on your previous article."
Yes, June 27, 2017, in fact...

You're correct that this particular issue is related to the uncurried nature of C# methods.

I do, however, maintain that C#'s type inference capabilities are weaker than F#'s or Haskell's. To be clear, I view this as the result of priorities. I don't think that the people who designed and wrote the C# compiler are less skilled than the designers of F# or Haskell. The C# compiler has to solve many other problems, such as for example overload resolution, which is a language feature in direct opposition to currying. The C# compiler is excellent at overload resolution, a task with which the F# compiler sometimes struggle (and is not even a language feature in Haskell).

Your comment is, however, a reminder that I should consider how I phrase such notions in the future. Thank you for pointing that out. As I'm publishing and get feedback, I constantly learn new things. I'm always grateful when someone like you take the time to educate me.

I'll see if I can improve in the future. I do, however, still have a backlog of articles I wrote months, or even more than a year, ago, so it's possible that more errors escape my attention when I proof read them before publication. If that happens, I'll appreciate more corrections.

2018-11-06 7:30 UTC
Tyson Williams

Thank you very much for your kind reply. I agree with everything you said.

I will expand my comment a bit to give a clearer picture of my understanding.

First, very little is "needed"; most things are merely sufficient. In particular, we don't need to overload your Apply method to achieve your goal. As I mentioned before, it sufficies to have a single Apply method and instead create overloads of a function called curry that explicitly curries a given function. Furthermore, I think there is a sense in which this latter approach to overcome the lack of default currying is somehow minimal or most abstract or most general.

Second, compared to languages like F# or Haskell, type inference is definitely weaker in C#. This issue was also present (in a subtle way) in your previous article, but I decided to largely ignore it in order to keep my comment more focused. In your previous article, you expliciltly defined the local variable concat like this

Func<stringstringstringstringstringstringstring> concat =
    (x, y, z, æ, ø, å) => x + y + z + æ + ø + å;
In particular, you explicitly told the C# compiler that the type of all of these six variable is string. That part was necessary; the type inference in C# is not strong enough to innfer (possibily in some use of concat) that the types could be string.

Suppose instead of defining concat as a local variable (with Func<stringstringstringstringstringstringstring> as its type) you had defined it as a member method on a class. Then its type in C# is some kind "method group". The method group of a method essentially corresponds to the set of methods containing itself and its overloads. Then in order to pass concat into curry, there needs to be a type conversion (or cast) from its method group to Func<stringstringstringstringstringstringstring>. This is also something that the C# system cannot do, and so Language Ext has overloads of a function called fun to do this explicitly. Using it on our hypothetical member function concat would look like

fun<stringstringstringstringstringstringstring>(concat)
Again, I think there is a sense in which this explicit way to specify non-inferable types is somehow minimal or most abstract or most general.

My impression is that there is some low hanging fruit here for strengthing the type inference of the C# compiler. If a method group correpsonds to a singleton set (and that method has no ref or out arguments), then I would think it would be straight forward to consider an implicit cast from the method group to the corresponding Func or Action delegate.

2018-11-06 15:31 UTC


Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

Published

Monday, 29 October 2018 06:17:00 UTC

Tags



"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!