# Foldable vs Traverse In Scala

This post is last sequel to Monad In Scala, Applicative vs Monad in Scala, Semigroup And Monoid In Scala and Monad vs Monoid In Scala.

We will wrap up our journey by introducing two new useful typeclasses that build upon `Monoid`

and `Applicative`

. But keep in mind that `Foldable`

and `Traverse`

**do not extend** `Monoid`

and `Applicative`

.

`Monoid`

and `Applicative`

are **structure-preserving** (in category theory, this is called **homomorphism** in that the shape stays the same during mapping of inner values). For example, `Future[Int] |+| Future[Int]`

produces another `Future[Int]`

and `(Future[Int] |@| Future[Int]) { _.toString + _.toString }`

produces `Future[String]`

. Here, the **structure** or **shape** denotes the instance of respective `Monoid`

and `Applicative`

, which are `Future[Int]`

and `Future`

(this is why `Applicative`

can freely change the type of inner value while `Monoid`

cannot.) This rule applies to all other typeclasses we’ve looked so far.

However, `Foldable`

and `Traverse`

are some different kinds. They are not structure-preserving (in category theory, this is called **catamorphism** which is a mere generalization over familiar `fold`

method in programming). And this is why these typeclasses do not extend the typeclasses we’ve looked at so far. But `Foldable`

do **rely** on `Monoid`

just as `Traverse`

do **rely** on `Applicative`

. We will see what I mean by this.

## Foldable

`Foldable`

is a typeclass that enables us to `fold`

over its instance.

I won’t go into too much details about `Foldable`

since everything is pretty straightforward and many programmers are already sufficiently familiar with `fold`

. And scala standard library already provides methods implemented by `Foldable`

like `foldLeft`

, `foldRight`

, `find`

etc.

But when you define your own custom class, you may want to form `Foldable`

since you can get myriads of useful methods just by implementing `fold`

method. Some of the derived methods are `find`

, `forAll`

, `minimum`

etc. As you can see all these methods **reduce** to a single value. `find`

reduces single element found, `forAll`

reduces to single `Boolean`

value to tell whether all elements pass the given predicates and so on.

What’s important with `Foldable`

is that it relies on `Monoid`

to `fold`

. The value that you `fold`

into must be an instance of `Monoid`

.

Look at the type signature primitive method `foldMap`

from scalaz (many functional libraries seem to diverge on this matter. Libraries may require `foldLeft`

, `fold`

, or `foldMap`

):

```
def foldMap[A,B](fa: F[A])(f: A => B)(implicit F: Monoid[B]): B
```

and for the sake of simplicity, let’s assume that we are dealing with `List`

foldable instance with `String`

inner values and `fold`

into `Int`

value. With that in mind:

```
def foldMap(fa: List[String])(f: String => Int)(implicit F: Monoid[Int]): Int
```

The way this would be implemented is straightforward. You’d `map`

`List[String]`

into `List[Int]`

using `f`

and then `combine`

`List[Int]`

to `Int`

using `Monoid[Int]`

(remember `Monoid`

can `combine`

over **indeterminate** number of values?)

But `Foldable`

isn’t all that useful since we can already do `fold`

without having to form `Foldable`

instance. Let’s look at `Traverse`

## Traverse

`Traverse`

is a typeclass that enables us to `traverse`

over its instance and since it extends `Foldable`

, it also has access to all of its methods. `Traverse`

also extends `Functor`

but we wont discuss its implications here.

`Traverse`

is an extremely useful typeclass but like every other useful functional concepts, it comes with steep learning curve.

First of all, here is documentation on `Traverse`

from cats library:

Traverse, also known as Traversable. Traversal over a structure with an effect. Traversing with the [[cats.Id]] effect is equivalent to [[cats.Functor]]#map. Traversing with the [[cats.data.Const]] effect where the first type parameter has a [[cats.Monoid]] instance is equivalent to [[cats.Foldable]]#fold.

To illustrate what it is, let’s first look at what it can do:

```
def fetchUser(user_id: Int): Future[User] = ???
fetchUser(1) // Future[User]
```

We have this method that fetches `User`

from somewhere. Now let’s say we need to fetch multiple users at once. Should we implement another methods that accept `List[Int]`

and return `Future[List[User]]`

? No. We use `traverse`

.

```
val user_ids = List(1,2,3,4,5) // List[Int]
user_ids.traverse(user_id => fetchUser(user_id)) // Future[List[User]]
```

This is amazing and it’s extremely useful in many use cases. Now let’s look at how this is possible.

Let’s first look at the signature of primitive method `traverseImpl`

from scalaz (`traverseImpl`

is exactly the same as `traverse`

method. Why scalaz chose this as primitive method is beyond me.):

```
def traverseImpl[G[_]:Applicative,A,B](fa: F[A])(f: A => G[B]): G[F[B]]
```

And let’s make a few assumptions to make this readable. Our `Traverse`

instance is `List`

and the type of its values is `Int`

. And the function we pass to `traverseImpl`

will return `Future[User]`

.

```
def traverseImpl(fa: List[Int])(f: Int => Future[User])(implicit F: Applicative[Future]): Future[List[User]]
```

As you can see, `F`

became `List`

, `A`

became `Int`

, `G`

became `Future`

and `B`

became `User`

.

Like how `Foldable`

relies on `Monoid`

, its more * capable* version

`Traverse`

relies on `Monoid`

’s more *version*

**capable**`Applicative`

. I used the term **capable**very liberally as in being less restricted and more flexible. Remember how

`Monoid`

is convertible to `Applicative`

but not the other way around? So `traverse`

requires whatever type that wraps the final result (`List[User]`

) to be an `Applicative`

. Why?

Let’s look at how `Traverse[List]`

would implement `traverseImpl`

with the assumptions we made above:

```
def traverseImpl(l: List[Int])(f: Int => Future[User])(implicit F: Applicative[Future]): Future[List[User]] =
l.foldLeft(F.point(List[User]())) { (i: Int, flu: Future[List[User]]) => flu |@| f(i) { (lu: List[User], u: User) => lu :+ u } }
```

This implementation is not performant at all but I’ve simplified things for the sake of illustration.

So it looks pretty simple. we have `List[Int]`

and `fold`

over it to `Future[List[User]]`

where we start with empty `List[User]()`

**lift**ed into `Future`

using `F.point`

. And the function passed to `fold`

simply `combine`

`Future[List[User]]`

and `Future[User]`

(which is the result of `f(i)`

) by `append`

ing `User`

into `List[User]`

.

As you can see, we must have `Applicative`

instance as wrapping type to be able to do `foldLeft`

, which requires an initial value to `fold`

with.

That’s it. `Traverse`

it is. I won’t go into details about how `Traverse`

can implement `Foldable`

’s `foldLeft`

and `Functor`

’s `map`

since this is already a long post.

## Takeaway

Use `Traverse`

when you have a function that accepts `A`

(eg. `Int`

) returns an `Applicative[B]`

(eg. `Future[User]`

) and you want to **lift** that function to work on `Traverse[A]`

(eg. `List[Int]`

) and return `Applicative[Traverse[B]]`

(eg. `Future[List[User]]`

).

This is an extremely useful concept if you take time to learn it. It enables maximum code reuse with elegant solution.