Justin du Coeur (jducoeur) wrote,
Justin du Coeur

Oh, right -- Monads Don't Compose

[Continuing Friday's deep programming burble, and figuring out how to use Gists instead of typing the freaking code directly into my entry. Hopefully this will all work...]

So when last we left our hero, he had just gotten his first Monad working, and there was much rejoicing.

Then I tried a more interesting use case, and it all fell apart. The problem is a well-known one in Functional Programming circles, which I knew perfectly well from working with other for comprehensions in Scala, but hadn't quite internalized yet: Monads Don't Compose. That is, you can build very powerful comprehensions using a single Monad, but as soon as you try to mix apples and oranges, the compiler chokes on them.

So here's a further burble, going into this problem, and how I'm working around it.

The example in question is _showLink, the Querki Function that receives either a local or external Link, and turns it into a conventional HTML <a> tag. The original code (based on my first pass at the Invocation class) looked like this:Example 1 -- original _showLink code

Yes, that's an inconsistent mess, hence the desire to clean it up. So I did the same exercise as last time, asking myself what I *wanted* it to look like, and got this:Example 2 -- first attempt to rewrite _showLink

Note the three lines marked as Problems. Those are places where what I really *want* is to embed a different Monad in the same statement.

Remember that the whole point of InvocationValue is that it's a nice, consistent Monad that I can simply lace through a for comprehension -- each line transforms it, and if an error happens it just skips the remainder of the processing and returns that error.

But Problem 1 is that "inv.contextElements" -- I want that to take the received context, turn it into a *list* of contexts, and process each one of those. That's a snap for the List Monad -- but I don't have the List Monad here. Similarly, Problems 2 and 3 are functions that returns Option[something] -- that is, they either return a value or not. Again, you can easily have a for comprehension of Options -- but you can't mix them in a comprehension of some *other* Monad.

In the end, I decided that the solution was to cheat. (Really, I suspect that I wound up implementing a poor man's version of scalaz's Monad Transformers, but I don't understand those at all well yet, so I simply dealt with the 98% case.) Specifically, I decided to follow Querki as my model.

The thing is, Querki does *not* treat its Collections as nice, neat Monads -- and now that I hit this problem, I was reminded of why. Monads are beautifully elegant so long as your basket is made up entirely of apples -- but Querki isn't nearly that neat. I specifically want my users to be able to mix Optional (the Option Monad) with ExactlyOne (the Identity Monad) with List (the List Monad, duh) easily, so it intentionally squishes out the differences. This is *horrifying* from a pure category theory point of view, and means that some use cases won't be so elegant -- but it means that 99% of Querki code is ridiculously obvious and simple.

So I rewrote InvocationValue to take a *sequence* of values, instead of exactly one. The original version expected that an InvocationValue[T] would take exactly one T if there wasn't an error. Now, it takes an Iterable[T]. If there is exactly one, that's an Iterable of length 1; if there are many, there are many; if there are None, it's just empty. The code comes out like this:Example 3 -- resulting InvocationValue

Finally, to get _showLink working the way I wanted, I added the .opt() and .iter() methods to Invocation. These simply take any Option[T] or Iterable[T], and transforms it into an InvocationValue[T], so that they can be used inside the same comprehension. So my calling code comes out pretty close to what I was originally hoping for:Example 4 -- resulting _showLink

Much better -- with just a little tweaking, I can now use Options and any sort of Iterable inside my for comprehensions. The result, I believe, will be that hundreds of messy, complex functions inside Querki are shortly going to be reduced to relatively straightforward (and consistent) for statements...
Tags: programming, querki

  • First day of the next phase of my life

    Friday was formally my last day at Memento, but I count it as yesterday. Way back in March, I gave a sort-of four months' notice, saying that I would…

  • You know you're a true tea addict when...

    ... you finish your job and are packing your desk, and the tea selection on the back of your desk takes an entire moving box all by itself. (Yes,…

  • Resume rules

    Conducted an interview this morning; suffice it to say I wasn't blown away in general, but the worst of it was the resume, which was almost…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded