Scalaz OptionT Monad Transformer

Suppose you’re writing code that deals with artists, albums, and songs using the following simple classes:


  case class Song(name: String, durationInSeconds: Int)
  case class Album(name: String, songs: List[Song])
  case class Artist(name: String, albums: List[Album])

Here’s a simple method that looks up a song based on its artist name, album name, and song name:


  def findSong(
      artists: List[Artist],
      artistName: String,
      albumName: String,
      songName: String): Option[Song] = for {

    artist <- artists       find { _.name === artistName }
    album  <- artist.albums find { _.name === albumName }
    song   <- album.songs   find { _.name === songName }
  } yield song

This code runs inside the Option monad, making error handling really easy. If we can’t find the artist, album, or song, we simply return None; otherwise, we return Some(song). The code is nice and clean relative to the equivalent traditional imperative code where we would have to test for null after both the artist and album lookups. Now suppose that for whatever reason, we want to track the number of times we lookup a song that’s longer than 10 minutes in duration. We might choose to track the number of long song lookups using a State monad where the state is simply an integer. We’ll first create a type for our State monad:


  type IntState[+A] = State[Int, A]

We’d like to be able to change our findSong() method to be something like this:


  def findSong(
      artists: List[Artist],
      artistName: String,
      albumName: String,
      songName: String): IntState[Option[Song]] = for {

    artist <- artists       find { _.name === artistName }
    album  <- artist.albums find { _.name === albumName }
    song   <- album.songs   find { _.name === songName }

    _ <- modify { count: Int =>
      if (song.durationInSeconds >= 10*60) count + 1 else count
    }
  } yield song

Unfortunately, this code won’t compile since we’re mixing our monads within the for comprehension. The first 3 lines in the for comprehension are using the Option monad, while the last is using our IntState monad. Since our state modification code must be within the IntState monad, let’s put all the code into this monad. We can get all the code into the IntState monad by pointing the Option’s returned by our 3 find calls into IntState:


  def findSong(
      artists: List[Artist],
      artistName: String,
      albumName: String,
      songName: String): IntState[Option[Song]] = for {

    artist <- artists find { _.name === artistName }
      .point[IntState]

    album <- artist.albums find { _.name === albumName }
      .point[IntState]

    song <- album.songs find { _.name === songName }
      .point[IntState]

    _ <- modify { count: Int =>
      if (song.durationInSeconds >= 10*60) count + 1 else count
    }
  } yield song

Sadly, there are two big problems with this code. First, because we’re now using IntState rather than Option as our monad, the expressions on the right side of our first three arrows are of types

  • IntState[Option[Artist]]
  • IntState[Option[Album]]
  • IntState[Option[Song]]

But that means that our artist, album, and song variables are now of types

  • Option[Artist]
  • Option[Album]
  • Option[Song]

rather than simply being of types Artist, Album, and Song like they were in the original code. So we can no longer refer to things like artist.albums since Option[Artist] doesn’t have an albums field.

The second problem has to do with error detection. In our original code based on the Option monad, we automatically stopped processing if we couldn’t find the specified artist, album, or song. But our latest code (if it would compile) keeps on processing regardless of whether we get None’s or Some’s from our lookups. We’re now in the State monad, and it doesn’t apply any interpretation to the values wrapped up in it. The State monad won’t stop just because we put a None in it.

Here’s a version of the code that correctly uses the IntState monad:


  def findSong(
      artists: List[Artist],
      artistName: String,
      albumName: String,
      songName: String): IntState[Option[Song]] = for {

    maybeArtist <- (artists find { _.name === artistName })
      .point[IntState]

    maybeAlbum <- (
      maybeArtist match {
        case Some(artist) =>
          artist.albums find { _.name === albumName }

        case None =>
          Option.empty[Album]
      }
    ).point[IntState]

    maybeSong <- (
      maybeAlbum match {
        case Some(album) =>
          album.songs find { _.name === songName }

        case None =>
          Option.empty[Song]
      }
    ).point[IntState]

    _ <- modify { count: Int =>
      maybeSong match {
        case Some(song) if song.durationInSeconds >= 10*60 =>
          count + 1

        case _ =>
          count
      }
    }
  } yield maybeSong

I guess it’s nice that this code works. It compiles, correctly looks up songs, and correctly increments the long song count in our IntState monad. But wow is it butt ugly! What happened to the nice clean monadic code we started with?

OptionT to the Rescue!

Our problem is that we have two competing monads: Option and IntState. But, for comprehensions only allow us to work in a single monad at a time. What we need is a new mega monad that incorporates all of the characteristics of Option and IntState. Luckily, that’s exactly what Scalaz’s OptionT monad does. OptionT allows us to mix an arbitrary monad like IntState with an Option to get a new monad that has all the characteristics of both.

OptionT takes two type parameters. The first is the monad that we want to blend with Option. The second is the standard monadic type parameter which represents any type that is wrapped in the monad. In our case, our OptionT will look like this:

  OptionT[IntState, A]

I’ll be explaining below how to use OptionT with IntState. But, it’s important to realize that you can use OptionT with any monad type at all, not just a State monad. For example, if we setup the following type using the Reader monad

  type StringReader[+A] = Reader[String, A]

we can have the following:

  OptionT[StringReader, Boolean]

We can construct an OptionT from either an IntState or an Option. If we have an IntState object, we call its liftM method to convert it to an OptionT, for example

  val m1: IntState[String] = "hello".point[IntState]
  val m2: OptionT[IntState, String] = m1.liftM[OptionT]

Converting an Option into an OptionT is only slightly more complicated. First, you have to wrap the Option in an IntState using the point method. Then, you wrap the resulting IntState in an OptionT using the optionT method. Here’s an example:

  val m1: Option[String] = "goodbye".some
  val m2: IntState[Option[String]] = m1.point[IntState]
  val m3: OptionT[IntState, String] = OptionT.optionT(m2)

Here’s how we can use OptionT to simplify our findSong() example:

  def findSong(
      artists: List[Artist],
      artistName: String,
      albumName: String,
      songName: String): OptionT[IntState, Song] = for {
  
    artist <- OptionT.optionT(
      (artists find { _.name === artistName }).point[IntState]
    )

    album <- OptionT.optionT(
      (artist.albums find { _.name === albumName })
        .point[IntState]
    )

    song <- OptionT.optionT(
      (album.songs find { _.name === songName }).point[IntState]
    )

    _ <- modify { count: Int =>
      if (song.durationInSeconds >= 10*60) count + 1 else count
    }.liftM[OptionT]

  } yield song

Let’s look at a couple parts of that method in more detail. First, let’s look at

    artist <- OptionT.optionT(
      (artists find { _.name === artistName }).point[IntState]
    )

Our call to the find() method returns an Option. But we want an OptionT, not an Option. No problem. Based on what I described above, we have to first wrap the Option in an IntState using the point() method. Then, we can convert the resulting IntState into an OptionT using method optionT().

What about the artist variable on the left side of the arrow? What’s its type? It’s now simply of type Artist, not Option[Artist]. Having a result of type Artist simplifies the rest of our code because we don’t have to use pattern matching to extract the Artist out of the Option.

What happens if the find() method returns None? The None gets wrapped up into an OptionT. Even more importantly, our processing will stop or be short-circuited. That is, we don’t have to worry about stopping our processing when we hit a None; the OptionT monad will do that for us automatically. So we don’t have to litter our code with ugly error checks.

In short, the OptionT is behaving exactly like the Option monad! Outside of a tiny bit of complexity from wrapping results in an OptionT, our code is as nice, simple, and clean as our original findSong() method at the beginning of this article (before we introduced IntState).

Next, let’s look at this block of code:

    _ <- modify { count: Int =>
      if (song.durationInSeconds >= 10*60) count + 1 else count
    }.liftM[OptionT]

The call to modify() returns a value of type IntState[Unit]. But we don’t want a value of type IntState; instead we need an OptionT value. No problem. We just need to call liftM() to wrap the IntState in an OptionT[IntState, Unit].

By using OptionT as our monad, we can easily work with IntState’s whenever we want to, and we can easily work with Option’s whenever we want to. We’re left with nice, clean code.

Here’s some code that calls our findSong() method:

  val m1: OptionT[IntState, Song] = findSong(
    artists, "Yes", "Going for the One", "Awaken")

  val m2: IntState[Option[Song]] = m1.run
  val (numLongSongs, maybeSong) = m2.run(0)

The key line here is

  val m2: IntState[Option[Song]] = m1.run

Notice that calling the run method on the OptionT without any parameters converts it into an IntState monad. The resulting IntState monad holds an Option[Song] as its value. We’re now just dealing with a standard State monad, which we can run by providing it with an initial state of 0 (since we start with a count of 0 long songs looked up). Once we run the State monad, we’re left with a final number of long songs looked up and maybe a song (a Song object wrapped in an Option).

If findSong() successfully finds our artist, album, and song, maybeSong will be a Some[Song]. But if it can’t find the artist, album, or song, maybeSong will be a None.

Binding Lists of OptionT’s

Now that we know how to lookup one song, let’s write a method that looks up a list of songs. First, we’ll create a case class that holds information needed to lookup one song:

  case class SongLookup(
    artistName: String,
    albumName: String,
    songName: String)

Our new findSongs() method will take lists of Artist’s and SongLookup’s as parameters. The return value should somehow include an IntState so that we can track the number of long song lookups. But we have an important requirements question to resolve regarding error handling. How severe should it be if we can’t locate one song? Should it be really severe and we return no information for any of the songs? Or should we return information for as many songs as possible?

If lookup errors should be really severe, our findSongs() method will return

  OptionT[IntState, List[Song]]

Remember that this is like an Option[List[Song]]. So, it will ultimately hold a Some[List[Song]] if all the songs were found or a None if any of the songs weren’t found.

Alternatively, if we want to return information for as many songs as possible, we’ll return

  IntState[List[Option[Song]]]

Each of the song requests will result in either a Some or a None being added to the result list.

We’ll go ahead and implement both versions, starting with the one that treats errors as being severe. Here’s a first, incorrect attempt:

  def findSongs(
      artists: List[Artist],
      lookups: List[SongLookup]): OptionT[IntState, List[Song]] = {

    lookups map { lookup =>
      findSong(
        artists, lookup.artistName,
        lookup.albumName, lookup.songName)
    }
  }

The problem is that map returns a List[OptionT[IntState, Song]], but we need an OptionT[IntState, List[Song]]. That is, we’ve got a list of monads when we really need a single monad of lists. How do we convert a list of monads into a single monad? We could manually bind the monads together by looping over them and flatMap’ing them two-at-a-time until we’re left with only one. That’s kind of a pain in the neck. Luckily, there’s a method traverseU that does exactly what we want. Method traverseU does all the work of the map, and it binds the resulting monads into a single monad while collecting the monads’ values into a list. Bottom line, if we change map to traverseU, the code will work:

  def findSongs(
      artists: List[Artist],
      lookups: List[SongLookup]): OptionT[IntState, List[Song]] = {

    lookups traverseU { lookup =>
      findSong(
        artists, lookup.artistName,
        lookup.albumName, lookup.songName)
    }
  }

We can call this method to get a list of songs as folows:

  val (numLongSongs: Int, maybeSongs: Option[List[Song]]) =
    findSongs(artists, lookups).run(0)

Taking this apart, findSongs() returns an OptionT[IntState, List[Song]]. Calling run (with no parameters) turns the result into an IntState[Option[List[Song]]]. Adding the parameter 0 runs the IntState’s apply() method (which is the same as its run() method). So, we’re ultimately running the IntState with an initial state of 0. The result is a count of long song lookups and optionally a list of songs (if all the lookups succeeded).

Here’s the code for the other version that returns information about as many songs as possible:

  def findSongs(
      artists: List[Artist],
      lookups: List[SongLookup]): IntState[List[Option[Song]]] = {

    lookups traverseS { lookup =>
      findSong(
        artists, lookup.artistName,
        lookup.albumName, lookup.songName).run
    }
  }

Let’s work backwards through this code. Recall that findSong() returns an OptionT[IntState, Song]. If we call run on the OptionT, we’ll have an IntState[Option[Song]]. So after we call run, we’re left with an IntState monad for each song we tried to lookup. If a lookup is successful, the corresponding IntState holds a Some[Song]. If the lookup fails, the IntState holds a None.

Now all we have to do is loop over the lookups, call findSong() for each, and bind the resulting IntState monads together into a single monad. Method traverseS will take care of all that for us. Method traverseS is very similar to traverseU. Use traverseS when working with State monads (as we are here); use traverseU when working with OptionT monads (as in the previous example).

We can now retrieve both a list of songs and a count of the number of long songs like this:

  val (numLongSongs: Int, songs: List[Option[Song]]) =
    findSongs(artists, lookups).run(0)

Summary

The OptionT monad allows you to combine the capabilities of the Option monad with another arbitrary monad, allowing you to write nice, simple clean code which isn’t littered with error checking. Any monad at all can be combined with OptionT. If you’re using a monad of type M, just remember the following rules:

  • If you have a value m of type M[A], you convert it to an OptionT by calling m.liftM[OptionT].
  • If you have a value opt of type Option[A], you convert it to an OptionT by first pointing it into monad M and then using method optionT like this: OptionT.optionT(opt.point[M])
  • If you have a value optT of type OptionT[M, A], you can convert it into an M[Option[A]] like this: optT.run
  • If you need to apply a function that returns an OptionT to each item in a list, use traverseU to invoke the function on each list item and bind the resulting OptionT’s into a single OptionT.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: