This post describes how to write a sequence method for your shiny new type F. This allows you to get from a type G[F[A]] to F[G[A]] – that is, to swap the order of your types. Here I’ll be using scalaz, and there is no magic involved. For many common types everything is already there for you, but if you write your own F[_] then there’s a little work to make it all fit together.

There limits on what the two types can be here, but in general:

sequence takes a G[F[A]] and gives you a F[G[A]]

Intuition

Consider your type to be like Option and the other type to be List. Starting with a list of options, you want to be able to get an optional list, which is present only if all of the options in the original list were present. If anything was absent, the returned Option[List] is absent.

Executive summary

You only need a few things in order to make this work, which I’ll describe below:

• an Applicative[F] instance for your type, e.g. Option
• a Traverse[G] instance for the other type, e.g. List
• syntax support from scalaz.syntax.traverse._ to add the sequence method to the G type
• consider using sequenceU if your type is more complicated than one with a single type parameter

Simple start with MyOption[A]

Let’s start with the simple example of implementing an option type, called MyOption. The minimal implementation looks something like this:

sealed trait MyOption[+A] {
  import MyOption._

  def map[B](f: A => B): MyOption[B] = this match {
    case Some(a) => Some(f(a))
    case None => None
  }
  def flatMap[B](f: A => MyOption[B]): MyOption[B] = map(f) getOrElse None
  def getOrElse[B >: A](b: => B): B = this match {
    case None    => b
    case Some(a) => a
  }
}
object MyOption {
  case object None extends MyOption[Nothing]
  case class Some[A](val get: A) extends MyOption[A]
}

The usage we’re trying to support might look like this:

val o1: MyOption[Int] = Some(3)
val o2: MyOption[Int] = Some(5)
val listOfOptions: List[MyOption[Int]] = List(o1, o2)
val optionalList: MyOption[List[Int]] = listOfOptions.sequence // Some(List(3, 5))

For a start, scalaz provides the Traverse[List] instance for us. This import says: give the scalaz helpers (specifically the typeclass instances) for the standard list type.

import scalaz.std.list._
import scalaz.syntax.traverse._

Now you need an Applicative for MyOption. It turns to be easier to create a Monad, which extends Applicative anyway.

import scalaz.Monad
implicit object MyOptionMonad extends Monad[MyOption] {
  // lift any A into my type, there's only one way to do this and it's obvious
  def point[A](a: => A): MyOption[A] = Some(a)

  // this is exactly flatMap, so just do that
  def bind[A, B](oa: MyOption[A])(f: A => MyOption[B]): MyOption[B] = oa flatMap f
}

That’s it: you can now do listOfOptions.sequence to turn a MyOption[List[A]] into a List[MyOption[A]].

Bonus: to do the reverse, create a Traverse for MyOption. Traverse acts a bit like flatMap,

implicit object MyOptionTraverse extends Traverse[MyOption] {
  def traverseImpl[F[_], A, B](fa: MyOption[A])(f: A => F[B])(implicit F: Applicative[F]) =
    fa map (a => F.map(f(a))(Some(_): MyOption[B])) getOrElse F.point(None)
}

Then you can do .sequence on a List[MyOption[A]] and get a MyOption[List[A]]. Note that it’s not always possible to map in both directions, because of the required properties of being able to find Applicative and Traverse instances.

Type Lambdas and Either[L, R]

It’s more tricky when your type has more than one type parameter, because you need to force your type into fitting into Applicative[A[_]], which takes one type parameter. The only good way of doing this is with a type lambda. The idea is that you fix one of the parameter types; here we fix L. You might call this a partially applied type constructor – this is exactly analogous to partial application of a function, where some of its parameters are fixed.

The expression ({type t[a] = MyEither[L, a]})#t means: a type t that takes one type parameter, and which is equal to MyEither[L, _]. This is an unfortunately complicated syntax for a simple idea.

Fixing one type parameter gives you a new type constructor that has only one type parameter. We can use this to create the Applicative. Note it’s not an object now, since we need one per type L that we fix for the first type parameter.

implicit def MyEitherApplicative[L]: Applicative[({type l[a] = MyEither[L, a]})#l] =
  new Applicative[({type l[a] = MyEither[L, a]})#l] {
    // lift any A into my type
    override def point[A](a: => A): MyEither[L, A] = Right(a)

    // given an applicative functor ef and an argument inside ea,
    // apply the function inside to the argument inside, if they're both there
    override def ap[A, B](ea: => MyEither[L, A])(ef: => MyEither[L, A => B]): MyEither[L, B] =
      for {
        a <- ea
        f <- ef
      } yield f(a)
}

This isn’t quite enough: attempting to compile listOfMyEithers.sequence gives cryptic error messages about could not find implicit value for parameter ev: scalaz.Leibniz.===[MyEither[String,Int],G[B]], which amounts to saying that it couldn’t find the required implicit to prove that MyEither has an Applicative instance. (The Leibniz part is about the equality condition required between your type and the Applicative.)

It’s possible to solve this with another type lambda, allowing the compiler to understand how you want to deconstruct the MyEither into something that can be expressed with a single type parameter. An easier way is with sequenceU, a different implementation of the same idea of sequence. With the same imports as above:

import scalaz.std.list._
import scalaz.syntax.traverse._
val sequencedListOfLefts: MyEither[String, List[Int]] = listOfMyEithers.sequenceU

Woah, what just happened there?

sequenceU is a method that implements the same behaviour as sequence but expresses the types differently, allowing the types to be inferred. This works through a type called Unapply that represents a type with one type parameter, but using a typeclass to provide the relation between the outer and inner types.

The implicit being used here can be created explicitly as the following. This says, paraphrasing the docs: unpack a value of type MyEither[A, B] into types [b]M[A, b] and B, and then find an Applicative instance for the partially applied type MyEither[L, _].

implicit val u: Unapply[Applicative, MyEither[String, List[Int]]] =
  Unapply.unapplyMAB2[Applicative, MyEither, String, List[Int]]