reduceLeft and foldLeft

• reduceLeft insert a given operator between adjacent elements of a list

List(x1, …, xn) reduceLeft op = x1 op x2 op … xn

Ex:

def sum(xs: List[Int]) = (0 :: xs) reduceLeft (_ + _);

def product(xs: List[Int]) = (1 :: xs) reduceLeft (_ * _)

• foldLeft is like reduceLeft but takes accumulator, z as an addition parameter and is returned when foldLeft is call on an empty list

(List(x1, …, xn) foldLeft z)(op) = z op x1 op x2 … xn

Ex:

def sum(xs: List[Int]) = (xs foldLeft 0) (_ + _);

def product(xs: List[Int]) = (xs foldLeft 1) (_ * _)

• Implementation of foldLeft and reduceLeft

abstract class List[T] {

 …

 def reduceLeft(op: (T, T) => T): T = this match {

  case Nil => throw new Error(“Nil.reduceLeft”)

  case x :: xs => (xs foldLeft x)(op)

 }

 foldLeft[U](z: U)(op: (U, T) => U): U = this match {

  case Nil => z

  case x :: xs => (xs foldLeft op(z, x))(op)

 }

}

foldRight and reduceRight

List(x1, …, x{n-1}, xn) reduceRight op = x1 op ( … (x{n-1} op xn) … ) 

(List(x1, …, xn) foldRight acc)(op) = x1 op ( … (xn op acc) … )

abstract class List[T] {
 
 …
 
 def reduceLeft(op: (T, T) => T): T = this match {
 
  case Nil => throw new Error(“Nil.reduceLeft”)
 
  case x :: xs => (xs foldLeft x)(op)
 
 }
 
 foldLeft[U](z: U)(op: (U, T) => U): U = this match {
 
  case Nil => z
 
  case x :: xs => (xs foldLeft op(z, x))(op)
 
 }
 
}

Ex:

def concat[T](xs: List[T], ys: List[T]): List[T] = 
 (xs foldRight ys) (_ :: _)