reduceLeftM doesn't short-circuit

[travisbrown]

It seems like it should be possible for reduceLeftM to short-circuit, since e.g. foldLeftM does:

scala> import cats.data.NonEmptyStream, cats.implicits._
import cats.data.NonEmptyStream
import cats.implicits._

scala> def f(i: Int): Either[Int, Int] = if (i < 100000) Right(i) else Left(i)
f: (i: Int)Either[Int,Int]

scala> val s = NonEmptyStream(0, Stream.from(1))
s: cats.data.package.NonEmptyStream[Int] = OneAnd(0,Stream(1, ?))

scala> s.foldLeftM(0)((b, a) => f(a).map(_ + b))
res3: scala.util.Either[Int,Int] = Left(100000)

scala> s.reduceLeftM(f)((b, a) => f(a).map(_ + b)) // hangs forever.

This is probably related to #3200, which isn't itself a bug, but if we had a working reduceLeftM we could write reduceMapM in terms of it.

[kevinmeredith]

FYI (to those following the issue out of curiosity like me), I had to supply type parameters for s.foldLeft... to compile:

@ import $ivy.`org.typelevel::cats-core:2.1.0`                             

@ import cats.data.NonEmptyStream, cats.implicits._ 
import cats.data.NonEmptyStream, cats.implicits._

@ def f(i: Int): Either[Int, Int] = if (i < 100000) Right(i) else Left(i) 
defined function f

@ val s = NonEmptyStream(0, Stream.from(1)) 
...

@ s.foldLeftM(0)((b, a) => f(a).map(_ + b)) 
cmd4.sc:1: no type parameters for method foldLeftM: (f: (Int, Int) => G[Int])(implicit G: cats.Monad[G])G[Int] exist so that it can be applied to arguments ((Int, Int) => scala.util.Either[Int,Int])
 --- because ---
argument expression's type is not compatible with formal parameter type;
 found   : (Int, Int) => scala.util.Either[Int,Int]
 required: (Int, Int) => ?G[Int]

val res4 = s.foldLeftM(0)((b, a) => f(a).map(_ + b))
                      ^
cmd4.sc:1: type mismatch;
 found   : (Int, Int) => scala.util.Either[Int,Int]
 required: (Int, Int) => G[Int]
val res4 = s.foldLeftM(0)((b, a) => f(a).map(_ + b))
                                 ^
cmd4.sc:1: Could not find an instance of Monad for G
val res4 = s.foldLeftM(0)((b, a) => f(a).map(_ + b))
                         ^
Compilation Failed

@ type EitherInt[A] = Either[Int, A] 
defined type EitherInt

@ s.foldLeftM[EitherInt, Int](0)((b, a) => f(a).map(_ + b)) 
res5: EitherInt[Int] = Left(100000)

@ s.reduceLeftM[EitherInt, Int](f)((b, a) => f(a).map(_ + b)) 
^C
Interrupted! (`repl.lastException.printStackTrace` for details)

[travisbrown]

@kevinmeredith You definitely can provide the type parameters to resolve that issue, but you're far better off enabling -Ypartial-unification (or migrating to 2.13, where it's on by default), since this is something you'll run into all the time when working with Cats. See the Getting Started section of the docs for more detail about the fix, or this old blog post of mine for some explanation of the underlying problem.