函数式数据结构只能被纯函数操作，纯函数一定不能修改原始数据结构或者产生副作用。
函数式数据结构被定义为不可变的。
模式匹配有点像一个别致的switch声明，它可以侵入到表达式的数据结构内部，对这个结构进行检验和提取子表达式。
单向链表：
sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]
object List {
def apply[A](as: A*): List[A] =
if(as.isEmpty) Nil
else Cons(as.head, apply(as.tail: _*))
}
练习 3.1
求下面模式匹配的结果是什么？
分析：分析列表匹配表达式3和4，但是匹配了3之后直接求值不会再匹配4，结果为1 + 2 = 3
def sum(li: List[Int): Int = li match {
case Nil => 0
case Cons(h, t) => h + sum(t)
}
val x = List(1, 2, 3, 4, 5) match {
case Cons(x, Cons(2, Cons(4, _))) => x
case Nil => 42
case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
case Cons(h, t) => h + sum(t)
case _ => 101
}
练习 3.2
实现tail函数，删除一个List的第一个元素。
分析：利用模式匹配提取列表的第一个元数据和子列表，然后返回子列表。
def tail[A](li: List[A]): List[A] = li match {
case Nil => Nil
case Cons(h, t) => t
}
练习 3.3
实现函数setHead用一个不同的值代替列表中的第一个元素。
分析：利用模式匹配提取第一个元素和子列表，用新的值和子列表组成一个新的列表并返回。
def setHead[A](li: List[A], a: A): List[A] = li match {
case Nil => Nil
case Cons(h, t) => Cons(a, t)
}
练习 3.4
实现函数drop用于从列表中删除前n个元素。
分析：利用模式匹配提取列表头部和尾部；利用递归完成元素的删除。
def drop[A](li: List[A], n: Int): List[A] = n match {
case m if m <= 0 => li
case _ => li match {
case Nil => Nil
case Cons(h, t) => drop(t, n - 1)
}
}
练习 3.5
实现dropWhile函数，删除列表中前缀全部符合判定的元素。
分析：利用模式匹配提取列表的头部元素和尾部列表，对头部元素进行判断，满足条件剔除元素；利用递归不断提取子列表的头部元素和其子元素完成列表的遍历。
def dropWhile[A](li: List[A], f: A => Boolean): List[A] = li match {
case Nil => Nil
case Cons(h, t) =>
if (f(h)) dropWhile(t, f)
else Cons(h, dropWhile(t, f))
}
练习 3.6
实现init函数，返回一个列表，它包含原列表除最后一个元素之外的所有的元素。
分析：init函数实现困难些，递归的取列表的中的头元素，将取出的头元素组成新的列表，取到倒数第二个元素后，返回组成的新的列表。使用length函数获取列表的长度；使用append函数拼接列表以组成新的列表。
def length[A](li: List[A]): Int = {
def loop(li: List[A], acc: Int): Int = li match {
case Nil => acc
case Cons(_, t) => loop(t, acc + 1)
}
loop(li, 0)
}
def append[A](l1: List[A], l2: List[A]): List[A] = l1 match {
case Nil => l2
case Cons(h, t) => Cons(h, append(t, l2))
}
def init[A](li: List[A]): List[A] = {
def loop(n: Int, li: List[A], res: List[A]): List[A] = n match {
case m if m <= 1 => res
case _ => li match {
case Nil => Nil
case Cons(h, t) => loop(n - 1, t, append(res, List(h)))
}
}
loop(length(li), li, Nil)
}
练习 3.7
def foldRight[A, B](li: List[A], b: B)(f: (A, B) => B): B = li match {
case Nil => b
case Cons(h, t) => f(h, foldRight(t, b)(f))
}
def product(li: List[Double]): Double =
foldRight(li, 1.0)(_ * _)
- 在入参是0.0时调用foldRight实现的product是否可以立即停止递归并返回0.0？为什么不可以或者为什么可以？
分析：可以，foldRight是右折叠 - 对一个大的列表调用foldRight的时候会有什么问题发生？
分析：性能问题，使用惰性列表来避免
练习 3.8
foldRight和List之间的关系，你有什么想法？
分析：foldRight以递归的方式遍历List的每个元素，并将所有的元素进行聚合。
练习 3.9
使用foldRight实现计算List的长度。
def length1[A](li: List[A]): Int =
foldRight(li, 0){(_, b) =>
b + 1
}
练习 3.10
使用尾递归实现foldLeft
def foldLeft[A, B](li: List[A], b: B)(f: (B, A) => B): B = li match {
case Nil => b
case Cons(h, t) => foldLeft(t, f(b, h))(f)
}
练习 3.11
写下sum和product函数，和一个用foldLeft计算列表长度的函数
def sum1(li: List[Int]): Int =
foldLeft(li, 0)(_ + _)
def product1(li: List[Double]): Double =
foldLeft(li, 1.0)(_ * _)
def length2[A](li: List[A]) =
foldLeft(li, 0){(b, _) =>
b + 1
}
练习 3.12
写一个对原列表元素颠倒顺序的函数，看下是否可以用折叠实现。
def reverse[A](li: List[A]): List[A] =
foldLeft(li, Nil: List[A]){(b, a) =>
Cons(a, b)
}
练习 3.13
能否根据foldRight来实现foldLeft ？
def foldLeft1[A, B](li: List[A], b: B)(f: (B, A) => B): B =
foldRight(li, b){(a, b) =>
f(b, a)
}
练习 3.14
根据foldLeft或者foldRight实现append函数。
def append1[A](l1: List[A], l2: List[A]): List[A] =
foldLeft(l2, l1){(b, a) =>
Cons(a, b)
}
练习 3.15
写一个函数将一组列表连接成一个单个列表
def union[A](li: List[List[A]]): List[A] =
foldLeft(li, Nil: List[A]){(b, a) =>
append(b, a)
}
练习 3.16
def ++(li: List[Int]): List[Int] = li match {
case Nil => Nil
case Cons(h, t) => Cons(h + 1, ++(t))
}
练习 3.17
写一个函数，将List[Double]中的每个值转化成String
def toString(li: List[Double]): List[String] =
foldLeft(li, Nil: List[String]){(b, a) =>
Cons(a.toString, b)
}
练习 3.18
写一个泛化的map函数，对列表中每一个元素进行修改，并维持列表的结构。
def map[A, B](li: List[A])(f: A => B): List[B] = li match {
case Nil => Nil
case Cons(h, t) => Cons(f(h), map(t)(f))
}
def map1[A, B](li: List[A])(f: A => B): List[B] =
foldLeft(li, Nil: List[B]){(b, a) =>
Cons(f(a), b)
}
练习 3.19
写一个泛化的filter函数，从列表中删除所有不满足条件的元素。
def filter[A](li: List[A])(f: A => Boolean): List[A] = li match {
case Nil => Nil
case Cons(h, t) =>
if (f(h)) Cons(h, filter(t)(f))
else filter(t)(f)
}
def filter1[A](li: List[A])(f: A => Boolean): List[A] =
foldLeft(li, Nil: List[A]){(b, a) =>
if (f(a)) Cons(a, b)
else b
}
练习3.20
def flatMap[A, B](li: List[A])(f: A => List[B]): List[B] = li match {
case Nil => Nil
case Cons(h, t) => append(f(h), flatMap(t)(f))
}
def flatMap1[A, B](li: List[A])(f: A => List[B]): List[B] =
foldLeft(li, Nil: List[B]){(b, a) =>
append(b, f(a))
}
练习 3.21
用flatMap实现filter。
def filter1[A](li: List[A])(f: A => Boolean): List[A] =
flatMap(li){a =>
if (f(a)) List(a)
else Nil
}
练习 3.22
写一个函数，接受两个列表，通过对应的元素相加构造出一个新的列表。
def zip(l1: List[Int], l2: List[Int]): List[Int] = (l1, l2) match {
case (a, Nil) => a
case (Nil, b) => b
case (Cons(h1, t1), Cons(h2, t2)) => Cons(h1 + h2, zip(t1, t2))
}
练习 3.23
对刚才的函数泛化，不知针对整型和相加操作。
def zipWith[A](l1: List[A], l2: List[A])(f: (A, A) => A): List[A] = (l1, l2) match {
case (a, Nil) => a
case (Nil, b) => b
case (Cons(h1, t1), Cons(h2, t2)) => Cons(f(h1, h2), zipWith(t1, t2)(f))
}
练习 3.24
def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = ???
网友评论