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:
def foo(i: Int): Option[String]
Simple enough. But then a typical use of such a function is to map it over all members of a collection:
val strings: List[Option[String]] = List(1, 2, 3).map(foo _)
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:
sequence :: Monad m => [m a] -> m [a]
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
def sequence[N[_], B](implicit a: A <:< N[B],
t: Traverse[M], n: Applicative[N]): N[M[B]] =
traverse((z: A) => (z: N[B]))
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!
There are comments.