Shall we base Foldable on `Iterator`?

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)
  }
}