JetBrains/kotlin — pull request #74 by zolotov (2012-06-15 10:06:31+00:00)
Title: Fix foldRight implementation for iterables

In Scala ```foldLeft``` and ```foldRight``` has extremely simple definition. ```foldLeft``` function groups elements of array from left and processes grouped pairs with given operation. E.g. array ```(1, 2, 3, 4)``` with operation ```+``` and initial value ```0``` processes as

((((0 + 1) + 2) + 3) + 4)

```foldRight``` function should do the same, but from right side of array:

(1 + (2 + (3 + (4 + 0))))

Current implementation of ```foldRight``` folds of reversed array from left in fact (It's not really right-folding, but literally left-folding of reversed array:)).

It does not make sense with commutative operation:

Correct implementation (1, 2, 3).foldRight(0, +) => (1 + (2 + (3 + 0))) => 6
Current implementation (1, 2, 3).foldRight(0, +) => (3, 2, 1).fold(0, +) => (((0 + 3) + 2) + 1) => 6

But current implementation gives wrong answer with noncommutative operation:

Correct implementation (1, 2, 3).foldRight(0, -) => (1 - (2 - (3 - 0))) => 2
Current implementation (1, 2, 3).foldRight(0, -) => (3, 2, 1).fold(0, -) => (((0 - 3) - 2) - 1) => -6

According to the ```foldRightTest``` in ```CollectionTest``` current implementation is correct. But according to [Scala implementation](http://www.scala-lang.org/archives/downloads/distrib/files/nightly/docs/library/scala/collection/TraversableOnce.html) or [Wolfram implementation](http://reference.wolfram.com/mathematica/ref/Fold.html) of this methods ```foldRightTest``` is wrong too.

## To discuss

Scala distinguishes methods ```fold``` and ```foldLeft```. ```fold``` function uses given comparator to define folding order. May be it make sense to rename kotlin ```fold``` function to ```foldLeft``` and create extra ```fold``` function with comparator.