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))