map and filter
一些predefined list functions接受其他的function當作參數傳入，所以這些functions當然就是higher-order functions。1. map
應該是很常用的function，接受一個transformation function，回傳transformed過後的新的list：
def squareList(xs: List[Int]): List[Int] = xs match { case Nil => Nil case y :: ys => (y*y) :: squareList(ys) } def squareList2(xs: List[Int]): List[Int] = xs.map( (x:Int) => x*x )
2. filter類別 (假設input List(2,-4,5,7,1))
partition會回傳一個pair of list，分別是filter和filterNot的結果，但是只要一次list traverse。
takeWhile的語意為take something while predicate is true，所以會從頭include element，直到第一次遇到predicate evaluation為false時停止。
dropWhile剛好跟takeWhile相反，會從頭開始不include element，直到第一次遇到predicate evaluation 為false時，把剩下的全部include。
span則適合partition一樣，回傳一個pair，各是takeWhile和dropWhile的結果，但是in single traverse。
使用map and filter
pack會把一個list中的重複相連的item打包成一個sublist:例如： pack(List("a", "a", "a", "b", "c", "c", "a"))
會變成：List(List("a", "a", "a"), List("b"), List("c", "c"), List("a"))
def pack[T](xs: List[T]): List[List[T]] = xs match { case Nil => Nil case x :: xs1 => val span = xs.span( y => y==x ) span._1 :: pack(span._2) }
用了這個pack真的是輕鬆愉快，因為我們在high level運作，思考模式接近人類語言了。
有了pack，我們來試試看implement run-length encoding，就是把pack的結果化為pair!
input: encode(List("a", "a", "a", "b", "c", "c", "a"))
output: List(("a", 3), ("b", 1), ("c", 2), ("a", 1))
def encode[T](xs: List[T]): List[(T,Int)] = { pack(xs).map( (x:List[T]) => (x.head, x.length) ) }
有沒有好簡單，好輕鬆～
Binary Reduction
把一個list reduce成某個value，例如sum a list這種的operation也是很常見。1. reduceLeft，把一個 List(a,b,c, ... )變成 (.. (((a op b) op c) op d).... op z)
所以sum可以簡單地用reduceLeft表示：
List(1,2,3).reduceLeft( (x,y)=>x+y ) //6
Scala甚至可以再簡化 anonymouse function的語法:
List(1,2,3).reduceLeft( _ + _ )
相當簡潔。
2. foldLeft
reduceLeft不能使用在empty list上，會有compile/runtime error。可以用另一個更generalized reduction function：foldLeft
foldLeft是一個curried function，接受了accumulator z當作參數，所以可以operate在empty list上：
def sum(list:List[Int]) : Int = list.foldLeft(0)(_ + _)
事實上reduceLeft就是用foldLeft implement的。
def reduceLeft[T](list:List[T])(op:(T,T)=>T) : T = list match { case Nil => throw new Error case x::xs => xs.foldLeft(x)(op) }
3. foldRight
有foldLeft/reduceLeft 當然就可以有foldRight/reduceRight，這就是如何詮釋binary operation的方式不同：
List(1,2,3,4).reduceLeft(_-_) // ((1-2)-3)-4List(1,2,3,4).reduceRight(_-_) // 1-(2-(3-4))
使用Binary reduction
有了fold function，我們可以用之來implement list concatenation:
def concat[T](list1:List[T], list2:List[T]) : List[T] = { list1.foldRight(list2)(_ :: _) }
因為fold有accumulator，可以視為list 1拆解成每個element與list2做binary operation，並且accumulate。
