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!

Project Euler Problem 8

I guess I should warn that these Project Euler posts have spoilers, in case you want to try the problems yourself ☺. My Scala solution to problem 8:

val input = "73167176531330624919225119674426574742355349194934" +
"96983520312774506326239578318016984801869478851843" +
"85861560789112949495459501737958331952853208805511" +
"12540698747158523863050715693290963295227443043557" +
"66896648950445244523161731856403098711121722383113" +
"62229893423380308135336276614282806444486645238749" +
"30358907296290491560440772390713810515859307960866" +
"70172427121883998797908792274921901699720888093776" +
"65727333001053367881220235421809751254540594752243" +
"52584907711670556013604839586446706324415722155397" +
"53697817977846174064955149290862569321978468622482" +
"83972241375657056057490261407972968652414535100474" +
"82166370484403199890008895243450658541227588666881" +
"16427171479924442928230863465674813919123162824586" +
"17866458359124566529476545682848912883142607690042" +
"24219022671055626321111109370544217506941658960408" +
"07198403850962455444362981230987879927244284909188" +
"84580156166097919133875499200524063689912560717606" +
"05886116467109405077541002256983155200055935729725" +
"71636269561882670428252483600823257530420752963450"

val digits = input.map(_.asDigit).toArray

def multiply(index: Int) = digits.slice(index, index + 5)
    .foldLeft(1)(_*_)

val multiples: Stream[Int] = {
    def rec(n: Int): Stream[Int] = Stream.cons(multiply(n),
        if (n > digits.length - 5) Stream.empty else rec(n+1))
    Stream.cons(mult(0), rec(1))
}
println(Iterable.max(multiples))

For convenience, this specifies the input as a string, then uses RichChar.asDigit to create a corresponding array of integers. The multiply function uses left fold to multiply together sequences of five digits. The multiples value is a stream (lazy list) of the multiples of all groups of five consecutive digits from the input. And finally, the Iterable object provides a convenient method to find the maximum value in any Iterable containing Orderable things.

Project Euler in Scala

Project Euler is a bunch of mathematical/programming problems. I've been trying to improve my Scala skills by using it on some of the Euler problems. I'm trying to use functional programming styles as much as possible. My solutions definitely haven't been very optimized, but I am learning, which is the aim.

Euler Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

My solution:

def sum(nums: Iterable[Int]): Int = (0 /: nums)(_ + _)

println(sum((3 until 1000).filter(i => i%3 == 0 || i%5 == 0)))

The 3 until 1000 creates a "range", which is a lazy sequence of numbers from 3 to 999 inclusive. Because it's lazy, you don't get 997 integers sitting around in memory, you only get those integers which pass the filter. The filter itself shows the Scala syntax for a "lambda expression" (anonymous function). The full syntax is (arg1, arg2, ..) => function body, but when you only have one argument (a single Int, in this case) you can leave out the brackets.

The sum function is the operator syntax for a left fold over nums. The _+_ is an even more terse form of a lambda expression that you can use for really simple expressions. The first underscore is replaced by the first argument to the function, and the second is replaced by the second argument.