 # Traverse

API Documentation: Traverse

In the `Applicative` tutorial we saw a more polymorphic version of the standard library `Future.traverse` and `Future.sequence` functions, generalizing `Future` to be any `F[_]` that's `Applicative`.

``````import cats.Applicative

def traverse[F[_]: Applicative, A, B](as: List[A])(f: A => F[B]): F[List[B]] =
as.foldRight(Applicative[F].pure(List.empty[B])) { (a: A, acc: F[List[B]]) =>
val fb: F[B] = f(a)
Applicative[F].map2(fb, acc)(_ :: _)
}``````

Here `traverse` still has knowledge of `List`, but we could just as easily use `Vector` or some similar data type. Another example is a binary tree:

``````object tree {
sealed abstract class Tree[A] extends Product with Serializable {
def traverse[F[_]: Applicative, B](f: A => F[B]): F[Tree[B]] = this match {
case Tree.Empty()         => Applicative[F].pure(Tree.Empty())
case Tree.Branch(v, l, r) => Applicative[F].map3(f(v), l.traverse(f), r.traverse(f))(Tree.Branch(_, _, _))
}
}

object Tree {
final case class Empty[A]() extends Tree[A]
final case class Branch[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]
}
}

import tree._``````

This suggests an abstraction over "things that can be traversed over," hence `Traverse`.

``````trait Traverse[F[_]] {
def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
}

// Example implementation for List
implicit val traverseForList: Traverse[List] = new Traverse[List] {
def traverse[G[_]: Applicative, A, B](fa: List[A])(f: A => G[B]): G[List[B]] =
fa.foldRight(Applicative[G].pure(List.empty[B])) { (a, acc) =>
Applicative[G].map2(f(a), acc)(_ :: _)
}
}

// Example implementation for Tree
implicit val traverseForTree: Traverse[Tree] = new Traverse[Tree] {
def traverse[G[_]: Applicative, A, B](fa: Tree[A])(f: A => G[B]): G[Tree[B]] =
fa.traverse(f)
}``````

## A note on sequencing

Sometimes you will be given a traversable that has effectful values already, such as a `List[Option[A]]`. Since the values themselves are effects, traversing with `identity` will turn the traversable "inside out."

``import cats.syntax.all._``
``````val list = List(Some(1), Some(2), None)
// list: List[Option[Int]] = List(Some(value = 1), Some(value = 2), None)
val traversed = list.traverse(identity)
// traversed: Option[List[Int]] = None``````

Cats provides a convenience method for this called `sequence`.

``````val sequenced = list.sequence
// sequenced: Option[List[Int]] = None``````

In general `t.map(f).sequence` can be replaced with `t.traverse(f)`.

## Traversables are Functors

As it turns out every `Traverse` is a lawful `Functor`. By carefully picking the `G` to use in `traverse` we can implement `map`.

First let's look at the two signatures.

``````import cats.{Applicative, Traverse}

def traverse[F[_]: Traverse, G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]] = ???

def map[F[_]: Traverse, A, B](fa: F[A])(f: A => B): F[B] = ???``````

Both have an `F[A]` parameter and a similar `f` parameter. `traverse` expects the return type of `f` to be `G[B]` whereas `map` just wants `B`. Similarly the return type of `traverse` is `G[F[B]]` whereas for `map` it's just `F[B]`. This suggests we need to pick a `G` such that `G[A]` communicates exactly as much information as `A`. We can conjure one up by simply wrapping an `A`.

``final case class Id[A](value: A)``

In order to call `traverse` `Id` needs to be `Applicative` which is straightforward - note that while `Id` just wraps an `A`, it is still a type constructor which matches the shape required by `Applicative`.

``````implicit val applicativeForId: Applicative[Id] = new Applicative[Id] {
def ap[A, B](ff: Id[A => B])(fa: Id[A]): Id[B] = Id(ff.value(fa.value))

def pure[A](a: A): Id[A] = Id(a)
}``````

Now we can implement `map` by wrapping and unwrapping `Id` as necessary.

``````import cats.Functor

trait Traverse[F[_]] extends Functor[F] {
def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]

def map[A, B](fa: F[A])(f: A => B): F[B] =
traverse(fa)(a => Id(f(a))).value
}``````

`Id` is provided in Cats as a type alias `type Id[A] = A`.

## Traversables are Foldable

The `Foldable` type class abstracts over "things that can be folded over" similar to how `Traverse` abstracts over "things that can be traversed." It turns out `Traverse` is strictly more powerful than `Foldable` - that is, `foldLeft` and `foldRight` can be implemented in terms of `traverse` by picking the right `Applicative`. However, `cats.Traverse` does not implement `foldLeft` and `foldRight` as the actual implementation tends to be ineffecient.

For brevity and demonstration purposes we'll implement the equivalent `foldMap` method in terms of `traverse` by using `cats.data.Const`. You can then implement `foldRight` in terms of `foldMap`, and `foldLeft` can then be implemented in terms of `foldRight`, though the resulting implementations may be slow.

``````import cats.{Applicative, Monoid, Traverse}
import cats.data.Const

def foldMap[F[_]: Traverse, A, B: Monoid](fa: F[A])(f: A => B): B =
Traverse[F].traverse[Const[B, *], A, B](fa)(a => Const(f(a))).getConst``````

This works because `Const[B, *]` is an `Applicative` if `B` is a `Monoid`, as explained in the documentation of `Const`.