Previously, Nicolas Rinaudo answered my question on Scala's List foldRight Always Using foldLeft?
Studying Haskell currently, my understanding is that foldRight
should be preferred over foldLeft
in cases where ::
(prepend) can be used over ++
(append).
The reason, as I understand, is performance – the former occurs in O(1)
, i.e. add an item to the front – constant time. Whereas the latter requires O(N)
, i.e. go through the whole list and add an item.
In Scala, given that foldLeft
is implemented in terms of foldRight
, does the benefit of using :+
over ++
with foldRight
even matter since foldRight
gets reversed, and then foldLeft'd
?
As an example, consider this simple fold..
operation for simply returning a list's elements in order.
foldLeft
folds over each element, adding each item to the list via :+
.
scala> List("foo", "bar").foldLeft(List[String]()) {
(acc, elem) => acc :+ elem }
res9: List[String] = List(foo, bar)
foldRight
performs a foldLeft with ::
operator on each item, but then reverses.
scala> List("foo", "bar").foldRight(List[String]()) {
(elem, acc) => elem :: acc }
res10: List[String] = List(foo, bar)
In reality, does it matter in Scala which foldLeft
or foldRight
to use given that foldRight
uses foldRight
?
Best Answer
@Rein Henrichs' answer is indeed irrelevant to Scala, because Scala's implementation of
foldLeft
andfoldRight
is completely different (for starters, Scala has eager evaluation).foldLeft
andfoldRight
themselves have actually very little to do wrt the performance of your program. Both are (liberally speaking) O(n*c_f) where c_f is the complexity of one call to the functionf
that is given.foldRight
is slower by a constant factor because of the additionalreverse
, though.So the real factor that differentiates one from the other is the complexity of the anonymous function that you give. Sometimes, it is easier to write an efficient function designed to work with
foldLeft
, and sometimes tofoldRight
. In your example, thefoldRight
version is best, because the anonymous function that you give tofoldRight
is O(1). In contrast, the anonymous function that you give tofoldLeft
is O(n) itself (amortized, which is what matters here), becauseacc
keeps growing from 0 to n-1, and appending to a list of n elements is O(n).So it actually matters whether you choose
foldLeft
orfoldRight
, but not because of these functions themselves, but because of the anonymous functions given to them. If both are equivalent, choosefoldLeft
by default.