Monads, part four

So far we’ve seen that if you have a type that follows the monad pattern, you can always create a “wrapped” value from any value of the “underlying” type. We also showed how five different monadic types enable you to add one to a wrapped integer, and thereby produce a new wrapped integer that preserves the desired “amplification” — nullability, laziness, and so on. Let’s march forth[1. HA HA HA HA HA HA I crack myself up.] and see if we can generalize the pattern to operations other than adding one to an integer.

Let’s stick with integers for a moment though; higher-order programming can be a bit tricky and so I want to approach it slowly. We represent an operation on integers with a Func<int, int> — that is, a delegate which takes an integer and produces an integer. We can generalize each of our five AddOne methods of last time to instead take a Func<int, int> that represents the desired operation:

static Nullable<int> ApplyFunction(
  Nullable<int> nullable, 
  Func<int, int> function)
{
  if (nullable.HasValue)
  {
    int unwrapped = nullable.Value;
    int result = function(unwrapped);
    return new Nullable<int>(result);
  }
  else
    return new Nullable<int>();
}

Our AddOne method is now a special case:

static Nullable<int> AddOne(Nullable<int> nullable)
{
  return ApplyFunction(nullable, (int x) => x + 1);
}

I’m sure you can see how we could apply this same simple transformation to the other AddOne methods to make all five ApplyFunction methods. Can we make this even more general? Sure; there’s nothing special about integers! We can replace all those integers with Ts:

static Nullable<T> ApplyFunction<T>(
  Nullable<T> nullable, 
  Func<T, T> function)
{
  if (nullable.HasValue)
  {
    T unwrapped = nullable.Value;
    T result = function(unwrapped);
    return new Nullable<T>(result);
  }
  else
    return new Nullable<T>();
}

And moreover: suppose we have a function from int to double; say we want to divide the int by two and get the result as a double. Clearly if we have an operation on an int that produces a double, then we should be able to make an operation on an “amplified” int that produces an “amplified” double. Really this thing should take two type parameters: the underlying type on the input side and the underlying type on the output side:

static Nullable<R> ApplyFunction<A, R>(
  Nullable<A> nullable, 
  Func<A, R> function)
{
  if (nullable.HasValue)
  {
    A unwrapped = nullable.Value;
    R result = function(unwrapped);
    return new Nullable<R>(result);
  }
  else
    return new Nullable<R>();
}

And similarly we can make ApplyFunction methods that allow you to do the same thing to our other examples of the monad pattern:

static Lazy<R> ApplyFunction<A, R>(
  Lazy<A> lazy, 
  Func<A, R> function)
{
  return new Lazy(()=> 
  {
    A unwrapped = lazy.Value;
    R result = function(unwrapped);
    return result;
  });  
}

And so on; the rest are an easy exercise given how verbosely I wrote them out last time.

We know that the first part of the monad pattern is that there’s got to be an easy way to take a value of the underlying type and turn it into a value of the amplified type. And I said earlier that, though it seems plausible that there ought to also be a way to get the values back out on demand, the truth is actually more subtle. What we’ve shown here is that we actually need to get the values back only insofar as is necessary to ensure that any function on the underlying values can be applied to any amplified value.

Essentially what we’ve got here is a way of turning functions from A to R into functions from M<A> to M<R> such that the action of the function is preserved and the “amplification” provided by the monadic type is also preserved. That is pretty darn useful!

Is this then the second requirement of the monad pattern: that you can write a method with the signature

static M<R> ApplyFunction<A, R>(
  M<A> amplified, 
  Func<A, R> function)

that does the right thing?

No. But we are so close! Next time on FAIC we’ll make a small but vital modification to the signature pattern ApplyFunction to arrive at the actual second requirement of the monad pattern.

About these ads

24 thoughts on “Monads, part four

  1. This is really good stuff. I like your pedagogical approach over something more densely technical. Another fellow blogger takes a similar approach, though he often gets into details much more quickly than you have. Check him out, if you don’t already – scientopia.org/blogs/goodmath/

    Mark is one of my favorite bloggers, and in general is just a really cool guy.

  2. “Small but vital modification”: rename the function “bind”?

    On a more serious note, bind should accept a function that already returns an augmented value, so the signature should be something like:

    static M<R>> Bind<A, R>(
      M<A> amplified, 
      Func<A, R> function)

    Which is highly useful, and required to implement the monad pattern. However, the ApplyFunction method you posted here, which is basically the same as fmap, is far more useful. The reason a monad needs Bind and not ApplyFunction is because ApplyFunction can be defined in terms of Bind, but not vice versa – Bind is more general while ApplyFunction is more useful.

  3. I’m enjoying your series on monads. I’d be interested to know:

    (1) Are the obvious functions for mapping values to amplified values, or for binding, the *only* ones that make a valid monad for those particular generic types? E.g., I could imagine a much less obvious function for mapping T to Nullable<T>, say (T t) => T is int ? new Nullable<int>((int)t + 1) : new Nullable<T>(t)

    God knows why you’d want to do that, but is it an equally valid monad?

    (2) Why can’t the other common C# generic types be expressed as monads? Is it that they don’t have an obvious bind method, or for some is there no *possible* way to define a valid bind method?

    • In a couple more episodes we’ll cover why such an encoding would not be a valid implementation of the monad pattern.

      As for other generic types, what types did you have in mind?

        • OK, so (1) what “amplification” does it represent? (2) how do you turn an instance of any type T into an instance of IEquatable<T>? and (3) if you have a function from A to R, how do you turn that into an “equivalent” function from IEquatable<A> to IEquatable<R>? If you can’t answer those three questions then it’s not an example of the monad pattern.

  4. (1) A T that can check whether it’s the same as another T. (I’m not sure if that’s a valid “amplification”, since I’m not totally clear on the rigorous definition of “amplification”, but it doesn’t sound that different than your examples of “a T that can be null”, or “a T that can be computed on demand”.

    (2) Well, I’m not sure if this is allowed but couldn’t you just wrap it in a class that implements IEquatable<T>, using the T’s equals method (that it inherits from object, if it doesn’t have its own)?

    (3) Hmm… I guess I would either need a way to convert any IEquatable<A> to A (so I could apply the Func<A,R> to it before comparing to R), or I’d need a way to invert the Func<A,R> so I could map the R to an A and compare to my IEquatable<A>

    At least if I’m trying to do the bind in a way that preserves some properties of the original function. Originally I had been thinking I could do the amplification in a trivial way like always define the Equals method as return true; (which is still a reflexive/symmetric/transitive equivalence relation), but based on your answer to my (1) above I’m guessing that will be invalid for reasons you have yet to reveal.

    • Could be wrong here, but I think you are basically describing the Identity monad here, so while it is a monad it doesn’t really buy you much?

    • The problem with calling IEquatable a monad is that there’s no way to “unpack” an arbitrary IEquatable, and hence there’s no way to define the Bind function (note that IEnumerable works because the interface defines methods for unpacking it). However, you could define a generic implementation of IEquatable that wraps an instance of T, define a bind method for that specific implementation of IEquatable, and call that a monad. The amplification would be that it turns any T into a “T that implements IEquatable”. But, even in that case, its a monad only trivially (similar to, but perhaps not identical to the Identity Monad) and not all that useful.

  5. Incidentally, types for which you can write ApplyFunction (more commonly called “map”):

      static M<B> Map<A>(M<A> x, Func<A> f)
    

    are called “(covariant) functors” in Haskell, and are much more prevalent than monads. It’s no accident that this is called “covariance” — it’s very closely related to the subtyping sort of covariance. In fact, it’s “the same thing”, just in a different category. Compare:

      (A <: B) → (F<A> <: F<B>) -- if you have "A is a subtype of B", then you also have "F<A> is a subtype of F<B>"
      (A → B) → (F<A> → F<B>) -- if you have "a function from A to B", then you have "a function from F<A> to F<B>"
    

    And you’ll find that, generally, you can write “map” for a particular type more or less exactly when it’s (subtyping) covariant.

    Contravariance works too, with the types reversed:

      static M<B> Contramap<A>(M<A> x, Func<B> f)
    
  6. This comment has nothing to do with monads. Sorry, but I wasn’t sure how to get to you directly.

    For a future series, could you go into the immutability techniques for Roslyn’s AST, such that you can update/replace individual nodes (e.g. an statement) without cloning the entire AST structure?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s