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 capable version 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]() lifted 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 appending 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.