The Traversable functor is similar to Reducible and Foldable, which we talked about in the previous chapter. The difference is that methods defined on Traversable preserve the underlying structure while going over it, as opposed to the other abstractions which collapse it into the single result. The Traversable defines two methods:

import scala.{ Traversable => _ }

trait Traversable[F[_]] extends Functor[F] {
  def sequence[A,G[_]: Applicative](a: F[G[A]]): G[F[A]]
  def traverse[A,B,G[_]: Applicative](a: F[A])(f: A => G[B]): G[F[B]]
}

Unfortunately, Scala has a deprecated Traversable definition left over from previous versions, so we are getting rid of it by using import renaming. Our Traversable defines the sequence and traverse methods, which loosely correspond to the reduce and fold methods defined on monoids. Starting with the sequence method, we can see that it turns its argument inside out. This is exactly what we needed to make our new cook happy. Let's skip the implementation part for a moment and see how it works in practice:

scala> println(freshPie)
List(None, None, Some(FishPie(38)))

scala>println(ch08.Traversable.bucketTraversable.sequence(freshPie))
None

As soon as we have None in the list, we're getting None back as the result. Let's give it another try:

scala> println(freshPie)
List(Some(FishPie(40)), Some(FishPie(27)), Some(FishPie(62)))

scala> println(ch08.Traversable.bucketTraversable.sequence(freshPie))
Some(List(FishPie(40), FishPie(27), FishPie(62)))

If all of the fish are fresh, we get Some bucket of pies, as expected. But we're still not 100% satisfied with this approach. The reason for this is that we first bake all of the fresh pies we possibly can and then discard them in the case that not all of the fish was fresh. Instead, we would like to stop as soon as we encounter the first rotten fish. This is what the traverse method is for. Using it, we can implement our baking process like so:

ch08.Traversable.bucketTraversable.traverse(bucketOfFish) { a: Fish =>
  checkHonestly(Option.empty[FreshFish])(a).map(f => bakePie(f, 10, 0.2f))
}

Here, we're traversing over the bucketOfFish. We're using bucketTraversable for this. It expects a function called Fish => G[?] so that G is applicative. We can satisfy this requirement by providing a function called Fish => Option[FishPie]. We're using checkHonestly to lift a Fish into the Option[FreshFish], and then we need to map over it with our original bakePie method.

How is traverse implemented? Unfortunately, the implementation for this requires knowing the structure of the effect so that it can be preserved. Because of this, it needs to be implemented for each instance of the type class or delegated to another abstraction where this knowledge is preserved, like Foldable.

This is how the traverse method can be implemented for Traversable[List]:

override def traverse[A, B, G[_] : Applicative](a: Bucket[A])(f: A => G[B]): G[Bucket[B]] = {
  val G = implicitly[Applicative[G]]
  a.foldRight(G.unit(List[B]()))((aa, fbs) => G.map2(f(aa), fbs)(_ :: _))
}

To preserve the structure of the list, we foldRight over it, starting by lifting an empty list into the context of G. We're using map2 in each fold iteration to call the provided function on the next element of the original list, lift it into G, and append it to the result.

For the Option, we could use an approach similar to what we used for fold, but as we only need to handle two cases, a pattern matching implementation reveals the intent much better:

implicit val optionTraversable = new Traversable[Option] {
  override def map[A, B](in: Option[A])(f: A => B): Option[B] =
   Functor.optionFunctor.map(in)(f)
  override def traverse[A, B, G[_] : Applicative](a: Option[A])(f: A => G[B]): G[Option[B]] = {
    val G = implicitly[Applicative[G]]
    a match {
      case Some(s) => G.map(f(s))(Some.apply)
      case None => G.unit(None)
    }
  }
}

We're just lifting the Option into the context of G by using the appropriate methods for different states of an Option. It is worth noting that we're using Some.apply directly in the case of the non-empty Option to preserve the structure as required.

The good news is that the second method, sequence, is less powerful than traverse. Because of this, it can be defined directly on Traversable in terms of traverse:

def sequence[A,G[_]: Applicative](a: F[G[A]]): G[F[A]] = traverse(a)(identity)

It just uses the identity function to return a proper value of G[A], as expected by traverse. 

Being a functor, Traversables also compose. The compose function will have the following signature:

trait Traversable[F[_]] extends Functor[F] {
  // ...
  def compose[H[_]](implicit H: Traversable[H]): Traversable[({type f[x] = F[H[x]]})#f]
}

We'll leave the task of implementing this to the reader.

This is how composing Traversables can make life easier. Remember our controversial deeplyPackaged example? This is, once again, what the type of the container looks like:

type DEEP[x] = scala.util.Try[Either[Unit, Bucket[Option[x]]]]

Can you imagine iterating over it and applying some logic to the elements of it? With a composed Traversable, this is absolutely straightforward:

import ch08.Traversable._
val deepTraverse = tryTraversable.compose(eitherTraversable[Unit].compose(bucketTraversable))

val deepYummi = deepTraverse.traverse(deeplyPackaged) { pie: Option[FishPie] =>
  pie.foreach(p => println(s"Yummi $p"))
  pie
}
println(deepYummi)

We first compose the Traversable to match our nested types. Then, we traverse over it, as we did previously. Please note how we omitted the bottom Option type and have it as a wrapper type for the function parameter for traverse. This is the output of the preceding snippet:

Yummi FishPie(71)
Yummi FishPie(5)
Yummi FishPie(82)
Some(Success(Right(List(FishPie(82), FishPie(5), FishPie(71)))))

Does it feel like you have superpowers yet? If you're still not feeling it, we have something more to offer in the next chapter!