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 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:
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.
We will not get the same response for the non-commutative operations. We can see it in below examples:
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:
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.
Now we will see that how can we resolve this issue?
But rest collections which we use most commonly, come with the stack safety.
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.