-
-
Save Krasnyanskiy/eb37e78530dd905b3925 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Reduction: We can sum all the elements | |
// with the usual recursive schema | |
def sum(xs: List[Int]): Int = xs match { | |
case Nil => 0 | |
case y :: ys => y + sum(ys) | |
} | |
// But this can be abstracted out using 'reduceLeft' | |
// That will perform these operations LINKING to the left | |
def sum(xs: List[Int]) = (0 :: xs) reduceLeft ((x, y) = x + y) | |
def product(xs: List[Int]) = (1 :: xs) reduceLeft ((x, y) = x * y) | |
// A shorter way | |
def sum(xs: List[Int]) = (0 :: xs) reduceLeft (_ + _) | |
def product(xs: List[Int]) = (1 :: xs) reduceLeft (_ * _) | |
// A more general function: foldLeft | |
def sum(xs: List[Int]) = (xs foldLeft 0) (_ + _) | |
def product(xs: List[Int]) = (xs foldLeft 1) (_ * _) | |
// Other ways to write that | |
def sum(xs: List[Int]) = xs.foldLeft(0)(_ + _) | |
def product(xs: List[Int]) = xs.foldLeft(1)(_ * _) | |
// scala operator infix (if operator ends in : reverse order) | |
// Note: /: is alternate syntax for foldLeft; z /: xs is the same as xs foldLeft z. | |
def sum(xs: List[Int]) = (0 /: xs) (_ + _) | |
def product(xs: List[Int]) = (0 /: xs) (_ * _) | |
// How would we implement reduceLeft and foldLeft in List? | |
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) | |
} | |
def foldLeft[U](z: U)(op: (U, T) => U): U = this match { | |
case Nil => z | |
case x :: xs => (xs foldLeft op(z, x))(op) | |
} | |
} | |
// There's also reduceRight and foldRight. | |
// They produce the same results but sometimes only one | |
// of them is appropiate | |
def concat[T](xs: List[T], ys: List[T]): List[T] = | |
(xs foldRight ys) (_ :: _) | |
// This is what happens with foldRight: | |
// :: | |
// x1 :: | |
// x2 :: | |
// xn :: | |
// y1 :: | |
// y2 :: | |
// yn Nil | |
// BUT: foldLeft would not work here because | |
// :: is not applicable to elements, only to lists | |
// (try rebuilding the tree above for foldLeft) | |
// Or visualising it with operator infix | |
def concat[T](xs: List[T], ys: List[T]): List[T] = | |
(ys :\ xs) (_ :: _) | |
// ** foldRight and foldLeft *** | |
// Northern wind comes from the North (Richard Bird) | |
List(a, b, c).foldRight(e)(f) // equals... | |
f(a, f(b, f(c, e))) // <---- | |
List(a, b, c).foldLeft(e)(f) // equals... | |
f(f(f(e, a), b), c) // ----> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment