Early-stops in folds in Scala with Cats

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._
val computed: Int =
  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
    }
    .merge // we're merging Either[Int,Int] to Int

An additional feature here is if you really need it, 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.