Saturday, December 31, 2011

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

Authored by Win Myo Htet



def diff [B >: A] (that: Seq[B]): List[A]
def diff (that: Seq[A]): List[A]
[use case] Computes the multiset difference between this list and another sequence.
def diff [B >: A] (that: GenSeq[B]): List[A]
Computes the multiset difference between this list and another sequence.

def distinct : List[A]
Builds a new list from this list without any duplicate elements.

def drop (n: Int): List[A]
Selects all elements except first n ones.
def dropRight (n: Int): List[A]
Selects all elements except last n ones.
def dropWhile (p: (A) ⇒ Boolean): List[A]
Drops longest prefix of elements that satisfy a predicate.

def take (n: Int): List[A]
Selects first n elements.
def takeRight (n: Int): List[A]
Selects last n elements.
def takeWhile (p: (A) ⇒ Boolean): List[A]
Takes longest prefix of elements that satisfy a predicate.

def splitAt (n: Int): (List[A], List[A])
Splits this list into two at a given position.
diff and distinct with their description and the code snippet, which we will see below, will be good enough to understand their function. We see the take functions which compliment drop functions along with splitAt.
scala> val list=List(1,2,3,4,5,6,7,8,9,10,10,10,10)
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10)

scala> val evenlist=list collect {case x:Int if x%2==0=>x}
evenlist: List[Int] = List(2, 4, 6, 8, 10, 10, 10, 10)

scala> list diff evenlist
res0: List[Int] = List(1, 3, 5, 7, 9)

scala> val evenarray=evenlist toArray
evenarray: Array[Int] = Array(2, 4, 6, 8, 10, 10, 10, 10)

scala> list diff evenarray
res1: List[Int] = List(1, 3, 5, 7, 9)

scala> list distinct
res2: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list drop 10
res3: List[Int] = List(10, 10, 10)

scala> list take 10
res4: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list dropRight 3
res5: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list takeRight 3
res6: List[Int] = List(10, 10, 10)

scala> list dropWhile(x => x <= 9)
res7: List[Int] = List(10, 10, 10, 10)

scala> list takeWhile(x => x <= 9)
res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

scala> list splitAt 9
res9: (List[Int], List[Int]) = (List(1, 2, 3, 4, 5, 6, 7, 8, 9),List(10, 10, 10, 10))


startsWith has been brought to the start of the next functions list to compliment endsWith. sameElements also is here to be near equal. There also is exists and find.
def startsWith [B] (that: Seq[B], offset: Int): Boolean
def startsWith [B] (that: GenSeq[B], offset: Int): Boolean
Tests whether this list contains the given sequence at a given index.
def startsWith [B] (that: Seq[B]): Boolean
def startsWith [B] (that: GenSeq[B]): Boolean
Tests whether this list starts with the given sequence.

def endsWith [B] (that: Seq[B]): Boolean
def endsWith [B] (that: GenSeq[B]): Boolean
Tests whether this list ends with the given sequence.

def equals (that: Any): Boolean
The equals method for arbitrary sequences.

def sameElements (that: GenIterable[A]): Boolean
[use case] Checks if the other iterable collection contains the same elements in the same order as this list.
def sameElements [B >: A] (that: GenIterable[B]): Boolean
Checks if the other iterable collection contains the same elements in the same order as this list.
def sameElements [B >: A] (that: Iterable[B]): Boolean 

def exists (p: (A) ⇒ Boolean): Boolean
Tests whether a predicate holds for some of the elements of this list.

def find (p: (A) ⇒ Boolean): Option[A]
Finds the first element of the list satisfying a predicate, if any.

scala> val list=List(1,2,3,4,5,6,7,8,9,10)
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> val startArray1=List(1,2,3) toArray
startArray1: Array[Int] = Array(1, 2, 3)

scala> val startArray2=List(0,1,2) toArray
startArray2: Array[Int] = Array(0, 1, 2)

scala> list startsWith startArray1
res0: Boolean = true

scala> list startsWith startArray2
res1: Boolean = false

scala> val endArray1=List(8,9,10) toArray
endArray1: Array[Int] = Array(8, 9, 10)

scala> val endArray2=List(8,9,0) toArray
endArray2: Array[Int] = Array(8, 9, 0)

scala> list endsWith endArray1
res2: Boolean = true

scala> list endsWith endArray2
res3: Boolean = false

scala> val array=list toArray
array: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> val list1 = list
list1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list equals array
res4: Boolean = false

scala> list equals list1
res5: Boolean = true

scala> list sameElements array
res6: Boolean = true

scala> array(1)=1

scala> array(0)=2

scala> list equals array
res9: Boolean = false

scala> list exists (x=> x%2==0)
res10: Boolean = true

scala> list find (x=> x%2==0)
res11: Option[Int] = Some(2)

find return the first element, which satisfies the predicate, wrapped in Option. We will be seeing some interesting function next in flatMap and flatten.


Authored by Win Myo Htet

Friday, December 30, 2011

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

Authored by Win Myo Htet


def apply (n: Int): A
Selects an element by its index in the list.

def canEqual (that: Any): Boolean
Method called from equality methods, so that user-defined subclasses can refuse to be equal to other collections of the same kind.

def collect [B] (pf: PartialFunction[A, B]): List[B]
[use case] Builds a new collection by applying a partial function to all elements of this list on which the function is defined.

def collect [B, That] (pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[List[A], B, That]): That
Builds a new collection by applying a partial function to all elements of this list on which the function is defined.

def collectFirst [B] (pf: PartialFunction[A, B]): Option[B]
Finds the first element of the list for which the given partial function is defined, and applies the partial function to it.

def combinations (n: Int): Iterator[List[A]]
Iterates over combinations.

def companion : GenericCompanion[List]
The factory companion object that builds instances of class List. (or its Iterable superclass where class List is not a Seq.)
apply's description is good enough and I don't think that I have to explain it. apply can also be invoked without the function name. One can read more about it in my case class blog(companion object). canEqual is for us to override for our own class, where we can defined if we are to allow two elements to evaluate  equality. List does not override it. If we look at IterableLike (line 292), from which canEqual is inherited, it simply returns true. So, List allows to do equality for all type. collect takes Partial Functions that is constructed how we we collect the elements. collectFirst just picks the nicely-wrapped-in-Option first element from the collect. combinations can be used to create Lists that has exactly the number, which is received from  combinations's parameter, of elements from the invoking List object. companion function return a factory like class GenericCompanion from which one can create a new collection of the type like List. It is explained quite nicely at SO here.
scala> val list=List(1,2,3,4,5,6,7,8,9,10)
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list.apply(0)
res0: Int = 1

scala> list(0)
res1: Int = 1

scala> list.canEqual("anything")
res2: Boolean = true

scala> val even:PartialFunction[Int,Int]={case x:Int if x%2==0 =>x}
even: PartialFunction[Int,Int] = <function1>

scala> list collect even
res3: List[Int] = List(2, 4, 6, 8, 10)

scala> val pretty_even:PartialFunction[Int,String]={case x:Int if x%2==0 =>"-"+x+"-"}
pretty_even: PartialFunction[Int,String] = <function1>

scala> list collect pretty_even
res4: List[String] = List(-2-, -4-, -6-, -8-, -10-)

scala> list collectFirst pretty_even
res5: Option[String] = Some(-2-)

scala> val strList=list.companion("a","b","c","d")
strList: List[java.lang.String] = List(a, b, c, d)

scala> for(x <- strList.combinations(2)) println(x)
List(a, b)
List(a, c)
List(a, d)
List(b, c)
List(b, d)
List(c, d)

scala> for(x <- strList.combinations(3)) println(x)
List(a, b, c)
List(a, b, d)
List(a, c, d)
List(b, c, d)

scala> 


We have covered compose, so let's look at the other functions start with C.
def contains (elem: Any): Boolean
Tests whether this list contains a given value as an element.

def containsSlice [B] (that: Seq[B]): Boolean
def containsSlice [B] (that: GenSeq[B]): Boolean
Tests whether this list contains a given sequence as a slice.

def copyToArray (xs: Array[A], start: Int, len: Int): Unit
[use case] Copies elements of this list to an array.
def copyToArray [B >: A] (xs: Array[B], start: Int, len: Int): Unit
Copies elements of this list to an array.
def copyToArray (xs: Array[A]): Unit
[use case] Copies values of this list to an array.
def copyToArray [B >: A] (xs: Array[B]): Unit
Copies values of this list to an array.
def copyToArray (xs: Array[A], start: Int): Unit
[use case] Copies values of this list to an array.
def copyToArray [B >: A] (xs: Array[B], start: Int): Unit
Copies values of this list to an array.

def copyToBuffer [B >: A] (dest: Buffer[B]): Unit
Copies all elements of this list to a buffer.

def corresponds [B] (that: Seq[B])(p: (A, B) ⇒ Boolean): Boolean
def corresponds [B] (that: GenSeq[B])(p: (A, B) ⇒ Boolean): Boolean
Tests whether every element of this list relates to the corresponding element of another sequence by satisfying a test predicate.

def count (p: (A) ⇒ Boolean): Int
Counts the number of elements in the list which satisfy a predicate.
contains is simple. containsSlice needs the sequenced slice as we will see that evenlist return false. There are quite a lot of copyToArray functions. copyToArray is self explanatory name but still the keyword, we usually need to look for reading such functions, is [use case]. In this case, the adequate description is provided for all the functions and we won't be going over the detail but run some code snippet. copyToBuffer needs us to use ListBuffer. The reason that it is not explicitly stated and that a lot of functions description is that the document is generated from the comments from the source code where a lot of other classes also inherit the same functions. If we go look at TraversableOnce source line 219, you will see the description for copyToBuffer. If we also look at all the sub classes, which inherit from TraversableOnce, we will see the reason why the descriptions of the functions are very generic. correponds checks if the other collections have the same elements. count checks the number of element that satisfies the predicate. In our case, it is even test.
scala> val list=List(1,2,3,4,5,6,7,8,9,10)
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list.contains(1)
res0: Boolean = true

scala> list.contains("a")
res1: Boolean = false

scala> val taillist=list tail
taillist: List[Int] = List(2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> val even:PartialFunction[Int,Int]={case x:Int if x%2==0 =>x}
even: PartialFunction[Int,Int] = <function1>

scala> val evenlist=list collect even
evenlist: List[Int] = List(2, 4, 6, 8, 10)

scala> list containsSlice taillist
res2: Boolean = true

scala> list containsSlice evenlist
res3: Boolean = false

scala> val tailarray = taillist toArray
tailarray: Array[Int] = Array(2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list containsSlice tailarray
res4: Boolean = true

scala> val array=new Array[Int](10)
array: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

scala> list.copyToArray(array,3,5)

scala> array
res6: Array[Int] = Array(0, 0, 0, 1, 2, 3, 4, 5, 0, 0)

scala> list.copyToArray(array)

scala> array
res8: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> val arrayAny=new Array[Any](8)
arrayAny: Array[Any] = Array(null, null, null, null, null, null, null, null)

scala> list.copyToArray(arrayAny)

scala> arrayAny
res10: Array[Any] = Array(1, 2, 3, 4, 5, 6, 7, 8)

scala> import scala.collection.mutable.ListBuffer
import scala.collection.mutable.ListBuffer

scala> val listbuffer=new ListBuffer[Int]()
listbuffer: scala.collection.mutable.ListBuffer[Int] = ListBuffer()

scala> list.copyToBuffer(listbuffer)

scala> listbuffer
res12: scala.collection.mutable.ListBuffer[Int] = ListBuffer(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> val array=list.toArray
array: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list.corresponds(array){(le,ae)=>le==ae}
res13: Boolean = true

scala> list.count{a => a%2==0}
res14: Int = 5
After we learn C, we learn D, right?


Authored by Win Myo Htet

Thursday, December 29, 2011

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

Authored by Win Myo Htet



def andThen [C] (k: (A) ⇒ C): PartialFunction[Int, C]
Composes this partial function with a transformation function that gets applied to results of this partial function.
def lift : (Int) ⇒ Option[A]
Turns this partial function into an plain function returning an Option result.
def orElse [A1 <: Int, B1 >: A] (that: PartialFunction[A1, B1]): PartialFunction[A1, B1]
Composes this partial function with a fallback partial function which gets applied where this partial function is not defined.
We toggle the Ordering in the search section to By Inheritance. The above three functions are inherited from PartialFunction. We know that PartialFunction are a very powerful feature derived from the Functional Programming. Let's see how we can apply that to List.
scala> val list: List[Int] = List(1, 2, 3, 4)
list: List[Int] = List(1, 2, 3, 4)

scala> val lsqr=list.andThen(x=> x +" square is "+(x*x))
lsqr: PartialFunction[Int,java.lang.String] = <function1>

scala> lsqr(0)
res0: java.lang.String = 1 square is 1

scala> lsqr(3)
res1: java.lang.String = 4 square is 16

scala> val optionList=list lift
optionList: Int => Option[Int] = <function1>

scala> optionList(0)
res2: Option[Int] = Some(1)

scala> optionList(-1)
res3: Option[Int] = None

scala> optionList(3)
res4: Option[Int] = Some(4)

scala> optionList(4)
res5: Option[Int] = None

scala> val outOfRange:PartialFunction[Int,String]={case x=>x+" is out of Range."}
outOfRange: PartialFunction[Int,String] = <function1>

scala> val safelsqr= lsqr orElse outOfRange
safelsqr: PartialFunction[Int,java.lang.String] = <function1>

scala> safelsqr(0)
res6: java.lang.String = 1 square is 1

scala> safelsqr(-1)
res7: java.lang.String = -1 is out of Range.

scala>  safelsqr(3)
res8: java.lang.String = 4 square is 16

scala> safelsqr(4)
res9: java.lang.String = 4 is out of Range.

scala> val lcompose=list.compose((x:Int)=> x match{ case x if x< 0 => -x; case x => x})
lcompose: Int => Int = <function1>

scala>  lcompose(-1)
res10: Int = 2

We declare val list and then we define PartialFunction andThen, which return String composed of the value x and its square value. Since we are applying andThen to list the x value comes from list, which return the value for the index we give to lsqr. lift make use of the Option monad pattern(concept like Design Pattern but more powerful and abstract). The return function from lift will return value wrapped in Option. Why lift? One might wonder the choice of the word. The term comes from the Mathematics, which Functional Programming has based upon. The Option monad concept has lifted the unsafe value to the safe value wrapped in the Option, thus even when we feed the index out of range, the function does not blow up. If we feed the out of range index to our lsqr function created from andThen, it will blow up (which is ugly and thus omitted from the code demo.) That is where orElse came in. We define the Partial Function outOfRange and combine that with orElse to create a new function safelsqr. Now our safelsqr can handle out of range index without blowing up.

def compose [A] (g: (A) ⇒ Int): (A) ⇒ A
I have squeezed in compose function. The example code snippet is not a very good one(if you have a good example, please share with us). The reason is that compose mirrors andThen in a functional sense. There is a github blog from twitter on that. Let's go to apply.

Authored by Win Myo Htet

Wednesday, December 28, 2011

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

Authored by Win Myo Htet


def forall (p: (A) ⇒ Boolean): Boolean
def foreach (f: (A) ⇒ Unit): Unit
Basically forall takes predicates and return Boolean and foreach takes lambda and return nothing.
scala> val list=(for (i <- 1 to 25 if i%2 ==0) yield i) toList
list: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24)

scala> list forall(x => x%2==0)
res0: Boolean = true

scala> list foreach println
2
4
6
8
10
12
14
16
18
20
22
24

scala> val print_pretty=(x:Int)=>{println("***"+x+"***")}
print_pretty: Int => Unit = <function1>

scala> list foreach print_pretty
***2***
***4***
***6***
***8***
***10***
***12***
***14***
***16***
***18***
***20***
***22***
***24***

scala> 


Now that we are doing some pretty printing, shall we look into some functions that can help with printing?
def addString (b: StringBuilder): StringBuilder
def addString (b: StringBuilder, sep: String): StringBuilder
def addString (b: StringBuilder, start: String, sep: String, end: String): StringBuilder
def mkString : String
def mkString (sep: String): String
def mkString (start: String, sep: String, end: String): String

scala> list
res3: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24)

scala> list.addString(new StringBuilder(""))
res4: StringBuilder = 24681012141618202224

scala> list.addString(new StringBuilder(""),",")
res5: StringBuilder = 2,4,6,8,10,12,14,16,18,20,22,24

scala> list.addString(new StringBuilder(""),"(",",",")")
res6: StringBuilder = (2,4,6,8,10,12,14,16,18,20,22,24)

scala> list.mkString
res7: String = 24681012141618202224

scala> list.mkString(",")
res8: String = 2,4,6,8,10,12,14,16,18,20,22,24

scala> list.mkString("(",",",")")
res9: String = (2,4,6,8,10,12,14,16,18,20,22,24)
Well, that is easy. You know when I first started reading the scala code, I didn't know mkString even and have to google it.

andThen ?


Authored by Win Myo Htet

Tuesday, December 27, 2011

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

Authored by Win Myo Htet



def /:\ [A1 >: A] (z: A1)(op: (A1, A1) ⇒ A1): A1
def fold [A1 >: A] (z: A1)(op: (A1, A1) ⇒ A1): A1
def reduce [A1 >: A] (op: (A1, A1) ⇒ A1): A1
def scan [B >: A, That] (z: B)(op: (B, B) ⇒ B)(implicit cbf: CanBuildFrom[List[A], B, That]): That
def aggregate [B] (z: B)(seqop: (B, A) ⇒ B, combop: (B, B) ⇒ B): B
Since these functions are grouped together, you can say that they have some common functionality. Yes, it is their ability to do parallel processing on the List collection. fold (/:\) keeps folding, reduce:reducing and scan:scanning. Since they all are doing what they are supposed be doing(Wow, very clear!), I will be focusing on fold only and how it does parallel processing.
scala> val list=(for (i <- 1 to 25) yield i) toList
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)

scala> list.fold(0){(sum,a)=>println(a+":"+sum);sum+a}
1:0
2:1
3:3
4:6
5:10
6:15
7:21
8:28
9:36
10:45
11:55
12:66
13:78
14:91
15:105
16:120
17:136
18:153
19:171
20:190
21:210
22:231
23:253
24:276
25:300
res0: Int = 325

scala> list.par.fold(0){(sum,a)=>println(a+":"+sum);sum+a}
13:0
1:0
14:0
2:0
15:14
3:2
29:13
5:1
16:0
4:0
17:16
5:4
18:33
6:9
51:42
15:6
19:0
7:0
20:19
8:7
21:39
9:15
22:60
10:24
23:82
11:34
24:105
25:129
12:45
154:93
57:21
247:78
res1: Int = 325

We create a List[Int] of 25 Int. We operate fold on it to sum up the number. If we look at the printed log, we notice that it is similar to foldLeft. The number increase in sequence. It only seems to get the optimization of foldLeft. Then, we use the function par.
def par : ParSeq[A]
Returns a parallel implementation of this collection.
With par returning the parallel collection, fold operation becomes truly parallel processing and we can see that in the printed log. It seems very easy to do parallel processing in this example because we are using the very primitive nature Int type with the sum operator + having an associative property. Well, what if we are to deal with data type that is not like Int type, then you can use aggregate and pass on the custom function for the combop lambda, which reconcile the sub-results produced by parallel processing,while seqop lambda being what you normally feed to foldLeft or reduceLeft for processing. Though the concept is easy to grasp, the implementation will be quite a challenge depending on the complexities of the underlying data. Instead of providing my own example, I will provide you the links for further reading(watching). Markus Jais has blog about the performance analysis of the aggregate's parallel processing power. Aleksandar Prokopec talks about implementation and designing for parallel processing. As usual, the question has been asked on SO and answered.

Shall we go to foreach and forall now?


Authored by Win Myo Htet

Monday, December 26, 2011

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

Authored by Win Myo Htet



def reduceLeft [B >: A] (f: (B, A) ⇒ B): B
def reduceLeftOption [B >: A] (op: (B, A) ⇒ B): Option[B]
def reduceRight [B >: A] (op: (A, B) ⇒ B): B
def reduceRightOption [B >: A] (op: (A, B) ⇒ B): Option[B]
The different between reduceLeft and foldLeft is that reduceLeft does not have seed value to start with. Because of that reduceLeft will not yield a different collection, it just reduces the List collection to a single element. We also have self documenting function reduceLeftOption, which will return the nicely wrapped result in Option.
scala> val intlist=List(1,2,3,4,5)
intlist: List[Int] = List(1, 2, 3, 4, 5)

scala> intlist.reduceLeft{(sum,a)=>sum+a}
res0: Int = 15

scala> intlist.reduceLeft{(product,a)=>product*a}
res1: Int = 120

scala> val strlist=List("a","b","c","d","e")
strlist: List[java.lang.String] = List(a, b, c, d, e)

scala> strlist.reduceLeftOption{(res,str)=>res+str}
res2: Option[java.lang.String] = Some(abcde)


We also have scanLeft which has different structure to reduceLeft. scanLeft takes an element as a seed value and return a collection of the result along with the seed value.
def scanLeft [B, That] (z: B)(op: (B, A) ⇒ B)(implicit bf: CanBuildFrom[List[A], B, That]): That
def scanRight [B, That] (z: B)(op: (A, B) ⇒ B)(implicit bf: CanBuildFrom[List[A], B, That]): That

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

scala> intlist.scanLeft(0){(sum,a)=>sum+a}
res4: List[Int] = List(0, 1, 3, 6, 10, 15)

scala> intlist.scanLeft(1){(product,a)=>product*a}
res5: List[Int] = List(1, 1, 2, 6, 24, 120)

scala> strlist
res6: List[java.lang.String] = List(a, b, c, d, e)

scala> strlist.scanLeft(""){(sum,a)=>sum+a}
res7: List[java.lang.String] = List("", a, ab, abc, abcd, abcde)

You might notice that the resulting List has one extra element from seed value and you will also notice that the function signature has an extra implicit argument for CanBuildFrom, which is beyond the scope of this series.  You can safely ignore it since it is implicit argument, compiler will look for the appropriate object for you.

Since I am very fond of foldLeft, I am confused with these extra functions : reduceLeft and scanLeft, then I remember about "do while", while, for and "for each". Talking about foreach, List also have foreach and forall as collection-traversing mechanism. ... Yeh, yeh, I have been outright ignoring some very relevant functions all these times. Let's talk about fold, reduce and scan first before we get to foreach and forall.


Authored by Win Myo Htet

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

Thursday, December 22, 2011

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

Authored by Win Myo Htet




def ++ [B] (that: GenTraversableOnce[B]): List[B]
[use case] Concatenates this list with the elements of a traversable collection.
def ::: (prefix: List[A]): List[A]
[use case] Adds the elements of a given list in front of this list.
Though they look cryptic, Scala is not as bad as certain language found in the Ocean. (Scala can be abused to be that bad, if you so desire.) The ++ function can concatenates with a other traversable collection while ::: only operates on two lists adding the parameter list in front. A code snippet is worth a thousand words
scala>  val list1=List(1,2,3,4,5)
list1: List[Int] = List(1, 2, 3, 4, 5)

scala> val list2=List(6,7,8,9,10)
list2: List[Int] = List(6, 7, 8, 9, 10)

scala> val array1=Array(11,12,13,14,15)
array1: Array[Int] = Array(11, 12, 13, 14, 15)

scala> list2.++(list1)
res8: List[Int] = List(6, 7, 8, 9, 10, 1, 2, 3, 4, 5)

scala> list2.++(array1)
res9: List[Int] = List(6, 7, 8, 9, 10, 11, 12, 13, 14, 15)

scala> list2++array1
res10: List[Int] = List(6, 7, 8, 9, 10, 11, 12, 13, 14, 15)

scala> list2.:::(list1)
res11: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list1:::list2
res12: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list1++list2
res13: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list2.:::(array1)
<console>:10: error: type mismatch;
 found   : Array[Int]
 required: List[?]
              list2.:::(array1)
                        ^

We concatenate list2 and list1, and list2 and array1 using ++ function. As I have said the previous blog, Scala can omit dot and () for 0 or 1 parameter. Then, there is a standard call to :::. Since any function that ends with ":" binds to the right, the following ::: execution is literally, the same as the one above. We have introduced the ++ function operating on the list1 again to compare with ::: function operating on list2. They both give the same result. Prependening function ::: is always preferred over concatenating function ++ because ::: is constant execution. The last error using ::: function is a reminder that ++ has its place dealing with other traversal collection.

What if we want to prepand other traversal collection to our list, like the last error throwing expression, instead of concatenating function ++ which deals with other traversal collection?
def ++: [B] (that: TraversableOnce[B]): List[B]
[use case]Concatenates this list with the elements 
of a traversable collection. It differs from ++ in 
that the right operand determines the type of the 
resulting collection rather than the left one.
The use case description is a bit misleading with the word concatenating and comparing with ++. The justification for comparing with ++ function might be that ++: also deals with other traversal collection. It is also concatenating to the right oprand. I am just happy that the Scala library author does not overlook these usage.
scala> val array1=Array(1,2,3,4,5)
array1: Array[Int] = Array(1, 2, 3, 4, 5)

scala> val list2=List(6,7,8,9,10)
list2: List[Int] = List(6, 7, 8, 9, 10)

scala> list2.++:(array1)
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> array1++:list2
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)


There are also their overloaded function with lower bound and implicit parameter like product and sum we have seen in the previous blog.
def ++ [B >: A, That] (that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That
def ++ [B >: A, That] (that: TraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That
def ++: [B >: A, That] (that: Traversable[B])(implicit bf: CanBuildFrom[List[A], B, That]): That
def ++: [B >: A, That] (that: TraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That
def ::: [B >: A] (prefix: List[B]): List[B]
Here they are more permissible to deal with different types, thus the resulting collections are of List[Any].
scala> val listInt=List(1,2,3,4,5)
listInt: List[Int] = List(1, 2, 3, 4, 5)

scala> val listString=List("a","b","c","d")
listString: List[java.lang.String] = List(a, b, c, d)

scala> val arrayString=Array("e","f","g","h")
arrayString: Array[java.lang.String] = Array(e, f, g, h)

scala> listInt:::listString++arrayString
res0: List[Any] = List(1, 2, 3, 4, 5, a, b, c, d, e, f, g, h)

scala> arrayString++:listInt
res1: List[Any] = List(e, f, g, h, 1, 2, 3, 4, 5)

Since we have seen enough of the over loaded functions with lower bound and the implicit parameter, I won't be going over them separately for the rest of the functions.

The following functions deal with individual element prepanding/appending to the List.
def +: (elem: A): List[A]
def +: [B >: A, That] (elem: B)(implicit bf: CanBuildFrom[List[A], B, That]): That
def :+ (elem: A): List[A]
def :+ [B >: A, That] (elem: B)(implicit bf: CanBuildFrom[List[A], B, That]): That
def :: (x: A): List[A]
def :: [B >: A] (x: B): List[B]
:: and +: function prepand element to the list while :+ function append element to the list. List has two prepand function :: and +: since Scala has inherited :: function from the functional programming domain to begin with (Remember? we have seen :: as a sub class for case pattern matching in the first blog of this series.) and +: (and :+)is added later.
scala> val list=List(1,2,3,4,5)
list: List[Int] = List(1, 2, 3, 4, 5)

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

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

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

scala> "a"+:list
res4: List[Any] = List(a, 1, 2, 3, 4, 5)

scala> list:+"z"
res5: List[Any] = List(1, 2, 3, 4, 5, z)

Again prepanding :: is preferred over appending. Wow, we are almost finished with the cryptic functions. I used to be intimidated browsing the List API seeing those function. Now that we have gone through it, it is clear that they are nothing to be intimidated about. It's easy ;) Let's get into a few left over cryptic functions.


Authored by Win Myo Htet

Wednesday, December 21, 2011

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

Authored by Win Myo Htet


Before we look into Abstract Value Members of List API, I assume that you have refreshed the List API scaladoc page so that the Search Section is back to default. There are two functions productArity and productElement under Abstract Value Members. In the search box, type "product" and change Ordering to By inheritance. We see that the two stated functions along with extra two functions are inherited from Product and there are also two other separate funtions, product from different classes. Product is, sort of, Tuple's cousin. I have covered a bit of Product in my blog: Learning Scala : "case class", twitter interview question? Please read up that blog to learn more about Product. I will still cover some of its usage here.

scala> val list=List(1,2,3,4,5,6,7,8,9,10)
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list.productArity
res0: Int = 2

scala> list.productElement(0)
res1: Any = 1

scala> list.productElement(1)
res2: Any = List(2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> list.productPrefix
res3: java.lang.String = ::

productArity talks about the number of field in the class. We have 2 fields. The first being 1 and the rest being the list. Hmmm..... Then, the productPrefix, which is a toString methods of the derived class, is "::". If we look at the source code at line 390, :: class.
final case class ::[B](private var hd: B, private[scala] var tl: List[B]) extends List[B] {
 override def head : B = hd
      override def tail : List[B] = tl
      override def isEmpty: Boolean = false
    .
    .
    .
It all makes sense now. The first field is head and the rest is tail. It is a case class and you will have a sense that the very well used List's pattern matching format of head::tail is coming from here. Scala List API author has done the bulk of lifting(converting) for the developer ease of use of head::tail from ::(head, tail). That process is beyond the scope of this blog. Daniel C. Sobral has talked a bit about it on SO.

That leaves us with two functions: product and product.
def product : A
def product [B >: A] (implicit num: Numeric[B]): B
Generally, they both serve the same purpose: Multiplies up the elements of this collection. The first product is for number literal and does not take any parameter. Leaving out the parameter is a Scala idiomatic usage meaning that the function does not have side effect. The second one has restriction in a form of lower bound, [B >: A],  and takes the implicit parameter.

scala> val numList=List(1,2,3)
numList: List[Int] = List(1, 2, 3)

scala> numList.product
res0: Int = 6

scala> numList.product()
<console>:9: error: not enough arguments for method product: (implicit num: Numeric[B])B.
Unspecified value parameter num.
              numList.product()
                             ^

scala> numList.sum
res2: Int = 6

scala> numList.sum()
<console>:9: error: not enough arguments for method sum: (implicit num: Numeric[B])B.
Unspecified value parameter num.
              numList.sum()
                         ^

scala> val stringList=List("one","two","three")
stringList: List[java.lang.String] = List(one, two, three)

scala> stringList.product
<console>:9: error: could not find implicit value for parameter num: Numeric[java.lang.String]
              stringList.product
                         ^

scala> stringList.sum
<console>:9: error: could not find implicit value for parameter num: Numeric[java.lang.String]
              stringList.sum
                         ^

scala> implicit object StringNumeric extends math.Numeric[String] {
     |   override def one=""
     |   override def zero=""
     |   def plus(x: String, y: String) =(x,y)match {case ("",y) =>y
     |                                             case (x,y)   =>  x+" + "+y}
     |   def minus(x: String, y: String) = x+" - "+y
     |   def times(x: String, y: String)=(x,y)match {case ("",y) =>y
     |                                             case (x,y)   =>  x+" * "+y}
     |   def negate(x: String): String ="-"+x
     |   def fromInt(x: Int) = x.toString
     |   def toInt(x: String) = -1
     |   def toLong(x: String) = toInt(x)
     |   def toFloat(x: String) = toInt(x)
     |   def toDouble(x: String) = toInt(x)
     |   def compare(x:String,y:String) = -1
     | }
defined module StringNumeric

scala> stringList.product
res6: java.lang.String = one * two * three

scala> stringList.sum
res7: java.lang.String = one + two + three

In the code snippet, we see the usage of the first function product on List with integers. Since product function is defined without the () to begin with, the error is thrown. However, if the function is defined as product(), then adding or leaving () won't be any issue. It is also the same for function call sum. When we try to apply(abuse) product and sum on stringList, it throws error. I have created(abused) the implicit object to show you the power of the Scala implicit feature and the product(and sum) function with implicit paramter. Here we also leave out the parenthesis along with the parameter (which is fed from the List)  when we are using the function product. (Scala allows to leave out the parenthesis, dot and parameter for function with one or zero parameter.)

Well, we have finished reading the Abstract Value Members section and 6 functions from the Concrete Value Members section : product, product, productIterator, productPrefix, sum and sum. Let's go take a look at those cryptic functions : ++ :+ :: :\ /:\ ...


Authored by Win Myo Htet

Monday, December 19, 2011

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

Authored by Win Myo Htet


Everything about data manipulation in Scala is List. Of course, I over exaggerate it. Yet, you will be using List more than any other data structure. I have started out learning Scala and run into List over and over. I even theorize that if you know List API, you know Scala and the majority of its API. After all, the majority of the functions in Scala data structure API overlap. I wish, I had learned the List API early and it would have made my life easier. I would have known about the neat function like mkString when I was reading the Tic Tac Toe code. I wouldn't be doing list.slice(0,list.length-2) or list(list.length-1). It seems silly now. Yes, I have done those things because I have not read or even skimmed the List API doc while I have been using more advanced functions like foldLeft, flatMap and flatten. If you go look at my gist repo and look at the first version of gists, you will see that I am telling the truth.

I don't know about the reader. For me coming from the pretty and greenery Adroid API world, scaladoc seems daunting until I see the C++'s stuff below
template <template <class, class> class C,
          class T,
          class A,
          class T_return,
          class T_arg
              >
C<T_return, typename A::rebind<T_return>::other>
map(C<T, A> &c,T_return(*func)(T_arg) )
{
    C<T_return, typename A::rebind<T_return>::other> res;
    for ( C<T,A>::iterator it=c.begin() ; it != c.end(); it++ ){
        res.push_back(func(*it));
    }
    return res;
}

I feel blessed. Enough with the intro, let's look at the List API. Please open the link in the different browser window while you are reading the blog since I will be referring to it as I talk about the List.

Well, Scaladoc API also is pretty, it's just packed with a lot of information. At the top most section, we have the package name: scala.collection.immutable and then the class name: List. The section is followed by the class signature section stating that List extends LinearSeq and have trait's of Product,  GenericTraversableTemplate and LinearSeqOptimized. [+A] means that List is covariant. Don't worry about [+A], it just likes java Generic.

The description section explains a bit about the class with the missing info from class signature like Attributes : sealed abstract, which means all the sub classes (for List: Nil and ::) of  the sealed class (List) must be in the same source file so that, when the pattern matching is used, the compiler can warn about whether the match is exhaustive or not. We also have the link for easy access to view the source file. You will see Nil on line 368 and :: on line 390 in the same List source file. There are more info about the version numbers. The Linear Supertypes  provide information of the multiple inheritance (without diamond problem).  There is also information on Subclasses.

At first, this section seems like more redundant information about the class with in-page-search box, which is neat. So, let's call this section, "Search section", which we will be using a lot later. This section is really powerful and will make you appreciate this official Scala API. By default, the following is selected Ordering : Alphabetic, Inherited : Show all, Visibility : Public. If you select By inheritance in Ordering, you will see all the List's value members ordered in a way the members are inherited. That way, you can track which member is inherited from which class if you are interested in it. "Hide all" does not really hide all. It leaves List's own concrete value members, which makes sense. From there one can toggle the classes interested in to see the particular class' value member only. Visibility : All will show the protected members also.

Now, we are left with Instance Constructors, Type Members, Abstract Value Members, Concrete Value Members and Deprecated Value Members sections. Instance Constructors is for Constructor method. Type Member can be assumed as inner Class Member, if you are not familiar with the Scala type system yet. Abstract Value Members is the abstract methods without implementation and values without initialization. Concrete Value Members are the ones we will be using. Needless to say, we won't be using any of the Deprecated Value Members.

Let me skip the Constructor stuff and get to Type Members. Here we have the inner class like member WithFilter class. What do we do with this? How are we going to use it? We don't have to do anything with this. Then, why is it there? It is there because List have inherited it from TraversableLike. If you go to Search Section and click on Hide all,  TraversableLike and List (to hide List's stuff) under Inherited, you will still see Type Members class WithFilter along with some Concrete Value Members. If you scroll down, you will see function withFilter in the Concrete Value Members. If you go look at the  TraversableLike source code, you will see this class WithFilter(line 639) and function withFilter(line 634) there. You are like, "Ok, fine, just show me how to use it." Now we know that function withFilter is the one we are interested in for usage.

If we expand and look at the definition of withFilter, we know that it takes a predicate (a function returning a Boolean) as a parameter and return  FilterMonadic stuff. Wow, Scary! Let's read a bit more. There is a note mentioning about the difference between filter and withFilter. If it talks about the difference, it must be similar! It is said that, compare to filter, withFilter does not create a new collection when doing the filtering, thus withFilter is the optimized version of the filter! We want to use the optimized version, withFilter then. There is more info on the FilterMonadic in the return type description. It is said that FilterMonadic is some object which support map, flatMap, foreach and withFilter. Well, let's give it a try then.


scala> val list=List(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)

scala> list.withFilter(num=>num%2==0)
res0: scala.collection.generic.FilterMonadic[Int,List[Int]] = scala.collection.TraversableLike$WithFilter@431067af

scala> list.withFilter(num=>num%2==0)foreach(println)
2
4
6
8
10
12
14

scala> list.filter(num=>num%2==0)foreach(println)
2
4
6
8
10
12
14

scala> list.filter(num=>num%2==0)
res3: List[Int] = List(2, 4, 6, 8, 10, 12, 14)

scala> list.filterNot(num=>num%2==0)
res4: List[Int] = List(1, 3, 5, 7, 9, 11, 13, 15)

scala> 


Ah... the FilterMonadic thingy is not scary after all. We just need to use it with map, flatMap, foreach and withFilter only. Now we have knocked withFilter and filter off from the List API's functions list for us to learn. Oh, I have squeezed in the filterNot too if you pay attention.

How do we get to the near bottom of the List API Scaladoc? We come here through Type Memeber. Well, then let's get back to where we are next. Shall we?


Authored by Win Myo Htet

Wednesday, December 7, 2011

Learning Scala : upper bound "<:" and lower bound ">:" for laypeople

Authored by Win Myo Htet


Scala has a very rich type system. One aspect of the type system is variance, which is annotated by "+" or "-" or " " (e.g. List[+A]). From that, we also have lower bound and upper bound. We are not going to get into the detail of it. We will only try to understand it from the object oriented analogy.  Generally, lower bound, ">:", can be seen as [Parent >: Child] format and upper bound, "<:", as [Child<:Parent]. They are there for the proper usage of the Scala generic. A code snippet is worth a thousand words. So, here is the code:

abstract class Animal (animalType:String)

class HasFourLegs(animalType:String) extends Animal(animalType){
  def move=println(this+" walking on four legs")
}

class HasTwoLegs(animalType:String) extends Animal(animalType){
  def move=println(this+" walking on Two legs")
}

case class Dog(animalType:String) extends HasFourLegs(animalType)
case class Ostrich(animalType:String) extends HasTwoLegs(animalType)

  def moveOn4legs[T<:HasFourLegs](animal:T)=  animal.move
  val dog = Dog("dog")
  val ostrich=Ostrich("ostrich")
  moveOn4legs(dog)
  /*
  moveOn4legs(ostrich)
  error: inferred type arguments [this.Ostrich] do not conform to method moveOn4legs's type parameter bounds [T <: this.HasFourLegs]
  moveOn4legs(ostrich)
  ^
  */
  println
  
class AnimalMovement [+T]{
  def movement[U>:T](animal:U)=println(animal+" walking on Two legs!!!")
}

  val moveLikeTwoLegs=new AnimalMovement[HasTwoLegs]()
  moveLikeTwoLegs.movement(ostrich)
  moveLikeTwoLegs.movement(dog)

We have two kinds of animals: 4 legs and 2 legs. From there, we have a Dog and an Ostrich. We then have a method, moveOn4legs, with upper bound parameterized as moveOn4legs[T<:HasFourLegs], thus restricting the  paramter type to be the Child of HasFourLegs class. We can only use this method for Dog which extends HasFourLegs. We get compile time error when we use Ostrich which does not extends HasFourLegs.

Now we get to the AnimalMovement class with [+T], which is covariance. ([-T] is contravariance and [T] is invariant). Inside it, we have a parameterized method with lower bound,  movement[U>:T](animal:U). We create an object, moveLikeTwoLegs, out of it with the type HasTwoLegs. The movement method is then invoked with both dog and ostrich. Here is the output of this whole code snippet.

aunndroid@ubuntu:/host/linux/learning_scala/notes$ scala upper_lower_Bound.scala 
Dog(dog) walking on four legs

Ostrich(ostrich) walking on Two legs!!!
Dog(dog) walking on Two legs!!!


From, the print out of the last two lines, we see that lower bound let us use dog, an object of DOG, which is not a Child of HasTwoLegs but of HasFourLegs, which shares the same Parent Animal.

Of course, proper usage of the terms should be supertype for Parent and subtype for Child but we just want to grasp the concept of upper bound "<:" and lower bound ">:" only.


Authored by Win Myo Htet