高阶列表函数

scaleList：

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

抽象成map：

1
2
3
4
5
6
7
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)
}
def scaleList(xs: List[Double], factor: Double) =
    xs map (x => x * factor)

posElems：

1
2
3
4
def postElems(xs: List[Int]): List[Int] = xs match {
    case Nil => xs
    case y :: ys => if (y > 0) y :: posElems(ys) else posElems(ys)
}

抽象成filter：

1
2
3
4
5
6
7
8
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 else xs.filter
    }
}
def posElems(xs: List[Int]): List[Int] =
    xs filter (x => x > 0)

过滤器的变体

1
2
3
4
5
xs filterNot p    // xs filter (x => !p(x))
xs partition p    // (xs filter p, xs filterNot p)
xs takeWhile p    // 满足p的最长前缀
xs dropWhile p    // 不满足p的最长前缀
xs span p         // (xs takeWhile p, xs dropWhile p)

练习：写一个函数pack，使得

1
pack(List("a", "a", "a", "b", "c", "c", "a"))

返回

1
List(List("a", "a", "a"), List("b"), List("c", "c"), List("a"))

答案：

1
2
3
4
5
6
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)
}

列表规约(reduction)

比如

1
2
sum(List(x1, …, xn))        // = 0 + x1 + … + xn
product(List(x1, …, xn))    // = 1 * x1 * … * xn

sum函数可以这样写：

1
2
3
4
def sum(xs: List[Int]): Int = xs match {
    case Nil => 0
    case y :: ys => y + sum(ys)
}

reduceLeft

1
List(x1, …, xn) reduceLeft op = (…(x1 op x2) op …) op xn

用reduceLeft可以简化上面两个函数：

1
2
def sum(xs: List[Int]) = (0 :: xs) reduceLeft (_ + _)
def product(xs: List[Int]) = (1 :: xs) reduceLeft (_ * _)

其中每一个_从左向右都代表一个新参数。

foldLeft

foldLeft和reduceLeft类似，但它多了一个累加器，当在空列表上调用foldLeft时就会返回它。

1
(List(x1, …, xn) foldLeft z)(op) = (…(z op x1) op …) op xn

所以sum和product也可以这样定义：

1
2
def sum(xs: List[Int]) = (xs foldLeft 0) (_ + _)
def product(xs: List[Int]) = (xs foldLeft 1) (_ * _)

foldLeft和reduceLeft可以在List中这样实现：

1
2
3
4
5
6
7
8
9
10
abstract class List[T] { …
    def reduceLeft(op: (T, T) => T): T = this match {
        case Nil => throw new Error("Nil.reduceLeft")
        case x :: xs => (xs foldLeft x)(op)
    }
    def foldLeft[U](z: U)(op: (U, T) => U): U = this match {
        case Nil => z
        case x :: xs => (xs foldLeft op(z, x))(op)
    }
}

foldRight和reduceRight

1
2
List(x1, …, x{n-1}, xn) reduceRight op    // x1 op (… (x{n-1} op xn) …)
(List(x1, …, xn) foldRight acc)(op)       // x1 op (… (xn op acc) …)

实现：

1
2
3
4
5
6
7
8
9
def reduceRight(op: (T, T) => T): T = this match {
    case Nil => throw new Error("Nil.reduceRight")
    case x :: Nil => x
    case x :: xs => op(x, xs.reduceRight(op))
}
def foldRight[U](z: U)(op: (T, U) => U): U = this match {
    case Nil => z
    case x :: xs => op(x, (xs foldRight z)(op))
}

练习：如果把下面函数中的foldRight换成foldLeft会发生什么错误？

1
2
def concat[T](xs: List[T], ys: List[T]): List[T] =
    (xs foldRight ys) (_ :: _)

答案是类型错误。