foldLeft v. foldRight - does it matter?

Question

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?

Answer 1

@Rein Henrichs' answer is indeed irrelevant to Scala, because Scala's implementation of foldLeft and foldRight is completely different (for starters, Scala has eager evaluation).

foldLeft and foldRight 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 function f that is given. foldRight is slower by a constant factor because of the additional reverse, 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 to foldRight. In your example, the foldRight version is best, because the anonymous function that you give to foldRight is O(1). In contrast, the anonymous function that you give to foldLeft is O(n) itself (amortized, which is what matters here), because acc 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 or foldRight, but not because of these functions themselves, but because of the anonymous functions given to them. If both are equivalent, choose foldLeft by default.