# Difference between fold and foldLeft or foldRight?

ScalaFold## Scala Problem Overview

NOTE: I am on Scala 2.8—can that be a problem?

Why can't I use the `fold`

function the same way as `foldLeft`

or `foldRight`

?

In the Set scaladoc it says that:

> The result of folding may only be a supertype of this parallel collection's type parameter `T`

.

But I see no type parameter `T`

in the function signature:

```
def fold [A1 >: A] (z: A1)(op: (A1, A1) ⇒ A1): A1
```

What is the difference between the `foldLeft-Right`

and `fold`

, and how do I use the latter?

EDIT: For example how would I write a fold to add all elements in a list? With `foldLeft`

it would be:

```
val foo = List(1, 2, 3)
foo.foldLeft(0)(_ + _)
// now try fold:
foo.fold(0)(_ + _)
>:7: error: value fold is not a member of List[Int]
foo.fold(0)(_ + _)
^
```

## Scala Solutions

## Solution 1 - Scala

Short answer:

`foldRight`

associates to the right. I.e. elements will be accumulated in right-to-left order:

```
List(a,b,c).foldRight(z)(f) = f(a, f(b, f(c, z)))
```

`foldLeft`

associates to the left. I.e. an accumulator will be initialized and elements will be added to the accumulator in left-to-right order:

```
List(a,b,c).foldLeft(z)(f) = f(f(f(z, a), b), c)
```

`fold`

is *associative* in that the order in which the elements are added together is not defined. I.e. the arguments to `fold`

form a *monoid*.

## Solution 2 - Scala

`fold`

, contrary to `foldRight`

and `foldLeft`

, does not offer any guarantee about the order in which the elements of the collection will be processed. You'll probably want to use `fold`

, with its more constrained signature, with parallel collections, where the lack of guaranteed processing order helps the parallel collection implements folding in a parallel way. The reason for changing the signature is similar: with the additional constraints, it's easier to make a parallel fold.

## Solution 3 - Scala

You're right about the old version of Scala being a problem. If you look at the scaladoc page for Scala 2.8.1, you'll see no fold defined there (which is consistent with your error message). Apparently, `fold`

was introduced in Scala 2.9.

## Solution 4 - Scala

For your particular example you would code it the same way you would with foldLeft.

```
val ns = List(1, 2, 3, 4)
val s0 = ns.foldLeft (0) (_+_) //10
val s1 = ns.fold (0) (_+_) //10
assert(s0 == s1)
```

## Solution 5 - Scala

Agree with other answers. thought of giving a simple illustrative example:

```
object MyClass {
def main(args: Array[String]) {
val numbers = List(5, 4, 8, 6, 2)
val a = numbers.fold(0) { (z, i) =>
{
println("fold val1 " + z +" val2 " + i)
z + i
}
}
println(a)
val b = numbers.foldLeft(0) { (z, i) =>
println("foldleft val1 " + z +" val2 " + i)
z + i
}
println(b)
val c = numbers.foldRight(0) { (z, i) =>
println("fold right val1 " + z +" val2 " + i)
z + i
}
println(c)
}
}
```

##### Result is self explanatory :

```
fold val1 0 val2 5
fold val1 5 val2 4
fold val1 9 val2 8
fold val1 17 val2 6
fold val1 23 val2 2
25
foldleft val1 0 val2 5
foldleft val1 5 val2 4
foldleft val1 9 val2 8
foldleft val1 17 val2 6
foldleft val1 23 val2 2
25
fold right val1 2 val2 0
fold right val1 6 val2 2
fold right val1 8 val2 8
fold right val1 4 val2 16
fold right val1 5 val2 20
25
```

## Solution 6 - Scala

There is two way to solve problems, iterative and recursive. Let's understand by a simple example.let's write a function to sum till the given number.

For example if I give input as 5, I should get 15 as output, as mentioned below.

**Input**: 5

**Output**: (1+2+3+4+5) = 15

**Iterative Solution.**

iterate through 1 to 5 and sum each element.

```
def sumNumber(num: Int): Long = {
var sum=0
for(i <- 1 to num){
sum+=i
}
sum
}
```

**Recursive Solution**

break down the bigger problem into smaller problems and solve them.

```
def sumNumberRec(num:Int, sum:Int=0): Long = {
if(num == 0){
sum
}else{
val newNum = num - 1
val newSum = sum + num
sumNumberRec(newNum, newSum)
}
}
```

>> **FoldLeft**: is a iterative solution

>> **FoldRight**: is a recursive solution
I am not sure if they have memoization to improve the complexity.

And so, if you run the foldRight and FoldLeft on the small list, both will give you a result with similar performance.

However, if you will try to run a `FoldRight`

on **Long List** it might throw a **StackOverFlow** error (depends on your memory)

Check the following screenshot, where `foldLeft`

ran without error, however `foldRight`

on same list gave `OutofMemmory`

Error.

## Solution 7 - Scala

fold() does parallel processing so does not guarantee the processing order. where as foldLeft and foldRight process the items in sequentially for left to right (in case of foldLeft) or right to left (in case of foldRight)

Examples of sum the list -

```
val numList = List(1, 2, 3, 4, 5)
val r1 = numList.par.fold(0)((acc, value) => {
println("adding accumulator=" + acc + ", value=" + value + " => " + (acc + value))
acc + value
})
println("fold(): " + r1)
println("#######################")
/*
* You can see from the output that,
* fold process the elements of parallel collection in parallel
* So it is parallel not linear operation.
*
* adding accumulator=0, value=4 => 4
* adding accumulator=0, value=3 => 3
* adding accumulator=0, value=1 => 1
* adding accumulator=0, value=5 => 5
* adding accumulator=4, value=5 => 9
* adding accumulator=0, value=2 => 2
* adding accumulator=3, value=9 => 12
* adding accumulator=1, value=2 => 3
* adding accumulator=3, value=12 => 15
* fold(): 15
*/
val r2 = numList.par.foldLeft(0)((acc, value) => {
println("adding accumulator=" + acc + ", value=" + value + " => " + (acc + value))
acc + value
})
println("foldLeft(): " + r2)
println("#######################")
/*
* You can see that foldLeft
* picks elements from left to right.
* It means foldLeft does sequence operation
*
* adding accumulator=0, value=1 => 1
* adding accumulator=1, value=2 => 3
* adding accumulator=3, value=3 => 6
* adding accumulator=6, value=4 => 10
* adding accumulator=10, value=5 => 15
* foldLeft(): 15
* #######################
*/
// --> Note in foldRight second arguments is accumulated one.
val r3 = numList.par.foldRight(0)((value, acc) => {
println("adding value=" + value + ", acc=" + acc + " => " + (value + acc))
acc + value
})
println("foldRight(): " + r3)
println("#######################")
/*
* You can see that foldRight
* picks elements from right to left.
* It means foldRight does sequence operation.
*
* adding value=5, acc=0 => 5
* adding value=4, acc=5 => 9
* adding value=3, acc=9 => 12
* adding value=2, acc=12 => 14
* adding value=1, acc=14 => 15
* foldRight(): 15
* #######################
*/
```