Shall we base Foldable on `Iterator`?

[julien-truffaut]

Currently Fold is based on foldMap

trait Fold[S, A] {
  def foldMap[M: Monoid](f: A => M)(s: S): M
}

The problem is that foldMap is not lazy, so when we use foldMap to implement headOption or find, we need to traverse the entire dataset.

val list = List(1, 2, 3, 4)
var counter = 0

val result = Fold.fromFoldable[List, Int].foldMap{x => counter +=1; Option(x)}(list)(Monoids.firstOption)

assertEquals(result, Some(1))
assertEquals(counter, 4)

counter is equal to 4, we traverse the entire list.

An alternative encoding could be based on Iterator which would allow a simple and lazy implementation for headOption, find, and so on.

trait Fold[S, A] { self =>
  def iterator(from: S): Iterator[A]

  def andThen[B](other: Fold[A, B]): Fold[S, B] = new Fold[S, B] {
    def iterator(from: S): Iterator[B] = self.iterator(from).flatMap(other.iterator)
  }
}

[yilinwei]

I think this would be better - non-laziness for this type of operation is really unexpected.

[julien-truffaut]

@yilinwei Yeah I agree. Are you ok with exposing an Iterator? I think it is simple and does the job.

[yilinwei]

I took a quick look at the issues in cats, since I remember they had some issues with it.

I don't think we'll run into this issue as long as S => Iterator[A] returns a fresh instance of an iterator.

[1] https://github.com/typelevel/cats/issues/1716