Friday, December 23, 2011

Learning Scala : Reading the exotic and essential List API scaladoc 4

Authored by Win Myo Htet


def /: [B] (z: B)(op: (B, A) ⇒ B): B
Applies a binary operator to a start value and all elements of this list, going left to right.
def foldLeft [B] (z: B)(f: (B, A) ⇒ B): B
Applies a binary operator to a start value and all elements of this list, going left to right.

def :\ [B] (z: B)(op: (A, B) ⇒ B): B
Applies a binary operator to all elements of this list and a start value, going right to left.
def foldRight [B] (z: B)(f: (A, B) ⇒ B): B
Applies a binary operator to all elements of this list and a start value, going right to left.
If you pay attention, you will notice that I have grouped the functions by having a line separating 2 functions above and 2 below. The definitions of the functions in each group are also the same. Well, if you click on both functions: /: and :\, you will see the note stating that they are the alternative syntax of foldLeft and foldRight respectively. Is it so? If you go check out the TraversableOnce source code, from which the methods are inherited, you will see that it simply is the case at line 137 and 139 respectively.

What does foldLeft and foldRight do? They traverse recursively through the List element for data manipulation. The folding concept come from the functional programming domain. Since Scala is the hybrid of FP and OO, Scala has other OO's familiar functions for data traversing. I have collected some usage of folding vs other data traversing mechanism in the industry in this blog. I have also talked about why foldLeft is preferred over foldRight here. I really recommend you to master the folding since it is a very powerful function.

If we look into the detail description, we see that it needs an initial value z of type B and return the result of type B (Our List[+A] has element of type A). It also needs anonymous function(lambda), which is similar to java's anonymous inner class. Let's look at some code snippet.
Welcome to Scala version 2.9.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_26).
Type in expressions to have them evaluated.
Type :help for more information.

scala>  val list=List(1,2,3,4,5)
list: List[Int] = List(1, 2, 3, 4, 5)

scala> list.foldLeft(0){(sum,a)=>sum+a}
res0: Int = 15

scala> list./:(0){(sum,a)=>sum+a}
res1: Int = 15

scala> (0 /: list){(sum,a)=>sum+a}
res2: Int = 15

scala>  list.foldRight(0){(a,sum)=>sum+a}
res3: Int = 15

scala> list.:\(0){(a,sum)=>sum+a}
res4: Int = 15

scala> (list :\ 0){(a,sum)=>sum+a}
res5: Int = 15

scala> list.foldLeft(0){(sum,a)=>println(a+":"+sum);sum+a}
1:0
2:1
3:3
4:6
5:10
res6: Int = 15

scala> list.foldRight(0){(a,sum)=>println(a+":"+sum);sum+a}
5:0
4:5
3:9
2:12
1:14
res7: Int = 15

scala> 

After I declare the val list, the following three lines are of foldLeft in different forms. foldRight usages come after that. I have included the println in the anonymous function(lambda) to show how foldLeft and foldRight traverse. Please pay attention to the position of sum and a in lambda. foldLeft and foldRight being differed in the direction and foldLeft being preferred, I will only use foldLeft for explanation here on ward. In the above code snippet, the initial value being type Int value 0 and the return of type Int and value 15; and the lambda doing the sum, the process does not seem that interesting. Let's look some more code snippet.
scala> list.foldLeft(""){(string,a)=>a+string}
res0: java.lang.String = 54321

scala> list.foldLeft("CreateString:"){(string,a)=>string+a}
res1: java.lang.String = CreateString:12345

scala> list.foldLeft(List[Int]()){(list,a)=>a*2::list}
res2: List[Int] = List(10, 8, 6, 4, 2)
Before we start with Int type 0, we get the result Int type 15. Using the same list, we have changed the initial value z to "","CreateString" and List[Int](), the results are of these respective types! Aren't you excited about such powerful function?

In the second blog of this blog series, we have talked about product and sum, along with the implicit object. If you look under the hood for them in TraversableOnce at line 188 and line 190, you will see that it is simply using foldLeft. You might also notice that I have overriden zero and one to "" in my implicit object.

When we work on product function, we get into sum function as well because they are similar in nature. Let's do the same here and look at similar functions.

Authored by Win Myo Htet

No comments:

Post a Comment