Reduce, fold or scan (Left/Right)?

Question

When should I use reduceLeft, reduceRight, foldLeft, foldRight, scanLeft or scanRight?

I want an intuition/overview of their differences - possibly with some simple examples.

Recommend you see http://stackoverflow.com/questions/25158780/difference-between-reduce-and-foldleft-in-functional-programming-particularly-s — samthebest, Aug 06 '14 at 11:08
Thanks for the pointer. It's a bit above my technical knowledge :) Is there something in my answer that you think should be clarified/changed? — Marc Grue, Aug 06 '14 at 15:20
No, just pointing out a bit of history and the relevance to MPP. — samthebest, Aug 06 '14 at 16:03
Well, strictly speaking the distinction between `reduce` and `fold` is NOT the existence of a start value - rather that is a _consequence_ of a more deep underlying mathematical reason. — samthebest, Aug 06 '14 at 16:16
https://stackoverflow.com/a/73916338/5249621 https://stackoverflow.com/a/75724473/5249621 — Dmytro Mitin, Apr 08 '23 at 08:30

Marc Grue · Accepted Answer · 2013-07-01T20:03:08.373

In general, all 6 fold functions apply a binary operator to each element of a collection. The result of each step is passed on to the next step (as input to one of the binary operator's two arguments). This way we can cumulate a result.

reduceLeft and reduceRight cumulate a single result.

foldLeft and foldRight cumulate a single result using a start value.

scanLeft and scanRight cumulate a collection of intermediate cumulative results using a start value.

Accumulate

From LEFT and forwards...

With a collection of elements abc and a binary operator add we can explore what the different fold functions do when going forwards from the LEFT element of the collection (from A to C):

val abc = List("A", "B", "C")

def add(res: String, x: String) = { 
  println(s"op: $res + $x = ${res + x}")
  res + x
}

abc.reduceLeft(add)
// op: A + B = AB
// op: AB + C = ABC    // accumulates value AB in *first* operator arg `res`
// res: String = ABC

abc.foldLeft("z")(add) // with start value "z"
// op: z + A = zA      // initial extra operation
// op: zA + B = zAB
// op: zAB + C = zABC
// res: String = zABC

abc.scanLeft("z")(add)
// op: z + A = zA      // same operations as foldLeft above...
// op: zA + B = zAB
// op: zAB + C = zABC
// res: List[String] = List(z, zA, zAB, zABC) // maps intermediate results

From RIGHT and backwards...

If we start with the RIGHT element and go backwards (from C to A) we'll notice that now the second argument to our binary operator accumulates the result (the operator is the same, we just switched the argument names to make their roles clear):

def add(x: String, res: String) = {
  println(s"op: $x + $res = ${x + res}")
  x + res
}

abc.reduceRight(add)
// op: B + C = BC
// op: A + BC = ABC  // accumulates value BC in *second* operator arg `res`
// res: String = ABC

abc.foldRight("z")(add)
// op: C + z = Cz
// op: B + Cz = BCz
// op: A + BCz = ABCz
// res: String = ABCz

abc.scanRight("z")(add)
// op: C + z = Cz
// op: B + Cz = BCz
// op: A + BCz = ABCz
// res: List[String] = List(ABCz, BCz, Cz, z)

.

De-cumulate

From LEFT and forwards...

If instead we were to de-cumulate some result by subtraction starting from the LEFT element of a collection, we would cumulate the result through the first argument res of our binary operator minus:

val xs = List(1, 2, 3, 4)

def minus(res: Int, x: Int) = {
  println(s"op: $res - $x = ${res - x}")
  res - x
}

xs.reduceLeft(minus)
// op: 1 - 2 = -1
// op: -1 - 3 = -4  // de-cumulates value -1 in *first* operator arg `res`
// op: -4 - 4 = -8
// res: Int = -8

xs.foldLeft(0)(minus)
// op: 0 - 1 = -1
// op: -1 - 2 = -3
// op: -3 - 3 = -6
// op: -6 - 4 = -10
// res: Int = -10

xs.scanLeft(0)(minus)
// op: 0 - 1 = -1
// op: -1 - 2 = -3
// op: -3 - 3 = -6
// op: -6 - 4 = -10
// res: List[Int] = List(0, -1, -3, -6, -10)

From RIGHT and backwards...

But look out for the xRight variations now! Remember that the (de-)cumulated value in the xRight variations is passed to the second parameter res of our binary operator minus:

def minus(x: Int, res: Int) = {
  println(s"op: $x - $res = ${x - res}")
  x - res
}

xs.reduceRight(minus)
// op: 3 - 4 = -1
// op: 2 - -1 = 3  // de-cumulates value -1 in *second* operator arg `res`
// op: 1 - 3 = -2
// res: Int = -2

xs.foldRight(0)(minus)
// op: 4 - 0 = 4
// op: 3 - 4 = -1
// op: 2 - -1 = 3
// op: 1 - 3 = -2
// res: Int = -2

xs.scanRight(0)(minus)
// op: 4 - 0 = 4
// op: 3 - 4 = -1
// op: 2 - -1 = 3
// op: 1 - 3 = -2
// res: List[Int] = List(-2, 3, -1, 4, 0)

The last List(-2, 3, -1, 4, 0) is maybe not what you would intuitively expect!

As you see, you can check what your foldX is doing by simply running a scanX instead and debug the cumulated result at each step.

Bottom line

Cumulate a result with reduceLeft or reduceRight.
Cumulate a result with foldLeft or foldRight if you have a start value.
Cumulate a collection of intermediate results with scanLeft or scanRight.
Use a xLeft variation if you want to go forwards through the collection.
Use a xRight variation if you want to go backwards through the collection.

If I'm not mistaken, the left version can use tail call optimization, which means it is much more efficient. — Trylks, Aug 11 '14 at 11:27
@Marc, I like the examples with letters, it made things very clear — Muhammad Farag, Jul 18 '15 at 21:13
@TimothyKim it can, with non-straightforward implementations optimised to do so. E.g. In the [particular case of Scala lists](https://github.com/scala/scala/blob/2.12.x/src/library/scala/collection/immutable/List.scala), that way consists on reversing the `List` to then apply `foldLeft`. Other collections may implement different strategies. In general, if `foldLeft` and `foldRight` can be used interchangeably (associative property of the applied operator), then `foldLeft` is more efficient and preferable. — Trylks, Apr 21 '16 at 18:57
@Trylks Both `xLeft` and `xRight` have the same asymptotic complexity and can be implemented in a tail-recursive way. The actual implementation in the Scala standard library however is impure (for efficiency). — 6infinity8, Oct 16 '21 at 08:27

Puneeth Reddy V · Answer 2 · 2015-07-17T06:36:22.013

Normally REDUCE,FOLD,SCAN method works by accumulating data on LEFT and keep on changing the RIGHT variable. Main difference between them is REDUCE,FOLD is:-

Fold will always start with a seed value i.e. user defined starting value. Reduce will throw a exception if collection is empty where as fold gives back the seed value. Will always result a single value.

Scan is used for some processing order of items from left or right hand side, then we can make use of previous result in subsequent calculation. That means we can scan items. Will always result a collection.

LEFT_REDUCE method works similar to REDUCE Method.
RIGHT_REDUCE is opposite to reduceLeft one i.e. it accumulates values in RIGHT and keep on changing the left variable.
reduceLeftOption and reduceRightOption are similar to left_reduce and right_reduce only difference is they return results in OPTION object.

A part of output for below mentioned code would be :-

using scan operation over a list of numbers (using seed value 0) List(-2,-1,0,1,2)

{0,-2}=>-2 {-2,-1}=>-3 {-3,0}=>-3 {-3,1}=>-2 {-2,2}=>0 scan List(0, -2, -3, -3, -2, 0)
{0,-2}=>-2 {-2,-1}=>-3 {-3,0}=>-3 {-3,1}=>-2 {-2,2}=>0 scanLeft (a+b) List(0, -2, -3, -3, -2, 0)
{0,-2}=>-2 {-2,-1}=>-3 {-3,0}=>-3 {-3,1}=>-2 {-2,2}=>0 scanLeft (b+a) List(0, -2, -3, -3, -2, 0)
{2,0}=>2 {1,2}=>3 {0,3}=>3 {-1,3}=>2 {-2,2}=>0 scanRight (a+b) List(0, 2, 3, 3, 2, 0)
{2,0}=>2 {1,2}=>3 {0,3}=>3 {-1,3}=>2 {-2,2}=>0 scanRight (b+a) List(0, 2, 3, 3, 2, 0)

using reduce,fold operations over a list of Strings List("A","B","C","D","E")

{A,B}=>AB {AB,C}=>ABC {ABC,D}=>ABCD {ABCD,E}=>ABCDE reduce (a+b) ABCDE
{A,B}=>AB {AB,C}=>ABC {ABC,D}=>ABCD {ABCD,E}=>ABCDE reduceLeft (a+b) ABCDE
{A,B}=>BA {BA,C}=>CBA {CBA,D}=>DCBA {DCBA,E}=>EDCBA reduceLeft (b+a) EDCB
{D,E}=>DE {C,DE}=>CDE {B,CDE}=>BCDE {A,BCDE}=>ABCDE reduceRight (a+b) ABCDE
{D,E}=>ED {C,ED}=>EDC {B,EDC}=>EDCB {A,EDCB}=>EDCBA reduceRight (b+a) EDCBA

Code :

object ScanFoldReduce extends App {

    val list = List("A","B","C","D","E")
            println("reduce (a+b) "+list.reduce((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (a+b) "+list.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (b+a) "+list.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))

            println("reduceRight (a+b) "+list.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("reduceRight (b+a) "+list.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  ")
                b+a
            }))

            println("scan            "+list.scan("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))
            println("scanLeft (a+b)  "+list.scanLeft("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))
            println("scanLeft (b+a)  "+list.scanLeft("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))
            println("scanRight (a+b) "+list.scanRight("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))
            println("scanRight (b+a) "+list.scanRight("[")((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))
//Using numbers
     val list1 = List(-2,-1,0,1,2)

            println("reduce (a+b) "+list1.reduce((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (a+b) "+list1.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  ")
                a+b
            }))

            println("reduceLeft (b+a) "+list1.reduceLeft((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))

            println("      reduceRight (a+b) "+list1.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("      reduceRight (b+a) "+list1.reduceRight((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  ")
                b+a
            }))

            println("scan            "+list1.scan(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("scanLeft (a+b)  "+list1.scanLeft(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b
            }))

            println("scanLeft (b+a)  "+list1.scanLeft(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (b+a)+"  " )
                b+a
            }))

            println("scanRight (a+b)         "+list1.scanRight(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                a+b}))

            println("scanRight (b+a)         "+list1.scanRight(0)((a,b)=>{
                print("{"+a+","+b+"}=>"+ (a+b)+"  " )
                b+a}))
}

This post is barely readable. Please shorten sentences, use real keywords (e.g. reduceLeft instead of LEFT_REDUCE). Use real mathematical arrows, code tags when you are dealing with the code. Prefer input/output examples rather than explaining everything. Intermediate calculations make it hard to read. — Mikaël Mayer, Jan 11 '16 at 18:28

score 8 · Answer 3 · answered Feb 26 '20 at 11:17

For the collection x with elements x0, x1, x2, x3 and an arbitrary function f you have the following:

1. x.reduceLeft    (f) is f(f(f(x0,x1),x2),x3) - notice 3 function calls
2. x.reduceRight   (f) is f(f(f(x3,x2),x1),x0) - notice 3 function calls
3. x.foldLeft (init,f) is f(f(f(f(init,x0),x1),x2),x3) - notice 4 function calls
4. x.foldRight(init,f) is f(f(f(f(init,x3),x2),x1),x0) - notice 4 function calls
5. x.scanLeft (init,f) is f(init,x0)=g0
                          f(f(init,x0),x1) = f(g0,x1) = g1
                          f(f(f(init,x0),x1),x2) = f(g1,x2) = g2
                          f(f(f(f(init,x0),x1),x2),x3) = f(g2,x3) = g3
                          - notice 4 function calls but also 4 emitted values
                          - last element is identical with foldLeft
6. x.scanRight (init,f) is f(init,x3)=h0
                          f(f(init,x3),x2) = f(h0,x2) = h1
                          f(f(f(init,x3),x2),x1) = f(h1,x1) = h2
                          f(f(f(f(init,x3),x2),x1),x0) = f(h2,x0) = h3
                          - notice 4 function calls but also 4 emitted values
                          - last element is identical with foldRight

In conclusion

scan is like fold but also emits all intermediate values
reduce doesn't need an initial value which sometimes is a little harder to find
fold needs an initial value that is a little harder to find:
- 0 for sums
- 1 for products
- first element for min (some might suggest Integer.MAX_VALUE)
not 100% sure but it looks like there are these equivalent implementations:
- x.reduceLeft(f) === x.drop(1).foldLeft(x.head,f)
- x.foldRight(init,f) === x.reverse.foldLeft(init,f)
- x.foldLeft(init,f) === x.scanLeft(init,f).last

Reduce, fold or scan (Left/Right)?

3 Answers3

Accumulate

De-cumulate

Bottom line

In conclusion

Linked