`Foldable` instance for `List` breaks substitution

[noelwelsh]

The Foldable instance for List breaks substitution, as the following program demonstrates. The value of result.value differs between the first and subsequent calls.

import cats.instances.list._
import cats.Eval
import cats.syntax.foldable._

val result  = List.range(0,10).foldM(List.empty[Int])((accum, elt) => Eval.always(elt :: accum))

result.value
// res: List[Int] = List(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

result.value
// res: List[Int] = List(0)

I haven't had time to debug but I suspect it relates to the use of a mutable ListBuffer in the implementation of tailRecM.

[peterneyens]

It is the use of an iterator in foldM using Foldable.iteratorFoldM.

With the default implementation of foldM it evaluates both times :

import cats.instances.list._
import cats.Eval

val numbers = List.range(0, 10)
val result = Foldable[List].foldLeft(numbers, Eval.now(List.empty[Int])) { (eb, a) => 
  eb.flatMap(acc => Eval.always(a :: acc))
}

result.value
// List[Int] = List(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

result.value
// List[Int] = List(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

[peterneyens]

If we change the foldM implementations which use Foldable.iteratorFoldM to use the default implementation, we probably need to reopen #1030, because the default implementation always folds across the entire structure while the implementation using Iterator and tailRecM can short circuit (added in #1414).

A potential solution may be @TomasMikula 's #1117.

[kailuowang]

@peterneyens shall we schedule #1117 to 1.0.0-MF then? I feel bad that we let it fell through the cracks.

[ceedubs]

I've approved #1117. It would be great to get some other reviewers on that. If/when it's merged we probably want to remove Foldable.iteratorFoldM, since it leads to these sorts of issues.

[johnynek]

Yeah, it seems like Foldable.iteratorFoldM is just not safe for "rerunning" monads. Since you can't tell if you have a monad like that or not when it is generic, it's only safe if you concretely know the monad you are using.