How do you improve the performance of foldLeft (or scanLeft) when you don't always need to examine all the elements of a list?

Question

For example if you have millions of elements, but typically only need to examine the first million(e.g. if you are accumulating a sum and you saturate at some max value or you have some other complex data structure you are building, but you finish after examining the first M elements). FoldLeft always forces you to iterate over the entire sequence. Ideally, you could supply a predicate that lets foldLeft know you are done.

If scanLeft is evaluated lazily(?), perhaps scanLeft along with a find (find first valid element) can accomplish this. I believe something like this would work in Haskell, but not sure about Scala.

numbers.scanLeft(0)((a, b) => a + b).find(_ >= 100)

So if numbers = List(100,0,9,10), then scanLeft will only look at the first element.

Does this help? [Abort early in a fold](https://stackoverflow.com/questions/12892701/abort-early-in-a-fold) — jrook, Jan 22 '20 at 20:00
That answer seems to abort and not return an answer. Anyway, the answer presented here is much more elegant and enlightening. — yalis, Jan 23 '20 at 20:45
I linked the question not the answer. A range of solutions has been offered in the answers to that question which might be helpful in addition to the answer here. Using lazy collections has also been mentioned in that question and its answers although in a different way. — jrook, Jan 23 '20 at 20:52

Luis Miguel Mejía Suárez · Accepted Answer · 2020-04-11T18:33:31.230

scanLeft produces a lazy collection for already lazy collections, like Iterator or LazyList (Strem prior 2.13). Thus, you can use that to abort early.
For example:

LazyList.continually(100)
  .scanLeft(0) { case (acc, n) => acc + n }
  .takeWhile(_ < 1000)
  .toList
// res: List[Int] = List(0, 100, 200, 300, 400, 500, 600, 700, 800, 900)

List(0, 100, 5, 300)
  .iterator
  .map(i => { println(i); i })
  .scanLeft(0) { case (acc, n) => acc + n }
  .find(_ >= 100)
// 0
// 100
// res: Option[Int] = Some(100)

How do you improve the performance of foldLeft (or scanLeft) when you don't always need to examine all the elements of a list?

1 Answers1