Scala筆記 19 - Scala collection hierarchy

Vector

scala vector是用java array implement的shallow tree，第一層超過32個element的時候，就會轉化成32*32的capacity tree，以此類推長大：

跟list不同的是，list access elements需要的時間proportional to index n in the list，而vector的話因為是一個shallow tree，access某個element的時間視它存在於哪一層而定：

另一個vector優於list的地方在於因為是用array implement，所以element都是adjacent to each other in memory，有利於現代的memory cache技術。

何時使用list或是vector? 這取決於你的access pattern。
當你要寫一直取head，然後丟入tail到recursion的時候，用list為佳，因為list取head為constant time，而vector需要log(N)。但是如果要做bulk operation例如map, filter, fold之類的，用vector會有較少的access time。

另一個list方便的地方在於可以insert element在either head or tail:

xs :+ x
x +: xs

Scala collection hierarchy

事實上list和vector都是scala collection中的一員：

Java Array/String 不在此中，但是都可以implicitly use Scala Seq functions，應該是因為Seq都用generics impelemt的關係。


Scala Range是一個順序性數字的Seq:

Sequence operations

以下是一些有用的：

其中flatmap比較特別，他把一個seqeunce的element先map到另一個sequence，然後在flatten:

"ABC" flatMap( s => List(s.toLower,s) ) //res0: String = aAbBcC

利用scala sequence，我們如何從兩個數列xs ys中找出所有的pair combination?
假設xs = List(1, 2,.....M)
ys = List(1, 2, ... , N)

這個直覺上應該用flatmap function：

def combination(M:Int, N:Int) : IndexedSeq[(Int,Int)] =
  (1 to M) flatMap (x => ( (1 to N) map(y => (x,y))))

Pattern matching function value

如果我們要implement一個vector scalar product，一開始會直覺寫成：

def scalarProduct(v1:Vector[Int], v2:Vector[Int]) =
  (v1 zip v2).map( (x,y) => x*Y )

不過這個不會compile過，因為 zip出來的sequence element type不是pair，所以要寫anonymous function (或稱為function value)的時候，不能寫成(x,y)，要用單一的變數來承接：

def scalarProduct(v1:Vector[Int], v2:Vector[Int]) =
  (v1 zip v2).map( x => x._1 * x._2 )

這會比較不直覺，所以Scala又提供了另一個sysntatic sugar：

def scalarProduct(v1:Vector[Int], v2:Vector[Int]) =
  (v1 zip v2).map{ case (x,y) => x * y }

這其實是以下的完整語法的省略：

def scalarProduct(v1:Vector[Int], v2:Vector[Int]) =
  (v1 zip v2).map( x => x match { case (a,b) => a * b })

這樣清爽多了！

實作isPrime with High-level sequence functions

按照數學定義的話，要檢測一個數n是不是質數，要看1以及n以外但是在之間的數，是否能被n整除：

def isPrime(n:Int):Boolean =
  (2 until n) forall( x => n%x != 0)