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:
|
1 2 3 |
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:
|
1 2 3 |
def sum(xs: List[Int]) = (xs foldLeft 0) (_ + _); def product(xs: List[Int]) = (xs foldLeft 1) (_ * _) |
- Implementation of foldLeft and reduceLeft
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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) … )
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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:
|
1 2 |
def concat[T](xs: List[T], ys: List[T]): List[T] = (xs foldRight ys) (_ :: _) |
Leave a Reply