Early-stops in folds in Scala with Cats

Abdulla Abdurakhmanov
Apr 21 · 2 min read

Catamorphism (e.g. ‘fold’) is a great concept in purely functional programming. It is a common case when you want to “fold” the whole structure into another with the initial value.

However, sometimes it might be confusing even in simple cases.

Let’s say you want to sum your list of int values (which, of course, has been already implemented as sum for you in the Scala Collection Library).

This should be easy:

List(1,2,3,4,5).foldLeft(0)( _ + _ )

Now let’s say you’d like to stop counting and computation if your sum is more than some specified max value:

val max = 5
List(1,2,3,4,5).foldLeft(0) { case (total, x) =>
val ux = total + x if ( ux < max )
ux
else
??? // Now what?
// We can't continue and have to stop
// 2 reasons to stop:
// - avoid wasting of computational resources
// (imagine if you have very long stream of values)
// - possible incorrect results
// without additional conditional params
}

So, basically we’re looking for some kind of `foldWhile`, but unfortunately there isn’t a ready to use function in the Scala library.

There are solutions for this:

  • Own tail-recursive function instead fold
  • Use gruesome return (and ready to be hated by your teammate).
  • Use throw (not much better… or even worse?)
  • Use while and var (an imperative style)
  • And finally, my favourite one, use foldM from Cats and Either from Scala
import cats.implicits._List(1,2,3,4,5).foldM(0) { case (total, x) =>  val ux = total + x  if ( ux < max )
ux.asRight // implicitly creates Either.Right here
else
total.asLeft // implicitly creates Either.Left here
}

And because of the Either result, you can detect if it was an early stop or not (Either.Left for an early-stop in our example).

This little trick helps to be more productive, enjoy.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store