Scala 筆記18 - Higher-order list functions

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。