Monads in Scheme

This bit of the Guix documentation provides a better explanation of why monads are useful than I could give:

    The procedures that operate on the store described in the previous
    sections all take an open connection to the build daemon as their
    first argument. Although the underlying model is functional, they
    either have side effects or depend on the current state of the
    store.

    The former is inconvenient: the connection to the build daemon has
    to be carried around in all those functions, making it impossible
    to compose functions that do not take that parameter with
    functions that do. The latter can be problematic: since store
    operations have side effects and/or depend on external state, they
    have to be properly sequenced.

    This is where the (guix monads) module comes in. This module
    provides a framework for working with monads, and a particularly
    useful monad for our uses, the store monad. Monads are a construct
    that allows two things: associating “context” with values (in our
    case, the context is the store), and building sequences of
    computations (here computations include accesses to the store.)
    Values in a monad—values that carry this additional context—are
    called monadic values; procedures that return such values are
    called monadic procedures.

https://gnu.org/software/guix/manual/html_node/The-Store-Mon...

One reason is that they allow you to write general, primitive functions, and then compose them together or hoist them up into the same category.

Consider this example, written in Java 8.

    // Maybe<T> can be Nothing(), representing failure, or Just(X) representing success.

    public abstract class Maybe<T> {}

    public class Just<T> extends Maybe<T> {
        public final T value;
        public Just(T value) { this.value = value; }
    }

    public class Nothing<T> extends Maybe<T> {}

Now consider these function signatures:

    // Returns Nothing() if argument is negative
    public Maybe<Double> squareRoot(double x);

    // Returns Nothing() if divisor is 0
    public Maybe<Double> divide(double x, double y);

    

What do I do if I want to chain these functions together to write a "square root and divide" function?

    // Returns Nothing() if dividend is negative or divisor is 0
    public Maybe<Double> squareRootAndDivide(double x, double y) {
        Maybe<Double> sqrt = squareRoot(x);
        if(sqrt instanceof Just<Double>) {
            return divide(sqrt.value, y);
        } else {
            return new Nothing();
        }
    }

This is kind of ugly. And if I want to compose lots of Maybe values, all of this instanceof nonsense (or having a tagged union in C or whatever) becomes extremely tedious.

Better is to define a function to contain this logic:

    // Returns Nothing() if x is Nothing(), otherwise returns f(unwrapped x)
    public <A, B> Maybe<B> bind(Maybe<A> x, Function<A, Maybe<B>> f) {
        if(x instanceof Just<A>) {
            return f.apply(x.value);
        } else {
            return new Nothing();
        }
    }

Now I can write the above squareRootAndDivide code like:

    public Maybe<Double> squareRootAndDivide(double x, double y) {
        return bind(squareRoot(x), ::divide);
    }

Now I can chain any number of calls that may all end in failure, not having to worry where the failure takes place:

    return bind(bind(foo(x), ::bar), ::baz);

That looks kind of stupid. We could define `bind` to be a member of the abstract class Maybe, and refer to `this` instead of `x`, then we could rewrite that like:

    return x.bind(::foo).bind(::bar).bind(::baz);

Which in Haskell would look like

    foo x >>= bar >>= baz   

Quite clean in both languages!

Of course, Java might be a bad example, because you might say "Well, I would just throw an exception for any of those illegal arguments, and that would also short-circuit the computation". This is true.

In Haskell, there is the Either type, which is similar to the Maybe type except instead of Nothing and Just you have Left and Right. The difference in Left and Nothing is Left can contain some information (such as a string explaining what failure happened, like a Java exception). Like Maybe, Either is also a monad, and can be chained together in much the same way, except instead of short circuiting on Nothing, it short circuits on Left.

So in Java, it's almost as if you are always living in the Either monad without even knowing it! Of course, this is a gross abuse of terminology.

There is also far more that can be done with monads than representing failure (although they are great for that in the above examples, or in parsers, etc). This is just a simple example.

It also might be interested to note that you cannot construct a Monad interface in Java that has this `bind` function, because Java lacks Higher-Kinded Types. Consider a type in java Foo<A, B, C>. It doesn't make sense to talk about Foo<A, B>, because Foo takes 3 type parameters. In Haskell we can talk about Foo<A, B> as a "higher kinded" type that takes another type as an argument (C) to produce a concrete type of Foo<A, B, C>.

As such, we have to code an ad-hoc monadic interface for every type we want to have one, but this means we can't write functions that operate on any generic monadic type.

Rust is currently running into this -- they have monad-like interfaces for Result and Option (Rust versions of Either and Maybe) where the function and_then is their bind. I would like to write a function which can say, go from Vec<Option<u32>> to Option<Vec<u32>. Where it returns None if any of the elements of the Vec were None.

I would also like to write a function that goes from Vec<Result<Err, u32>> to Result<Err, Vec<u32>>, giving me Err if any of the elements of the Vec were Err. You can see how this is the same pattern as above. In Haskell, with Higher-Kinded types, we can write this function generlized to all monads (called `sequence` in the standard library), but in Rust or Java, I would have to write this function for each particular instance.

You might find it valuable to read something like [1], but it might use too much Haskell syntax to be particularly readable. Give it a shot, anyway. Specifically for Monads, the section about the Kleisli category is the most applicable.

[1] http://www.haskellforall.com/2012/08/the-category-design-pat...

I think that Haskell has maybe done a bit of a disservice by making so much hay about using monads for side effects. That's super-important in the context of Haskell, of course, but it gives the unfortunate and false impression that that's what they're really about.

I don't know that I'm feeling up to banging out a concrete example in Scheme, but I'd strongly encourage anyone who'd like to see monads being put to good use outside the Haskell space to take a look at the .NET ecosystem. Monads are the soul of LINQ, and F#'s workflows are essentially just monads wearing Groucho glasses.

For a concrete example of where they can be useful, let's say you've got the following LINQ query (C# code):

  var sum = Enumerable.Range(1, 10000)
                      .Select(SomeInterestingCalculation)
                      .Where(SomeInterestingPredicate)
                      .Sum();

and you want to parallelize it. It's pretty easy to do because some clever folks have already done all the hard work and encapsulated the whole mess in an easy-to-use package:

  var sum = Enumerable.Range(1, 10000)
                      .AsParallel()
                      .Select(SomeInterestingCalculation)
                      .Where(SomeInterestingPredicate)
                      .Sum();

And that's a very rightful question.

To me even more concise and readable is the imperative solution the article also mentions: just refer to a "global" counter and increment it (it doesn't have to actually be global, for that matter, just scoped around the tree-building code). The article doesn't even really argue against that solution. Instead the goal here seems to be more of an intellectual challenge problem: find a functional solution that, unlike the straightforward functional solution (thread state through every function call), is not that much clunkier than the imperative solution.