Algebra of Functions, Part 3: Comprehensions

Query Comprehensions

In answer to a colleague recently: fluent method calls are primary; query comprehension syntax is the sugar.

We're talking about LINQ queries in C#, and what I'm saying is that this kind of thing,

from order in orderList
where order.Number == 123456
select order.Date;

gets transformed pronto into this kind of thing:

orderList
.Where(order => order.Number == 123456)
.Select(order => order.Date);

quite early in the compilation process. So early in fact that the bits between the from, where and select keywords, and the rest, are hardly analysed at all. In his Fabulous Adventures In Coding blog article, Query transformations are syntactic, Eric Lippert has some crazy fun with this situation.

Now, combine this fact with one from Part 2, where I briefly mentioned that LINQ's IEnumerable exemplifies the List monad, if you construe SelectMany as its Bind operation. You might then leap to the conclusion that any monad could be represented in this cool and sweet comprehension syntax. And you'd be right! Rather than composing our monadic functions using the After operation, we can simply rename the monad's Bind operation to SelectMany, and use much cooler, nested from clauses instead.

Comprehending a Monad

Let's rework the example of the Maybe monad more thoroughly. We'll get rid of that value type constraint by using this custom generic class to represent any type of data:

class Maybe<T>
{
  public T Value { get; private set; }
  public bool IsEmpty { get; private set; }
  public static readonly Maybe<T> Nil = new Maybe<T>();

  Maybe() { IsEmpty = true; }

  public Maybe(T value)
  {
    Value = value;
    IsEmpty = false;
  }

  public override string ToString()
  {
    return IsEmpty ? "<empty>"
      : Value == null ? "null"
      : Value.ToString();
  }
}

This extremely simple class just encapsulates a Value, of any type T, and an IsEmpty flag to indicate when the Value is absent. Note incidentally that we are allowing null as a value (assuming of course that T is a reference type).

Next, we rewrite Bind as SelectMany. Okay, actually there is a little more to it than that. You'll notice both Select and SelectMany methods below. The latter, accepting the extra function 'g', is just an optimization that C# insists on being present, to help it avoid an inefficient, too-deep nesting of lambdas. It's quite safe to ignore the details of this for our current purposes. Whatever your monad, just follow the pattern, and provide the extra method; it's needed to enable the use of comprehension syntax.

Oh, and one more thing I haven't mentioned yet. As well as a Bind operation, monads have a so-called Unit or Return operation, whose job is to amplify an unamplified value. Ours is named ToMaybe, and as you can see it simply calls the appropriate constructor.

static Maybe<U> Select<T, U>(this Maybe<T> t, Func<T, Maybe<U>> f)
{
  return t.IsEmpty ? Maybe<U>.Nil : f(t.Value);
}

static Maybe<V> SelectMany<T, U, V>(this Maybe<T> t, Func<T, Maybe<U>> f, Func<T, U, V> g)
{
  return t.Select(x => f(x).Select(y => g(x, y).ToMaybe()));
}

static Maybe<T> ToMaybe<T>(this T value)
{
  return new Maybe<T>(value);
}

That's all we need. Now we can reimplement those up and down functions from the previous example using our new generic class type, and build the climb composition using the awesomest comprehension syntax on the planet:

static void Main()
{
  Func<int, Maybe<int>>
    up =
      x => x < int.MaxValue ? (x + 1).ToMaybe() : Maybe<int>.Nil,
    down =
      x => x > int.MinValue ? (x - 1).ToMaybe() : Maybe<int>.Nil,
    climb =
      x => from y in up(x) from z in down(y) from w in down(z) select w;
  Console.WriteLine(" '{0}' '{1}' '{2}' ",
    climb(0), climb(int.MaxValue), climb(int.MinValue));
  // Displays '-1' '<empty>' '<empty>'
  Console.ReadKey();
}

Well, awesomest apart from the comprehension syntax of any fully functional language. But this is a C# series!