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

Wednesday, November 30, 2011

Learning Scala : "case class", twitter interview question?

Authored by Win Myo Htet


I have been learning Scala actively and reading blogs, stackoverflow, and books; browsing repo, getting my hands dirty coding snippet and writing blog. I come to this subject "case class". Well, I have to admit that reading the books is boring unlike blog, yet, the books are more reliable sources of information (oh yeah? You don't know that ?) Then, there is stackoverflow, which is more reliable, does not detour and gives instant enlightened answers/insights proof-read by professionals. Still, the book does a better job of explaining (better experience on ebook with the help of Glossary and Index) Yes, I will talk about the "case class". I digress in introduction!

As I crawl the internet to learn Scala, I have downloaded some twitter's open source popular repos on github. I have browsed, skimmed and searched the repos to see how the early scala adopter is using it and defining the Scala usage pattern. Here are the downloaded repos(watchers) : flockdb (1,133), finagle(592), gizzard(966), killdeer(18) and ostrich(179). With only these opened in the eclipse, I use eclispe search tool for some of the thing I am interested in. Search keyword and number found paired.

tailrec 17
foldLeft 19
foldRight 0
for 2945 /*This includes "for" from code comment*/
while 152 /*This also includes "while" from code comment*/

Yup, at that time, I want to know how pervasive is the TCO'ed recursion and fold usages. I guess, for-comprehension rules the day. And I also skim through the codes and notice quite a lot of case block matchings. So here are some stats:

case 1658 /*This includes "just in case ..." kind of comment*/
case class 187 /*don't know if this words pair can be in comment*/

Now I hope to have your attention on the seriousness of the subject matter. It will be on the twitter interview questions! Ok, how is "case class" different from "class"? What is "case class"? "case class" is just a class. Ok... It adds extra niceties-methods : copy, equal, hashcode and (prettier) toString. The important part is that when "case class" is used, the compiler creates companion object which has both apply and unapply methods. "apply(variables)" method in Scala can be replaced with just "(variables)", thus "case class" enables constructor without keyword "new".

scala> case class MyCaseClass(name:String,isCase:Boolean)
defined class MyCaseClass

scala> val myCaseClass=MyCaseClass("myCaseClass",true)
myCaseClass: MyCaseClass = MyCaseClass(myCaseClass,true)

scala> class MyClass(name:String,isCase:Boolean)
defined class MyClass

scala> val myClass=MyClass("myClass",false)
<console>:7: error: not found: value MyClass
       val myClass=MyClass("myClass",false)
                   ^

scala> val myClass=new MyClass("myClass",false)
myClass: MyClass = MyClass@be7f971

So the interviewer asks "Why is that "case class" constructor does not require "new" keyword while the regular one does?" Then, you will answer "Cause the compiler generate "companion object" with "apply" method which can be omitted" Then, the interviewer will ask "We don't care much about "new" keyword but we just want to use regular class and want the benefit of case pattern matching. How would you do that?" Don't worry. Here is the answer for you. "case class" pattern matching is made possible by companion object's unapply extractor method. So we just need to do what "case class" does!

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> case class MyCaseClass(name:String,isCase:Boolean)
defined class MyCaseClass

scala> :paste
// Entering paste mode (ctrl-D to finish)

class MyClass(val name:String,val isCase:Boolean)
object MyClass {
  def unapply(myClass:MyClass):Option[(String,Boolean)]={
    if(myClass eq null) None
    Some((myClass.name,myClass.isCase))
  }
}

// Exiting paste mode, now interpreting.

defined class MyClass
defined module MyClass

scala> val myCaseClass=MyCaseClass("myCaseClass",true)
myCaseClass: MyCaseClass = MyCaseClass(myCaseClass,true)

scala> val myClass=new MyClass("myClass",false)
myClass: MyClass = MyClass@7bc2f501

scala> val classList=List(myClass,myCaseClass)
classList: List[ScalaObject] = List(MyClass@7bc2f501, MyCaseClass(myCaseClass,true))

scala> for( x <- classList) x match{
     |   case MyCaseClass(name,isCase)=>println(x+" "+name+" "+isCase)
     |   case MyClass(name,isCase)=>println(x+" "+name+" "+isCase)
     | }
$line2.$read$$iw$$iw$MyClass@7bc2f501 myClass false
MyCaseClass(myCaseClass,true) myCaseClass true

scala> 


In case, if you miss it, I have started the new repl session and redefine the classes. You will notice the ":paste" before MyClass definition tho. It is because we want the repl session to know that the following object with unapply method is the companion object to the class above. If you forget ":paste", don't worry, the repl will warn you. "unapply" method takes MyClass object and return the fields like the default constructor wrapped in the Option. Then we see the unapply extractor method of MyClass at work for pattern matching in the for loop near the bottom like MyCaseClass. Do you notice how pretty "case class" makes MyCaseClass's toString ? Your interviewer will then said "Ok, I am convinced that "case class" is better. What else does it do? How about if I want a new constructor?" Well, "case class" makes default constructor fields to be immutable (Scala always encourages immutable type.), so you don't have to state "val" explicitly. However, you will have to do that for "var" tho. If you want new constructor, you can create them yourself but to use it, you have to use "new" keyword because there won't be any compiler generated overloaded "apply" method for that new constructor.

Then, the interviewer is happy and you get the job at twitter. Don't forget me when twitter goes IPO and you become rich,OK?

Update
So, one interviewee came back to me and said that the interviewer said there are more to the case class. Well, if it is said so, let's take a look:

aunndroid@ubuntu:/host/linux/learning_scala/notes$ cat MyCaseClass.scala
case class MyCaseClass(name:String,isCase:Boolean){
  override def productPrefix="MyPrettyCaseClass"
}


We will use scalac -print option to peep into it. Please do it at home, it is safe. Actually I have omitted some interesting lines of codes for brevity, that's why.

aunndroid@ubuntu:/host/linux/learning_scala/notes$ scalac -print MyCaseClass.scala 
[[syntax trees at end of cleanup]]// Scala source: MyCaseClass.scala
package <empty> {
  case class MyCaseClass extends java.lang.Object with ScalaObject with Product with Serializable {
  .
  .
  .

  };
  final <synthetic> object MyCaseClass extends scala.runtime.AbstractFunction2 with ScalaObject with Serializable {
  .
  .
  .
  
  }
}


Now, we know that case class also has mixin of Serializable and Product trait. We know SerializableWhat is Product? Product enables the case class' fields to be accessed without reflection. Here is the Product scaladoc API and the following is the code snippet.

aunndroid@ubuntu:/host/linux/learning_scala/notes$ scala
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> :load MyCaseClass.scala
Loading MyCaseClass.scala...
defined class MyCaseClass

scala> val myCaseClass=MyCaseClass("aunnDroidCaseClass",true)
myCaseClass: MyCaseClass = MyPrettyCaseClass(aunnDroidCaseClass,true)

scala> myCaseClass.productArity
res3: Int = 2

scala> myCaseClass.productElement(0)
res4: Any = aunnDroidCaseClass

scala> myCaseClass.productElement(1)
res5: Any = true

scala> for(x <- myCaseClass.productIterator)println(x)
aunnDroidCaseClass
true

scala> myCaseClass.productPrefix
res7: java.lang.String = MyPrettyCaseClass


We have skipped the canEqual function. productArity provides the number of fileds in the class while productElement (n: Int) let us access those field with index. productIterator gives us the Iterator[Any] object which we use with for comprehension to print out the fields. We have overriden productPrefix, which is part of the reason why the case class has a pretty toString method.

Hope the interviewer is happy this time.

Authored by Win Myo Htet

Tuesday, November 22, 2011

Learning Scala : Recursion and TCO 2

Authored by Win Myo Htet



In the previous post, we talk about the TCO. Now, we will do some TCO'ed recursion exercise. I have picked an example  from "Programming Interviews Exposed" on P.97. Here is the problem definition : "Implement a function that prints all possible combinations of the characters  in a string. These combinations range in length from one to the length of the string. Two combinations that differ only in ordering of their characters are the same combination. In other words, "ab" and "ca" are different combinations from their input string "abc". But "ba" is the same as "ab""

We want to write a tail call recursive code with accumulator, which will give us the final result, at the end of iteration. We have to remember that we don't want any computation on the way back in these recursive calls. We will accumulate the result along the way so that we don't have to do backtrack computing. Before we go on analyzing the code, let me disclose something first. In the past, when I started coding, I tried to implement this problem by myself without reading at the authors' analysis. I failed. :) I was quite frustrated with my attempts and didn't try it again until I have started learning recursion in Scala. I try again this time. Yay! I made it. ;) With these experience, I have understood the problem and answer well. I am able to do educated grouping to form some patterns.

Yet, I still need paper and pencil! Nothing can beat paper and pencil in this age of computing when it comes to do pattern analyzing scratches for the problem. Holding pencil in the right hand like a sword, while paper in the left hand like a shield, I march on! When I am implementing the simple recursion for this problem, I look at the two logically grouped tables in the book (I won't be drawing these tables here. Buy the book!) It helps me with my thinking and visualizing of the data grouping and the flow of the data in the code too. Now, I am trying to go through the data flow where I don't have to backtrack for computing, the following data flow emerge.


input: w x y z 
=======
result: w wx wxy wxyz wxz wy wyz wz x xy xyz xz y yz z 

mydata flow
-----------
w
x
  wx 
y
  wy  xy
          wxy
z
  wz  xz  
          wxz
               yz
                   wyz  xyz  
                             wxyz  

Authored by Win Myo Htet


First, we will have 'w', which we will carry it in our accumulator to the next iteration. Then, we have 'x'. We will keep the 'w'. We want to add 'x' and also our first combination of character 'wx' too. I would like to go over this again. We start with 'w'. Carry it over. Get a new character 'x', keep the 'w', add the new 'x' and add 'w' and 'x' combination. Carry all these over in the accumulator to the next iteration. We still want to keep whatever we have before and add a new 'y' and the new characters combinations of 'y' and the previous list. Now, you know what happens to Z. If you don't, well, read this whole paragraph recursively until you get it. ;)

So basically, we have the accumulator and add a new character to the accumulator and also add a new list which has the combination of the new character with the string in the accumulator. Cool!

import scala.annotation.tailrec
 final def tailReccursionEx(str : String) : List[String] = {

  @tailrec
  def doTailRecursionEx(str : String, pos : Int, accu : List[String]) : List[String] = {
   if (pos == str.length) return accu
   else {
    val newAccu = accu ++ accu.foldLeft(List[String](str(`pos`).toString)) {
     (l, ch) => l :+ ch + str(`pos`)
    }
    doTailRecursionEx(str, pos + 1, newAccu)
   }
  }

  doTailRecursionEx(str, 0, List[String]())
 }

To make life simpler, I have started foldLeft process with the List with the new character. You can get the complete source code here .

When you look at the complete source code from the provided git repo link. You will see the comparison of imperative, recursion and TCO'ed recursion. They all look comparable. Here is another FP recursion implementation from the book (the one after the above example). When I implement the regular recursion, I am able to write it out. However, I have to make considerable effort to get it TCO'ed. The TCO'ed code is more verbose than regular recursion and at the same time also suffer from the performance impact.

Why do we want TCO again? To prevent side effect. To prevent stack over flow. To prevent our precious application from crashing. Is TCO worth the time and energy? Do you have better tip and trick ? Please let me know. I get to this haskell thread when I start looking into recursion via Ackermann.  I was thinking of implementing it TCO'ed. Having read the thread and seeing the TCO destroy the beauty of recursion and the extent needed to go to achieve the TCO, I don't want to try anymore. Yup, these are the ugly sides of FP and recursion. It is the different side of the same coin. We need to have discussion going how to tackle these issue to get FP traction for wider use. Here is one of the methods called trampoline to address some TCO issue in Scala. It is still not easy to use. It is advanced stuff. Well, it's an option.

StackOverflow discussion on this.


Authored by Win Myo Htet

Learning Scala : Recursion and TCO 1


Authored by Win Myo Htet



fib=1:1[a+b|(a,b)<-zip fib(tail fib)]
My buddy texted me the above Haskell Fibonacci code, which uses  recursion, of course. Very neat, huh? We have also seen recursion making QuickSort self documenting  and gracefully simple. I have also used recursion in my Boyer-Moore search without making a conscious effort. Yes, recursion is at home in functional programming.

Recursion can make thing simple. Yet, simple is not easy! It takes recursively using recursion to master recursion. Ok, that's not a very good joke. But you get the point that you need to keep using recursion whenever possible to learn to think in recursion if you want to be the master in the land of functional programming. In Scala, you can get away with, without using recursion, then, you are not really in functional programming land. Assume that you have decided to start using recursion buying into my much lauded hype, well, let me raise the bar a bit then. With great power comes ... I mean, "With Recursion comes this nasty bug stack overflow."

Great... Well, all hope is not lost, sort of... The stack overflow happens because the function keeps calling itself thus putting itself on the stack memory again and again until it runs out of stack memory. The remedy to this is TCO (Tail Call Optimization). In TCO, we are using a particular pattern of recursion so that the compiler can optimize the code to avoid the stack overflow. Let's try lookat some code.

scala> List(1,2,3,4,5,6).foldLeft(10)(_ + _)
res0: Int = 31

Are we still talking about recursion? Yes, we are. I have mentioned in one of the blog before that foldLeft is preferred over foldRight. The reason being is that foldLeft is TCO'ed while foldRight is not. Here is a bit detail analysis of their process.

Here is the foldLeft sequence:
((((((10 + 1) + 2) + 3) + 4) + 5) + 6)
((((((11) + 2) + 3) + 4) + 5) + 6)
(((((13) + 3) + 4) + 5) + 6)
((((16) + 4) + 5) + 6)
(((20) + 5) + 6)
((25) + 6)
(31)

Here is the foldRight sequence:
(1 + (2 + (3 + (4 + (5 + (6 + 10))))))
(1 + (2 + (3 + (4 + (5 + (16))))))
(1 + (2 + (3 + (4 + (21)))))
(1 + (2 + (3 + (25))))
(1 + (2 + (28)))
(1 + (30))
(31)

In foldLeft, you can see that the result can be computed before the next iteration, while foldRight have to traverse all the way to the end, then compute and backtrack for more computing. Alright, how do we do that for our own Fibonacci code? Following the above foldLeft example, here is our Fibonacci code

object Fibonacci{

  def main(args:Array[String]):Unit={
    println(fibonacci(6))  
  }

  import scala.annotation.tailrec
  private def fibonacci(n:Int):Int={
  
    @tailrec
    def fibonacciTCO(n:Int,accu:Int):Int={
      if(n==1) return n+accu
      fibonacciTCO(n-1,n+accu)
    }
    
    fibonacciTCO(n,10)
  }  
}

Authored by Win Myo Htet

We have to include proper import above fibonacci and @tailrec annotation above fibonacciTCO. The fibonacci function has to be declared private or final so that the method cannot be overridden to undo the TCO. You also need to have accumulator (e.g. In our case accu) so that we can carry on our result and return  the final result at the last iteration without needing to backtrack all the way back. If you look carefully at the code, you will notice that, our (near ?) result(accu) is always in the same function scope and the stack reference to the previous call is not needed any more. Now, to make sure that our method is TCO'ed, we will look into the byte code of our compilation using javap with -c and -private option on the class file of Fibonacci$.class itself.

aunndroid@ubuntu:/host/Users/aunndroid/workspace/source_code$ javap -c -private Fibonacci\$
Compiled from "fibonacci.scala"
public final class Fibonacci$ extends java.lang.Object implements scala.ScalaObject{
public static final Fibonacci$ MODULE$;

public static {};
  Code:
   0: new #9; //class Fibonacci$
   3: invokespecial #12; //Method "":()V
   6: return

public void main(java.lang.String[]);
  Code:
   0: getstatic #19; //Field scala/Predef$.MODULE$:Lscala/Predef$;
   3: aload_0
   4: bipush 6
   6: invokespecial #24; //Method fibonacci:(I)I
   9: invokestatic #30; //Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
   12: invokevirtual #34; //Method scala/Predef$.println:(Ljava/lang/Object;)V
   15: return

private int fibonacci(int);
  Code:
   0: aload_0
   1: iload_1
   2: bipush 10
   4: invokespecial #42; //Method fibonacciTCO$1:(II)I
   7: ireturn

private final int fibonacciTCO$1(int, int);
  Code:
   0: iload_1
   1: iconst_1
   2: if_icmpne 9
   5: iload_1
   6: iload_2
   7: iadd
   8: ireturn
   9: iload_1
   10: iconst_1
   11: isub
   12: iload_1
   13: iload_2
   14: iadd
   15: istore_2
   16: istore_1
   17: goto 0

private Fibonacci$();
  Code:
   0: aload_0
   1: invokespecial #48; //Method java/lang/Object."":()V
   4: aload_0
   5: putstatic #50; //Field MODULE$:LFibonacci$;
   8: return

}

aunndroid@ubuntu:/host/Users/aunndroid/workspace/source_code$ 

Don't worry too much if you don't know anything here. Well, if you know everything and if you are the master of the Scala Universe, you might even not bother to read this, right ? ;) So, we find our TCO'ed fibonacciTCO$1, at line 30. At line 47, instead of re-referencing itself, we find this 17: goto 0. When you see that goto expression, you can be rest assured that your tail call recursion has been TCO'ed. The tail call recursion get optimized by scala compiler using goto. Compare to other functional languages, Scala has some restraints. Since Scala run on JVM and JVM does not support TCO(yet), Scala requires that tail call recursion must be self recursive tail call (e.g. fibonacciTCO must call fibonacciTCO).

Yup, that's quite a bit of info. I don't conceive these knowledge auto-magically. I am not the creator of Scala. I have read the blogs and books. So, I also recommend you to keep on reading about recursion and encourage you to blog about it too. Reading the same info from different narration will help you grasp the concept better. Here are the two I have read: Graham's blog and Nick's blog. They are also explaining the same info in their own way. As usual, we will be getting into some code in the next blog in this series.



Authored by Win Myo Htet

Friday, November 18, 2011

Learning Scala : Boyer–Moore search 3

Authored by Win Myo Htet


We have both the first table and second. Now we just need to create a startSearch method, which will take the two tables and two Strings : searchBody and searchString. We will return a List[Int],  which will have positions of the match strings, thus the size will be the number of the matches.

def startSearch(searchBody : String, searchString : String,
  pos : Int, table1 : Map[Int, Int],
  table2 : Map[Char, Int]) : List[Int] = {
  
  def search(pos : Int, inc : Int = 0) : List[Int] = {
   if (pos >= searchBody.length - 1) return List[Int]()
   val jump = matchChar(pos + searchString.length - 1, inc)
   if (jump > 0) return search(pos + jump, 0)
   if (jump == 0) return search(pos, inc + 1)
   if (jump == -1) 
     return pos :: search(pos + searchString.length, 0)
   List[Int]()
  }

  def matchChar(pos : Int, inc : Int) : Int = {
   if (!searchBody.isDefinedAt(pos - inc)) return -2
   
   if (!table2.isDefinedAt(searchBody(pos))) 
     return searchString.length
   if (searchBody(pos - inc) 
       == searchString(searchString.length - 1 - inc)) {
    if (searchString.length - 1 - (inc + 1) == -1) return -1
    return 0
   }
   val result1 = table1.get(inc).get
   
   if (!table2.isDefinedAt(searchBody(pos - inc))) 
     return result1   
   val result2 = table2.get(searchBody(pos - inc)).get
   if (result2 > result1) return result2
   result1
  }
  
  search(pos)
 }


We have two nested functions inside our function. We check the validity of our search continuity by searchBody string length. We invoke matchChar function to get the jump value. -1 means we found a string match. 0 means the character match. All the positive value means, we will jump that much position. The sort of default return is empty list. Inside matchChar, we will do the validity check and return -2, which will fall through our default empty list return in search function. We return the length of the searchString if the last character is not a valid character according to table2. Then, we do the individual character matching. If it is matched, we will check to see it is the last character to match. If it is the last character matched, we found a match String and return -1. If it is not the last character matched, we will return 0. If the characters are not matched, the two tables are referred for the jump value and larger value is return. In case of the character not being in the table2, we cannot jump the whole searchString's length since there still is a possible match inside the range.

Below is some output. I admit that it is not well tested. You can get the complete source code here.

Look at the two Map values of ANPANMAN
aunndroid@ubuntu:/host/Users/aunndroid/workspace/source_code$ scala boyer_moore.scala 

Usage: boyer_more string_body search_string
e.g. : boyer_more "HERE IS A SIMPLE EXAMPLE" "ANPANMAN"
Map(A -> 1, M -> 2, N -> 3, P -> 5)
Map(0 -> 1, 5 -> 6, 1 -> 8, 6 -> 6, 2 -> 3, 7 -> 6, 3 -> 6, 4 -> 6)
ANPANMAN
HERE IS A SIMPLE EXAMPLE
       -
        ANPANMAN
HERE IS A SIMPLE EXAMPLE
               -
                ANPANMAN
HERE IS A SIMPLE EXAMPLE
                       -
Match found : 0 Pos : 

Here is the search replica of step by step B-M search demo from the official site <?>

aunndroid@ubuntu:/host/Users/aunndroid/workspace/source_code$ scala boyer_moore.scala "HERE IS A SIMPLE EXAMPLE" "EXAMPLE"
Map(E -> 6, X -> 5, A -> 4, M -> 3, L -> 1, P -> 2)
Map(0 -> 1, 5 -> 6, 1 -> 7, 6 -> 6, 2 -> 6, 3 -> 6, 4 -> 6)
EXAMPLE
HERE IS A SIMPLE EXAMPLE
      -
       EXAMPLE
HERE IS A SIMPLE EXAMPLE
             -
         EXAMPLE
HERE IS A SIMPLE EXAMPLE
               -
         EXAMPLE
HERE IS A SIMPLE EXAMPLE
              -
         EXAMPLE
HERE IS A SIMPLE EXAMPLE
             -
         EXAMPLE
HERE IS A SIMPLE EXAMPLE
            -
         EXAMPLE
HERE IS A SIMPLE EXAMPLE
           -
               EXAMPLE
HERE IS A SIMPLE EXAMPLE
                     -
                 EXAMPLE
HERE IS A SIMPLE EXAMPLE
                       -
                 EXAMPLE
HERE IS A SIMPLE EXAMPLE
                      -
                 EXAMPLE
HERE IS A SIMPLE EXAMPLE
                     -
                 EXAMPLE
HERE IS A SIMPLE EXAMPLE
                    -
                 EXAMPLE
HERE IS A SIMPLE EXAMPLE
                   -
                 EXAMPLE
HERE IS A SIMPLE EXAMPLE
                  -
                 EXAMPLE
HERE IS A SIMPLE EXAMPLE
                 -
Match found : 1 Pos : 17
aunndroid@ubuntu:/host/Users/aunndroid/workspace/source_code$

That's it, folk!


Authored by Win Myo Htet