Short-circuit on foldLeft

FoldLeftSC

A Foldable.foldLeftimplementation that short-circuits on a given predicate

The first attempt was a failure. Using foldM and Option.

def foldLeft[F[_]: Foldable, A, B](fa: F[A])(b: B)(f: (B, A) => B)(p: B => Boolean): B = 
  Foldable[F].foldM[Option,A,B](fa, b) { 
    case (b, a) if !p(b) => none or b.some
    case (b, a) => f(b,a).some
  }.getOrElse(b)

Both implementation did actually not do what we want:

The first one, using none, will short-circuit as expected but will always return none.
The second one, using some, will accumulate while skipping the elements that do not fulfill the predicate.

The solution is use foldM but Either[B,B] instead of Option:

def foldLeft[F[_]: Foldable, A, B](fa: F[A])(b: B)(f: (B, A) => B)(p: B => Boolean): B =
      Foldable[F].foldM[Either[B, ?],A,B](fa, b) {
        case (b, a) if !p(b) => b.asLeft
        case (b, a) => f(b,a).asRight
      } match {
      case Left(b) => b
      case Righ(b) => b
    }

// Should return 3
foldLeft(List(1,2,3,4,5))(0)(_ + _)(_ < 3)
// res0: 3

Which is actually the same as traverse :-)

monadplus/short-circuit-foldleft.md

FoldLeftSC