Coursera Scala 5-4：List的高階函數

Coursera Scala 5-4：List的高階函數

Recurring Patterns for Computations on Lists

重複出現的Lists計算模式

lists的很多函數有相似的結構，重複出現的模式有：

• 用某個方法轉換每個元素
• 用某個條件提取元素
• 用某種方法鏈接元素

函數式編程語言，讓程序員能寫出更通用的計算模式，通過使用高階函數。

Applying a Function to Elements of a List

將一個list的所有元素，進行轉換。例子：返回一個新的集合，每個元素乘以factor

def scaleList(xs: List[Double],factor:Double):List[Double] = xs match {
    case Nil => xs
    case y::ys => y*factor :: scaleList(ys,factor)
}

高階函數:Map

上麵的模式，可以通過map函數來進行通用性封裝：

abstract class List[T] {...
    def map[U](f: T=>U): List[U] = this match {
        case Nil => this
        case x::xs => f(x) :: xs.map(f)
    }

(實際上，map的定義更複雜，不僅僅隻支持lists)
使用map,scaleList很容易被實現：

def scaleList(xs:List[Double],factor: Double) =
    xs map (x => x * factor)

高階函數:Filtering

這是另外一個常用的操作。從集合中篩選滿足條件的元素

abstract class List[T] {
    ...
    def filter(p: T => Boolean): List[T] = this match {
        case Nil => this
        case x::xs => if(p(x)) x::xs.filter(p) else xs.filter(p)
    }
}

filter還有其他變種：
xs fileterNot p 相當於xs fileter(x=>!p(x))
xs partition p 分區:List(1,0,1,0) partition (>0) // ((1,1),(0,0))
xs takeWhile p 用法：1 to 10 takeWhile (<5) // (1,2,3,4)
xs dropWhile p 用法：1 to 10 dropWhile (<5) // (5,6,7,8,9,10)
xs span p 用法：1 to 10 span (<5) // ((1,2,3,4),(5,6,7,8)

Excercise

編寫函數pack滿足：
List（"a","a","a","b","b","c","c","a")
=>
List( List("a","a","a"), List("b","b"), List("c","c"),List("a") )

def pack[T](xs: List[T]): List[List[T]] = xs match {
    case Nil => Nil
    case x :: xs1 =>
        val (first,rest) = xs span (y=>y==x)
        first :: pack(rest)  
}

Excercise2

編寫函數encode滿足：
List（"a","a","a","b","b","c","c","a")
=>
List( List("a",3), List("b",2), List("c",2),List("a",1) )

def encode[T](xs: List[T]): List[(T,Int)] =
 pack(xs) map (ys => (ys.head, ys.length))