Applying Applicative Functors in Scala

A chap named ittayd has written a nice gentle tutorial on functional programming in Scala. My only minor complaint is that he calls the applicative functor “sequential application” function apply. While this is a logical choice, in Scala apply is used everywhere to implement plain old function application, so it could lead to confusion. I think it’s better to call it <*>, as in Haskell. Read on.

I found the tutorial interesting because it talks a bit about applicative functors, and how to give them a nice syntax in Scala. The one thing that has bugged me about applicatives is that using them in Scala always felt clunkier than Haskell. Ittayd comes up with a scheme I like, but says “we have one difficulty: we can no longer define apply inside Future”. He uses a standard object-pimping implicit conversion to get around this, and that works fine. However, it is possible to define <*> inside your thing-with-an-applicative-functor, using one of my favourite Scala features: generalized type constraints. To continue with ittayd’s example using Future:

trait Future[A] { … def <*>[X, Y](x: Future[X])(implicit ev: A <:< (X => Y)) = new Future[Y] { def get = Future.this.get(x.get) def isDone = Future.this.isDone && x.isDone } }

The compiler will only allow <*> to be called on a Future that provides an appropriate function as its value.

Ittayd bootstraps things simply by lifting the function to be applied into Future, but personally I prefer the Haskell style of using <$>, aka “map”. In Scala, <$> is unsuitable for a few reasons, so I picked **::

trait Future[A] { … def **:[B](f: A => B): Future[B] = map(f) }

Obviously, this is just the standard map method with a different name, what’s the point? Well, because the operator ends with a :, it’s right associative; and because it starts with an *, it has higher precedence than <*>; so you end up with:

(marry _).curried **: joe <*> jane

Or, if you subscribe to the slippery slope theory of gay marriage:

(gayMarry _).curried **: joe <*> bob <*> george <*> fido <*> aDonkey

This is reasonably close to the Haskell idiom:

gayMarry <$> joe <*> bob <*> george <*> fido <*> aDonkey

You may wonder why obsess over the best way of dealing with applicative functors? After all, most of the applicative functors you see have an associated monad, so we can use Scala’s nice for syntax. Yes this is true for many useful applicative functors, but not all of them.

Just a quick asside on termonology. In casual conversation, you may hear it said that “Option is a monad”. But it’s more accurate to say “Option has a monad”. Because many types only have one useful monad associated with them, we tend to think that the type itself is the monad, but that’s not quite right. This doesn’t just apply to monads, of course, the same goes for monoids, applicative functors, etc. For example, numeric types have two useful monoids: one for addition and one for multiplication.

Now consider a Validation type from this Tony Morris tutorial. You can write a useful monad for this type, which implies an applicative functor as well. However, the tutorial is concerned with a second useful applicative functor for Validation. This second applicative is only relevant for the case where the Validation is using a semigroup as its error type (the tutorial explains what a semigroup is), and it allows using the semigroup to accumulate a list of all the validation failures. The classic example of this is validating data entered by a user on a form with several fields. The “plain” applicative/monad will only record the first validation failure it finds, whereas the semigroup applicative will record all the failures.

Now, finally, to my point (I think). This applicative functor that uses semigroup does not have a corresponding monad. Which means that we can’t use it with Scala’s for syntax. Hence the desire for a nice syntax for applicative functors. It is most definitely useful.

Obligatory Scalaz reference: those guys have pretty much worked out the best way to do all this stuff in Scala. But I find I learn a lot by experimenting myself.

Posted via email from lockster's posterous

Scala's Missing Monad

I've been writing more and more pure functional code in both Scala and Java recently. An issue I found myself running into quite often is this: say you have a function that sometimes returns no results (e.g. looking up a key in a map). A common way to deal with that in Scala is to return an Option:

Simple enough. But then a typical use of such a function is to map it over all members of a collection:

What I find I often want to do in a situation like this is to only bother with the results if all the applications of foo returned a result. In other words, I want to turn the strings list above into an Option[List[String]], which is Some(List(foo(1).get, foo(2).get, foo(3).get)) if all those applications of foo give values, and None otherwise. I couldn't see any method in the Scala standard library that does what I want.

As a bit of a functional programming n00b, one approach I've found to be useful is to work out the Haskell type signature of the function I want, feed that into Hoogle and see what I get, if anything. In this case, the Haskell type is:

The top Hoogle result for that is the sequence function:

And look, the sequence function works on any monad, not just Maybe/Option. For example, if my foo function had been returning Either[SomeErrorType, String], then the sequence function would give the first error in the list if there was an error, or the list of results if there was no error. So this is a useful function, but as I said, I can't find it in the standard Scala library.

When I thought about how to implement sequence in Scala, I immediately ran into trouble. It is often said that "Scala has monads", and we know that the flatMap method is doing a monadic bind. But this support isn't much more than a convention for method names and type signatures, combined with nice syntax in the form of for expressions. There is no monad type declared anywhere in the standard library. Without a monad type, the sequence function would have to be re-implemented over and over: Option.sequence, Either.sequence, List.sequence, etc.

The good news is that Scala's type system can express the monad type. And the better news is that some really smart people have already done all the work for us in a library called Scalaz. So I had a look, and lo and behold there is the sequence function:

That may look nothing like the Haskell function, but that is mostly a result of how typeclasses are expressed in Scala. Trust me, this is the same function. Also, this Scalaz function is more general than the Haskell function above. It turns out that sequence works for any "traversable" thing (not just lists) containing anything that is an applicative functor (not just monads). Haskell also has the equivalent fully generalised sequence function in the Data.Traversable library.

So what did I learn from this exercise? First that the lack of explicit types for monad, functor and friends in Scala's standard library is a greater problem than I'd expected. Second, if you're writing pure functional Scala code, you should be using Scalaz. Since all Scala programmers should be writing pure functional code, it follows that all Scala programmers should be using Scalaz!