Monads, part seven

Posted on by

Srinivasa Ramanujan - OPC - 2Way back in 1992 I was studying linear algebra at Waterloo. I just could not seem to wrap my head around dual spaces. Then one night I went to sleep after studying algebra for several hours, and I dreamed about dual spaces. When I awoke I had a clear and intuitive understanding of the concept. Apparently my brain had decided to sort it all out in my sleep. It was a bizarre experience that never happened again.[1. Unfortunately I no longer have an intuitive understanding of dual spaces, having not used anything more than the most basic linear algebra for two decades. I’m sure I could pick it up again if I needed to, but I suspect that the feeling of sudden clarity is not going to be regained.] History is full of examples of people who had sudden insights that solved tricky problems. The tragically short-lived mathematician Srinivasa Ramanujan claimed that he dreamed of vast scrolls of mathematics, most of which turned out to be both correct and strikingly original.

There is of course a difficulty with waiting for a solution to appear in a dream: you never know when that’s going to happen. Since insight is unreliable, we’ve developed a far more reliable technique for solving tough problems: recursive divide and conquer. We solve problems the same way that a recursive method solves problems:

Is the current problem trivial? If so, solve it. Otherwise, break the current problem down into one or more smaller problems. Recursively solve the smaller problems and then compose those solutions into a solution to the larger problem.

It’s “composition” that I want to talk about today. Composition is the act of combining two or more solutions to smaller problems into a single abstraction that solves a larger problem. We do this so often when writing computer programs, it’s like the air we breathe. It’s all around us but we don’t think about it that often. Here we have a composition of two properties with an operator; the result of the composition is a third property:

public double Area
{
  get { return this.Length * this.Width; }
}

And of course whatever Rectangle type this is has probably composed two values of Point type for the corners, which have in turn composed two double values for the coordinates, and so on. All the mechanisms of a modern, pragmatic programming language are there to make it easy to compose solutions to smaller problems into solutions of larger problems.

Thus there are an enormous number of different kinds of composition available to C# programmers. Today I want to talk about a very specific kind of composition: composition of non-void functions of one parameter. This is one of the most basic of compositions.[1. Well, arguably the composition of two void functions of no parameters into a third is even more basic; you can’t get much simpler than void M() { A(); B(); }.] As a silly illustrative example, if you have:

static long Cube(int x) { return (long)x * x * x; }
static double Halve(long y) { return y / 2.0; }

then you can always make a third function that composes these two:

static double HalveTheCube(int x) { return Halve(Cube(x)); }

Typically when we write programs, the program text itself describes a whole pile of compositions, each rather more complex than these simple function-of-one-parameter compositions. But we can also perform function compositions dynamically if we want to, using delegates:

Func<int, long> cube = x => (long)x * x * x;
Func<long, double> halve = y => y / 2.0;
Func<int, double> both = z => halve(cube(z));

And in fact, we could even make a method that does it for us:

static Func<X, Z> Compose<X, Y, Z>(
  Func<X, Y> f,
  Func<Y, Z> g)
{ 
  return x => g(f(x));
}

And then we could say:

Func<int, long> cube = x => (long)x * x * x;
Func<long, double> halve = y => y / 2.0; 
Func<int, double> both = Compose(cube, halve);

Of course you would never actually do that, because function composition has such a lovely syntax already in C#. But logically, this is what you are doing every time you write a program where the result of one function is fed into the next: you are composing the two functions into a third.

Notice that of course in order to be composed, the return type of the “inner” function must be implicitly convertible to the parameter type of the “outer” function. Which brings us back to the topic at hand: the final rule of the monad pattern for types. We’ve been talking about “special” functions that return an instance of a monadic type. Suppose we have two such functions:

Func<int, Nullable<double>> log = x => x > 0 ? 
  new Nullable<double>(Math.Log(x)) : new Nullable<double>();
Func<double, Nullable<decimal>> toDecimal = y => Math.Abs(y) < decimal.MaxValue : 
  new Nullable<decimal>((decimal)y) : new Nullable<decimal>(); 
Func<int, Nullable<decimal>> both = Compose(log, toDecimal);

That doesn’t work. toDecimal takes a double, but log returns a Nullable<double>. What do we want to happen? Clearly we want to say that the result of the composed functions is null if log returns null, and otherwise passes the underlying value along to toDecimal. But we already have a function that does precisely that: ApplySpecialFunction! And therefore we can build a monadic composition helper:

static Func<X, Nullable<Z>> ComposeSpecial<X, Y, Z>(
  Func<X, Nullable<Y>> f,
  Func<Y, Nullable<Z>> g)
{ 
  return x => ApplySpecialFunction(f(x), g);
}

Now we can say:

Func<int, Nullable<decimal>> both = ComposeSpecial(log, toDecimal);

The ApplySpecialFunction helper method enables us to apply any function to a monadic type, which is awesome. But in doing so it also enables us to compose any two functions that return that type!

I said last time that we were finally going to get to the last rule of the monad pattern, and at long last we’ve arrived. The last rule is: the ApplySpecialFunction helper must ensure that composition works. In code:

Func<X, M<Y>> f = whatever;
Func<Y, M<Z>> g = whatever;
M<X> mx = whatever;
M<Y> my = ApplySpecialFunction(mx, f);
M<Z> mz1 = ApplySpecialFunction(my, g);
Func<X, M<Z>> h = ComposeSpecial(f, g);
M<Z> mz2 = ApplySpecialFunction(mx, h);

We require that mz1 and mz2 be semantically the same. Applying f to some value and then applying g to the result must be logically the same as first composing f with g and then applying the composition to the value.[2. Again, we do not require referential identity, though that’s great if you can get it. But semantic identity is required.]

Finally we’ve got all the small details taken care of and we can correctly describe the monad pattern in C#:

A monad is a generic type M<T> such that:

  • There is some sort of construction mechanism that takes a T and returns an M<T>. We’ve been characterizing this as a method with signature
static M<T> CreateSimpleM<T>(T t)
  • Also there is some way of applying a function that takes the underlying type to a monad of that type. We’ve been characterizing this as a method with signature:
static M<R> ApplySpecialFunction<A, R>(
  M<A> monad, Func<A, M<R>> function)

Finally, both these methods must obey the monad laws, which are:

  • Applying the construction function to a given instance of the monad produces a logically identical instance of the monad.
  • Applying a function to the result of the construction function on a value, and applying that function to the value directly, produces two logically identical instances of the monad.
  • Applying to a value a first function followed by applying to the result a second function, and applying to the original value a third function that is the composition of the first and second functions, produces two logically identical instances of the monad.

Whew! And now perhaps you see why I started this series all those weeks ago with the idea of exploring the pattern by looking at examples, rather than starting in with the monad laws.

Next time on FAIC I’ll explain what these mechanisms are more traditionally called.

The information for Ramanujan’s passport photo can be found on Wikimedia Commons.

24 thoughts on “Monads, part seven”

  1. I’ve been following along from the beginning and I’ve understood everything that’s been said. At some point in this journey I should have had a moment of enlightenment which led me to see that, wow I can do this, that, and these other useful things with Monads. That has not happened.

    I’m hoping there will be a part (nine?) which demonstrates why, as a C# programmer, I should care about Monads.

    Reply ↓

    • Others may have a different answer, but for me learning about Monads opened up the world of more expressive type systems. A real turning point was realizing what C# could not express and Haskell type classes could express. Then discovering what Haskell’s type system cannot express or enforce. With this richer picture of the world of computation I feel I became a much better C# programmer. I now had names for more concepts and could reason about those concepts with concrete laws (something that is hard to do with just a perspective of “design pattern”). More and more of my design work (in C#) was a matter of writing down Haskell types and seeing where things went wrong or discovering some new and profound way of looking at the problem because. Often these new perspectives were implied by algebraic transformations of the types.

      Reply ↓

    • I would also like to see a post about that. Monads sound interesting and your explanation has been wonderfully clear, but the syntax is ugly in C# and we’ve been using the existing monadish types (like IEnumerable) without the monad pattern. Perhaps this is a failure of my imagination, but is there something great that the monad pattern can accomplish in C# that outweighs its ugly syntax? Is it simply that designing types that could be used with the monad pattern helps avoid creating certain leaky abstractions? Or is it all just academic? 🙂

      Reply ↓

      • But the syntax in C# 3 is beautifully clear, it is:

            from a in x
    from b in f(a)
    select b

        That’s the syntax for calling ApplySpecialFunction(x, f) in C#. We just call it SelectMany instead of ApplySpecialFunction. The problem is that of course that syntax only reads nicely for the sequence monad. But as we’ll see in a few more episodes, that syntax can be used on any monad, provided that you rename ApplySpecialFunction to SelectMany.

        Reply ↓

        • I got too curious to see how SelectMany would work with Nullable just to discover the compiler wouldn’t call the overload I was expecting, but ignoring the extra unexpected parameter I got somewhere, just not exactly what a reader would expect:

          namespace Monads
          {
          class Program
          {
          static void Main(string[] args)
          {
          Func<double, decimal?> f = y =>
          {
          try
          {
          return new Nullable((decimal)y);
          }
          catch (OverflowException)
          {
          return new Nullable();
          }
          };

          double? x = 5;

          var r = from a in x
          from b in f(a)
          select “the real wtf”;

          Console.WriteLine(r.ToString());
          }
          }

          public static class NullableMonad
          {
          public static TResult? SelectMany<TSource, TResult, Twtf>(this TSource? value, Func<TSource, TResult?> selector, Func<TSource, TResult, Twtf> wtf)
          where TSource: struct
          where TResult:struct
          {
          return value.HasValue ? selector(value.GetValueOrDefault()) : null;
          }
          }
          }

          Reply ↓

    • To understand the interest of monads for a C# programmer, just look at the monad exemples in the first article: Nullable, IEnumerable and Task were all considered important enough to have syntactic sugar added to the language itself to use them better. Basically, things like the ? notation for nullable, yield and linq for IEnumerable and await for Tasks make the compiler itself implement the monad pattern for you.

      Most of the recent improvements in the C# language are linked one way or another to monads. i think that’s reason enough to care.

      Reply ↓

  3. Hey Eric, this has been a really interesting series, as always. I’m also hoping you include a section about “when you might use a Monad” with maybe an example of something that doesn’t currently exist in the BCL.

    On a totally unrelated note; do you know any good books you could recommend about designing compilers? I would prefer something that is lighter on the theory side and more heavy on the practical side.

    Thanks!

    Reply ↓

  4. Func<double, Nullable> toDecimal = y => Math.Abs(y) < decimal.MaxValue :
    new Nullable((decimal)y) : new Nullable();

    Eric there is a typo after “Math.Abs(y) < decimal.MaxValue".

    Reply ↓

  5. Just a note: comparing a double to decimal.MaxValue is tricky. There’s no implicit conversion between decimal and double, so Math.Abs(y) < decimal.MaxValue won't work. If you convert the left side to decimal, you may get an OverflowException. If you cast the right side to double, it won't represent the same value. Also, logically your check should be less-than-or-equal rather than less-than, because if it equals the maximum value it should be fine, but (decimal)d throws an exception when d == (double)decimal.MaxValue.

    To avoid these problems, I define a constant to equal 7.92281625142643331939E+28, which is the maximum double value that can be converted into a decimal. That makes an assumption about the range of the decimal type, but the range is documented and decimal.MaxValue is const (meaning it'd break existing binaries to change it) so I don't feel the assumption is unsafe.

    Reply ↓

    • y => {
      try
      {
      return new Nullable<decimal>((decimal)y);
      }
      catch(OverflowException)
      {
      return new Nullable<decimal>();
      }
      }

      Does it works?

      Reply ↓

    • Comparisons between different numeric types can only really be done accurately by code which examines both numbers in their native type and takes into account differences between them. The .NET Framework doesn’t do that even in equality-comparison cases where the semantics should be clear and well-defined (for example, while one could define a proper equivalence relation between values of types `double` and `long` [such that for any three variables x,y,z of any combination of those types, if x==y and y==z, then x==z], the `==` operator in C# does not do so (e.g. x=1L<<62; y=(double)x; z=x+1). Unless one is going to explicitly code comparison operators that "understand" their operands [e.g. writing a `long`/`double` comparison operator which reports unequal if the double is outside the range of a long or has a non-zero fractional part, and otherwise converts to long and does the comparison], I would posit that semantics will be clearer if one requires that code explicitly converts things to the same format before comparison. Note that in the case of `double`-vs-`Decimal` comparisons, in most cases where a `Decimal`-to-`double` conversion would be imprecise, the resulting `double` value will also have no precise `Decimal` representation either.

      Reply ↓

  6. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1316

Leave a comment