## Scala Notes: Fold

Fold is a general purpose operation on list (e.g., `List[A]`), which involves iterating (over each element) and applying a binary function–

f: A -> B -> B

to reduce the list to a single result, i.e., `B`. The initial value of `B` is provided as an argument and then at each stage of the operation, `f` is applied to the successive elements of `List[A]`, with `B` that has been accumulated so far.

In this post, we implement and explain key characteristics of `foldRight` and `foldLeft`.

## Fold Left

Following diagram illustrates generic `foldLeft`, where the initial value is given by `a`. As the name suggests, the iteration starts from the left. Evidently, the signature of the function follows–

foldLeft: A List -> B -> (A -> B -> B) -> B

Tail-recursive implementation of `foldLeft` is outlined next.

```  def foldLeft[A, B](l: List[A], z: B)(f: (B, A) => B): B =
l match {
case Nil => z // contains result
case x :: xs => foldLeft(xs, f(z, x))(f)
}

```

The above `length` can be implemented using `foldLeft` as follows:

```def lengthTR[A](l: List[A]) = foldLeft(l, 0)((acc, _) => acc + 1)
```

## Fold Right

`foldRight` is quite similar to `foldLeft`, yet there are some subtle differences. To begin with, the unwinding phase starts from the end of the list. In effect, iteration direction is from the right to left. As a result, `foldRight` is not a tail-recursive function. Following illustrates `foldRight` function — We can implement `foldRight` as follows.

```def foldRight[A,B](l:List[A], z:B)(f: (A,B) => B): B =
l match{
case Nil => z
case x::xs => f(x, foldRight(xs, z)(f))
}
```

To show how it works, let’s apply it in implementing `length` of a `List`.

```def length[A](l: List[A]) = foldRight(l, 0)((x,y)=> y+1)
```

As noted earlier, we can see that the unwinding phase start after reaching at the end of the `List` and thus, `foldRight` is not a tail-recursive function.

During the execution of `foldRight`, `Nil` gets replaced by the value of `z`, the second argument of `foldRight`, whereas every `Con` gets replaced by an invocation of `f`.

## References

The images used to explain `foldLeft` and `foldRight` are taken from “Elements of Functional Programming” by Chris Reade.

## Scala Notes: Functions

Functions in Scala can be defined simply as follows:

```def fnname (args)={
// function body
}

def double(i:Int) = i*2
```

Implementing `loop` can be done in following manner.

```def whileLoop{
var i = 1
while (i<=3) {
println (i)
}
}
```

Function that takes other functions as a parameter, or that returns a function as the result, are called higher order function. One thing that is particular to functional programming is that it treats function as value. This provides a flexible way to compose programs.

```def totalResultOverRange(number:Int, codeBlock: Int => Int):Int = {
var result = 0;

for ( i <- 1 to number) {
result = result + codeBlock(i)
}

return result;
}                                               //> totalResultOverRange: (number: Int, codeBlock: Int => Int)Int

totalResultOverRange(11, i => i)                //> res0: Int = 66

totalResultOverRange(11, i =>if (i%2 == 0) 0 else 1)
//> res1: Int = 6

totalResultOverRange(11, i => 1)                //> res2: Int = 11
```