Map, Scan, Fold and Reduce functions

Map, Scan, Fold and Reduce

Assume we have items var

items //List(1, 2, 6, 4, 2, 1) (result)

Map function

We can map each item to another value, but we need to define how to do it. We need unary operator or single argument function

def how1(currentItem : Int) = currentItem * 2

and then apply it to each item

items.map(how1) //List(2, 4, 12, 8, 4, 2) (result)

or

items.map(how1(_)) //List(2, 4, 12, 8, 4, 2) (result)

We can replace

items.map(how1) //List(2, 4, 12, 8, 4, 2) (result)

with

val result0 = how1(items(0)) // 2
val result1 = how1(items(1)) // 4
val result2 = how1(items(2)) // 12
// ...
val resultn = how1(items(n)) // 2
val result = List(result0, ..., resultn) // List(2, 4, 12, 8, 4, 2)

Since vars result0, result1, ... resultn are independent we can evaluate them in any order.

Scan function

If we assume some processing order of items (e.g. from left (first to last) or from right (last to first)), then we can make use of previous result in subsequent calculation. That means we can scan items.

val result0 = do_something_with(???, items(1))
val result1 = do_something_with(result0, items(1))
val result2 = do_something_with(result1, items(2))
// ...
val resultn = do_something_with(resultn-1, items(n))
val result = List(result0, ..., resultn)

We must define how to do_something_with previous result and current item. We need binary operator or two argument function

def how2(prevResult : Int, currentItem : Int) 
 = prevResult * currentItem + 1

But for result0 there's no previous result, instead we provide some_input

val result0 = do_something_with(some_input, items(1))

Replace do_something_with with how2.

val input = ???
val result0 = how2(input, items(1))
val result1 = how2(result0, items(1))
val result2 = how2(result1, items(2))
// ...
val resultn = how2(resultn-1, items(n))
val result = List(input, result0, ..., resultn)

Then we can shorten to form

items.scan(input)(how2)

Time to provide input value

items.scan(0)(how2v)

Code result

List(0, 1, 3, 19, 77, 155, 156)

Output

how2(0, 1)=1
how2(1, 2)=3
how2(3, 6)=19
how2(19, 4)=77
how2(77, 2)=155
how2(155, 1)=156

Execution time: 1 Result scan returns input followed by calculated results

input :: results

Scan function examples

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.scan(0)(_+_)

Output

0
1
3
9
13
15
16

Product of items

items.scan(1)(_*_)

Output

1
1
2
12
48
96
96

As expression

items.scan("input")("f(" + _ + ", " + _ + ")")

Output

input
f(input, 1)
f(f(input, 1), 2)
f(f(f(input, 1), 2), 6)
f(f(f(f(input, 1), 2), 6), 4)
f(f(f(f(f(input, 1), 2), 6), 4), 2)
f(f(f(f(f(f(input, 1), 2), 6), 4), 2), 1)

empty list

List().scan(0)(_+_) //List(0) (result)

single element list

List(0).scan(0)(_+_) //List(0, 0) (result)

Fold function

Scan function returns input and all intermediate results. If we need only last of them then we can fold items.

items.scan(0)(how2)

Output

0
1
3
19
77
155
156

If we need only last result, we can use

items.scan(0)(how2).last //156 (result)

or shorter form fold instead of scan

items.fold(0)(how2) //156 (result)

Fold function examples

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.fold(0)(_+_) //16 (result)

Product of items

items.fold(1)(_*_) //96 (result)

As expression

items.fold("input")("f(" + _ + ", " + _ + ")")

Output

f(f(f(f(f(f(input, 1), 2), 6), 4), 2), 1)

empty list

List().fold(0)(_+_) //0 (result)

single element list

List(0).fold(0)(_+_) //0 (result)

Reduce function

We can split items

items //List(1, 2, 6, 4, 2, 1) (result)

into head

items.head //1 (result)

and tail

items.tail //List(2, 6, 4, 2, 1) (result)

then use scan function

items.tail.scan(items.head)(how2) //List(1, 3, 19, 77, 155, 156) (result)

if we need just last element...

items.tail.fold(items.head)(how2) //156 (result)

Or use shorter form

items.reduce(how2) //156 (result)

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.reduce(_+_) //16 (result)

Product of items

items.reduce(_*_) //96 (result)

As expression

items.map(_.toString).reduce("f(" + _ + ", " + _ + ")")

Output

f(f(f(f(f(1, 2), 6), 4), 2), 1)

empty list

List[Int]().reduce(_+_)

Output

Exception:
empty.reduceLeft

single element list

List[Int](0).reduce(_+_) //0 (result)

Left and Right functions

items.map is not left nor right items.scan is eqivalent to items.scanLeft

items.scan(0)(_+_) //List(0, 1, 3, 9, 13, 15, 16) (result)

items.scanLeft(0)(_+_) //List(0, 1, 3, 9, 13, 15, 16) (result)

items.fold is eqivalent to items.foldLeft

items.fold(0)(_+_) //16 (result)

items.foldLeft(0)(_+_) //16 (result)

items.reduce is eqivalent to items.reduceLeft

items.reduce(_+_) //16 (result)

items.reduceLeft(_+_) //16 (result)

scanRight

items.scanRight(0)(_+_) //List(16, 15, 13, 7, 3, 1, 0) (result)

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.scanRight(0)(_+_)

Output

16
15
13
7
3
1
0

Product of items

items.scanRight(1)(_*_)

Output

96
96
48
8
2
1
1

As expression

items.scanRight("input")("f(" + _ + ", " + _ + ")")

Output

f(1, f(2, f(6, f(4, f(2, f(1, input))))))
f(2, f(6, f(4, f(2, f(1, input)))))
f(6, f(4, f(2, f(1, input))))
f(4, f(2, f(1, input)))
f(2, f(1, input))
f(1, input)
input

empty list

List[Int]().scanRight(0)(_+_) //List(0) (result)

single element list

List(0).scanRight(0)(_+_) //List(0, 0) (result)

foldRight

items.foldRight(0)(_+_) //16 (result)

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.foldRight(0)(_+_) //16 (result)

Product of items

items.foldRight(1)(_*_) //96 (result)

As expression

items.foldRight("input")("f(" + _ + ", " + _ + ")")

Output

f(1, f(2, f(6, f(4, f(2, f(1, input))))))

empty list

List[Int]().foldRight(0)(_+_) //0 (result)

single element list

List(0).foldRight(0)(_+_) //0 (result)

reduceRight

items.reduce(_+_) //16 (result)

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.reduceRight(_+_) //16 (result)

Product of items

items.reduceRight(_*_) //96 (result)

As expression

items.map(_.toString).reduceRight("f(" + _ + ", " + _ + ")")

Output

f(1, f(2, f(6, f(4, f(2, 1)))))

empty list

List[Int]().reduceRight(_+_)

Output

Exception:
Nil.reduceRight

single element list

List[Int](0).reduceRight(_+_) //0 (result)