concept Traverse in category functional programming

This is an excerpt from Manning's book Functional Programming in C#: How to write better C# code. Login to get full access to this book.

Traverse is one of the slightly more esoteric core functions in FP, and it allows you to work with lists of elevated values. It’s probably easiest to approach through an example.

This is a common enough scenario that there’s a specific function called Traverse to address it, and a type for which Traverse can be defined is called a traversable. Figure 13.1 shows the relation between Map and Traverse.

Figure 13.1. Comparing Map and Traverse

13.2.5. Defining Traverse for single-value structures

So far you’ve seen how to use Traverse with an IEnumerable and a function that returns an Option, Validation, Task, or any other applicative. It turns out that Traverse is even more general. That is, IEnumerable isn’t the only traversable structure out there; you can define Traverse for many of the constructs you’ve seen in the book.

If we take a nuts and bolts approach, we can see Traverse as a utility that stacks effects up the opposite way as when performing Map:

Map      : Tr<T> → (T → A<R>) → Tr<A<R>>
Traverse : Tr<T> → (T → A<R>) → A<Tr<R>>

copy

So if we have a function that returns an applicative A, Map returns a type with the A on the inside, whereas Traverse returns a type with the A on the outside.

This is an excerpt from Manning's book Functional Programming in Scala. Login to get full access to this book.

This means that Traverse can extend Foldable and we can give a default implementation of foldMap in terms of traverse:

trait Traverse[F[_]] extends Functor[F] with Foldable[F] { #1 ... def foldMap[A,M](as: F[A])(f: A => M)(mb: Monoid[M]): M = traverse[({type f[x] = Const[M,x]})#f,A,Nothing]( #2 as)(f)(monoidApplicative(mb)) } #1: A trait may list multiple supertraits, separated by the keyword with. #2: Scala can’t infer the partially applied Const type alias here, so we have to provide an annotation.

copy

Note that Traverse now extends both Foldable and Functor! Importantly, Foldable itself can’t extend Functor. Even though it’s possible to write map in terms of a fold for most foldable data structures like List, it’s not possible in general.

So what is Traverse really for? We’ve already seen practical applications of particular instances, such as turning a list of parsers into a parser that produces a list. But in what kinds of cases do we want the generalization? What sort of generalized library does Traverse allow us to write?

12.7. Uses of Traverse

Let’s now explore the large set of operations that can be implemented quite generally using Traverse. We’ll only scratch the surface here. If you’re interested, follow some of the references in the chapter notes to learn more, and do some exploring on your own.

But what is the relationship between Traverse and Foldable? The answer involves a connection between Applicative and Monoid.