ScalaFP: Let’s discuss about Foldable

In our today’s blog, we are going to discuss a type of iterator called foldable that is used to iterate over collections. Foldable is an abstraction for the foldLeft & foldRight. We will now look in the Foldable.

Foldable

Foldable type class contains the foldLeft & foldRight are instances of foldable which we are used on List, Vector, and Stream. We can create generic folds with the help of Foldable.

Let’s recap on the topic of folding. We have accumulator value and a binary func on to combine it with each item in the sequence:

scala> def showLeft[A](list: List[A]): String =
     | list.foldLeft("nil")((accum, item) => s"$item then $accum")
show: [A](list: List[A])String

scala> showLeft(Nil)
res0: String = nil

scala> showLeft(List(1, 2, 3))
res1: String = 3 then 2 then 1 then nil

scala> def showRight[A](list: List[A]): String =
    | list.foldRight("nil")((accum, item) => s"$item then $accum")
showRight: [A](list: List[A])String

scala> showRight(List(1, 2, 3))
res3: String = nil then 3 then 2 then 1

So as we can see here,  we have created two methods showLeft and showRight. These methods will work down recursively on the sequence. We can see that foldLeft traverses from “left” to “right” (start to finish) and foldRight traverses from “right” to “left” (finish to start). foldLeft and foldRight are equivalent if we are performing the commutative operations.

scala> List(1, 2, 3).foldLeft(0)(_ + _)
res4: Int = 6

scala> List(1, 2, 3).foldRight(0)(_ + _)
res5: Int = 6

We will not get the same response for the non-commutative operations. We can see it in below examples:

scala> List(1, 2, 3).foldLeft(0)(_ - _)
res6: Int = -6

scala> List(1, 2, 3).foldRight(0)(_ - _)
res7: Int = 2

Foldable in Cats

In Cats, Foldable is an abstraction over the foldLeft and foldRight into type class. The instance of foldable define these two methods. Cats provide out-of-the-box instances of Foldable to help iterate over the List, Vector, Stream and Option data types.

foldLeft with Foldable

Let’s see some example with the help of List and Stream. We will perform foldLeft over the list and stream:

import cats.Foldable
import cats.instances.list._
import cats.instances.stream._

val list = List(1,2,3,4,5,6)
val updatedList = Foldable[List].foldLeft(list, 0)(_ + _)  //21

val stream = Stream(1, 3, 5)
val updatedStream = Foldable[Stream].foldLeft(stream, 0)(_ + _) //9

foldRight with Foldable

foldRight is not defined as foldLeft in the Foldable for the Eval of monads. Eval is a monad that allows us to abstract over different models of evaluation. We typically hear of two such models: eager and lazy. Eval throws in a further distinction on of whether or not a result is memoized. We will discuss that how does foldRight work in the terms of Eval Monads:

def foldRight[A, B](fa: F[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B]

Eval comes with one condition which is that folding is always stack safe, even when the collection’s default definition of foldRight is not.

Implementation of the foldRight for the stream is not stack safe and it will send StackOverFlowError while working with a stream that has huge amounts of data.

import cats.Eval
import cats.Foldable

def stream = (1 to 1000000).toStream
stream.foldRight(0L)(_ + _) // java.lang.StackOverflowError ...

Now we will see that how can we resolve this issue?

import cats.Eval
import cats.instances.stream._

def bigData = (1 to 1000000).toStream
val eval: Eval[Long] =
Foldable[Stream].
foldRight(bigData, Eval.now(0L)) { (num, eval) =>
eval.map(_ + num)
}
eval.value // 500000500000

But rest collections which we use most commonly, come with the stack safety.

scala> (1 to 1000000).toList.foldRight(0L)(_ + _)
res2: Long = 500000500000

scala> (1 to 1000000).toVector.foldRight(0L)(_ + _)
res3: Long = 500000500000

In this blog, we have discussed the usage of foldable in scala cats along with the foldRight, foldLeft, and foldable wrapper.

If you have any doubt or suggestion, let me know in comments.

Thanks 🙂