Why does scala reduce() and reduceLeft() reduce the sequence of the values in the same way?

user_8572540 0
Viewed 865

If I run:

List(1, 4, 3, 9).reduce {(a, b) => println(s"$a + $b"); a + b}

The result is:

1 + 4
5 + 3
8 + 9

However, If I use reduceLeft instead of reduce, it also prints:

1 + 4
5 + 3
8 + 9

I have thought that reduce reduces the sequence of values in this way:

(1+4) + (3+9)
(5) + (12)
(17)

What is the real difference between reduceLeft and reduce?

scala collections
2 Answers

Take a look at the type of the two functions:

def reduce[B >: A](op: (B, B) => B): B 
def reduceLeft[B >: A](op: (B, A) => B): B

Notice, how the second argument to op in reduceLeft is A (same as the element type), while in reduce it is B (same as the return value).

This is an important difference. The operation in reduce must be associative, meaning that you can split the list into several segments, apply operation to each of them separately, and then apply it again to the results to combine.

This is important when you want to do things in parallel: reduce can be applied in parallel to different parts of the list, and then the results can be combined.

reduceLeft on the other hand, can only work sequentially (left to right, as the name implies), operation does not have to be associative, and can expect its second parameter to always be an element of the sequence (and the first one – result of the operation so far);

Consider

    val sum = (1 to 100).reduce(_ + _)

This yields the same result as (1 to 100).reduceLeft(_ + _), except that the former can be parallelized. On the other hand:

    val strings = (1 to 100).reduceLeft[Any](_.toString + ";" + _.toString)

Should not be written as reduce (even though, in this contrived example, it can, and will even work as long as you stick with serial processing), because the result depends on the order in which elements are fed to the operation.

user_42545170

The difference is:

  1. reduce is allowed to reduce in any order; for a List it happens to be the same as reduceLeft because it's more efficient (and it's the default implementation for IterableOnceOps subtypes, so most of them will be the same). For another collection it could be equivalent to reduceRight, and for a tree type it may be more as you expected.

  2. different type signatures:

    reduce[B >: A](op: (B, B) => B): B

    versus

    reduceLeft[B >: A](op: (B, A) => B): B

    because the first parameter to op in reduceLeft is always an element of the collection it's called on, but for reduce it could be the result of a recursive reduce call.

alexey_r_92040
Related