Log in

No account? Create an account
Previous Entry Share Next Entry
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...

  • 1
Does it mean you are transforming Option to List, and then flatten?

In QL (the language inside Querki), or in my Scala-level Monads?

I was thinking about Scala; but, essentially, it does not matter, conceptually.

Actually, never mind -- the answer is basically the same.

In both cases, the key is that I am treating all three of the really *common* Monads -- List, Option and Identity -- as special cases of Iterable. That works quite well in practice, so long as you don't care deeply about the resulting Monad identity (which I usually don't). So each one gets converted to Iterable on the way in, and iterated over.

So in my Scala-level comprehensions, this means that InvocationValue takes an Iterable under the hood, and I convert the incoming value to that. In QL, everything is internally a List, and the '->' operator (which is effectively Querki's flatMap operator) again simply treats everything as Iterable.

This isn't an elegant universal solution, and isn't as widely applicable as Monads -- it's a non-sequiteur to, say, the Future Monad. But it makes the really common cases much easier to work with, so I'm willing to swallow the hack...

  • 1