### Traverse

Two of the three motivating examples McBride and Paterson provide for idiomatic computations — sequencing a list of monadic effects and transposing a matrix — are instances of a general scheme they call traversal. This involves iterating over the elements of a data structure, in the style of a `map`, but interpreting certain function applications idiomatically. … We capture this via a type class of Traversable data structures.

In Cats, this typeclass is called Traverse:

``````@typeclass trait Traverse[F[_]] extends Functor[F] with Foldable[F] { self =>

/**
* given a function which returns a G effect, thread this effect
* through the running of this function on all the values in F,
* returning an F[A] in a G context
*/
def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]

/**
* thread all the G effects through the F structure to invert the
* structure from F[G[_]] to G[F[_]]
*/
def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] =
traverse(fga)(ga => ga)
....
}
``````

Note that the `f` takes the shape of `A => G[B]`.

When m is specialised to the identity applicative functor, traversal reduces precisely (modulo the wrapper) to the functorial map over lists.

Cats’ identity applicative functor is defined as follows:

``````  type Id[A] = A
def pure[A](a: A): A = a
def extract[A](a: A): A = a
def flatMap[A, B](a: A)(f: A => B): B = f(a)
def coflatMap[A, B](a: A)(f: A => B): B = f(a)
override def map[A, B](fa: A)(f: A => B): B = f(fa)
override def ap[A, B](fa: A)(ff: A => B): B = ff(fa)
override def flatten[A](ffa: A): A = ffa
override def map2[A, B, Z](fa: A, fb: B)(f: (A, B) => Z): Z = f(fa, fb)
override def lift[A, B](f: A => B): A => B = f
override def imap[A, B](fa: A)(f: A => B)(fi: B => A): B = f(fa)
}
``````

Here’s how we can traverse over `List(1, 2, 3)` using `Id`.

``````scala> import cats._, cats.data._, cats.implicits._
import cats._
import cats.data._
import cats.implicits._
scala> List(1, 2, 3) traverse[Id, Int] { (x: Int) => x + 1 }
res0: cats.Id[List[Int]] = List(2, 3, 4)``````

In the case of a monadic applicative functor, traversal specialises to monadic map, and has the same uses. In fact, traversal is really just a slight generalisation of monadic map.

Let’s try using this for `List`:

``````scala> List(1, 2, 3) traverse { (x: Int) => (Some(x + 1): Option[Int]) }
res1: Option[List[Int]] = Some(List(2, 3, 4))
scala> List(1, 2, 3) traverse { (x: Int) => None }
res2: Option[List[Nothing]] = None``````

For a Naperian applicative functor, traversal transposes results.

We’re going to skip this one.

For a monoidal applicative functor, traversal accumulates values. The function `reduce` performs that accumulation, given an argument that assigns a value to each element

``````scala> def reduce[A, B, F[_]](fa: F[A])(f: A => B)
(implicit FF: Traverse[F], BB: Monoid[B]): B =
{
val g: A => Const[B, Unit] = { (a: A) => Const((f(a))) }
val x = FF.traverse[Const[B, ?], A, Unit](fa)(g)
x.getConst
}
reduce: [A, B, F[_]](fa: F[A])(f: A => B)(implicit FF: cats.Traverse[F], implicit BB: cats.Monoid[B])B``````

Here’s how we can use this:

``````scala> reduce(List('a', 'b', 'c')) { c: Char => c.toInt }
res3: Int = 294``````

Using `-Ypartial-unification`, `traverse` is able to infer the types:

``````scala> def reduce[A, B, F[_]](fa: F[A])(f: A => B)
(implicit FF: Traverse[F], BB: Monoid[B]): B =
{
val x = fa traverse { (a: A) => Const[B, Unit]((f(a))) }
x.getConst
}
reduce: [A, B, F[_]](fa: F[A])(f: A => B)(implicit FF: cats.Traverse[F], implicit BB: cats.Monoid[B])B``````

We’ll find out what this is about later.

### sequence function

`Applicative` and `Traverse` are mentioned together by McBride and Paterson in Applicative programming with effects.

As a background, until a few months ago (March 2015), the sequence function in `Control.Monad` package used to look like this:

``````-- | Evaluate each action in the sequence from left to right,
-- and collect the results.
sequence :: Monad m => [m a] -> m [a]
``````

If I translate this into Scala, it would look like:

``````def sequence[G[_]: Monad, A](gas: List[G[A]]): G[List[A]]
``````

It takes a list of monadic values, and returns a monadic value of a list. This already looks pretty useful on its own, but whenever you find a hardcoded `List` like this, we should suspect if it should be replaced with a better typeclass.

McBride and Paterson first generalized the `sequence` function to `dist`, by replacing `Monad` with `Applicative`:

``````def dist[G[_]: Applicative, A](gas: List[G[A]]): G[List[A]]
``````

Next, they realized that `dist` is often called with `map` so they added another parameter for applicative function, and called it `traverse`:

``````def traverse[G[_]: Applicative, A, B](as: List[A])(f: A => G[B]): G[List[B]]
``````

Finally they generalized the above signature into a typeclass named `Traversible`:

``````@typeclass trait Traverse[F[_]] extends Functor[F] with Foldable[F] { self =>

/**
* given a function which returns a G effect, thread this effect
* through the running of this function on all the values in F,
* returning an F[A] in a G context
*/
def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]

/**
* thread all the G effects through the F structure to invert the
* structure from F[G[_]] to G[F[_]]
*/
def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] =
traverse(fga)(ga => ga)
....
}
``````

Thus as the matter of course, `Traverse` implements a datatype-generic, `sequence` function, which is just `traverse` with `identity`, conceptually easier to remember, because it simply flips `F[G[A]]` into `G[F[A]]`. You might have seen this function for `Future` in the standard library.

``````scala> import scala.concurrent.{ Future, ExecutionContext, Await }
import scala.concurrent.{Future, ExecutionContext, Await}
scala> import scala.concurrent.duration._
import scala.concurrent.duration._
scala> val x = {
implicit val ec = scala.concurrent.ExecutionContext.global
List(Future { 1 }, Future { 2 }).sequence
}
x: scala.concurrent.Future[List[Int]] = Future(<not completed>)
scala> Await.result(x, 1 second)
res4: List[Int] = List(1, 2)``````

Another useseful thing might be to turn a `List` of `Either` into an `Either`.

``````scala> List(Right(1): Either[String, Int]).sequence
res5: Either[String,List[Int]] = Right(List(1))
scala> List(Right(1): Either[String, Int], Left("boom"): Either[String, Int]).sequence
res6: Either[String,List[Int]] = Left(boom)``````

Note that we no longer need `sequenceU`.