函数式数据结构：列表与树的探索

### 函数式数据结构：列表与树的探索 #### 1. 列表操作与数据共享 在函数式编程中，列表是一种常见的数据结构。我们可以对列表进行多种操作，同时数据共享能让这些操作更高效。 - **setHead 函数**：用于将列表的第一个元素替换为不同的值。 - **drop 函数**：移除列表的前 n 个元素，若列表为空则返回空列表。其实现如下： ```scala def drop[A](as: List[A], n: Int): List[A] ``` - **dropWhile 函数**：从列表的前缀中移除满足给定谓词的元素。 ```scala def dropWhile[A](as: List[A], f: A => Boolean): List[A] ``` - **append 函数**：将一个列表的所有元素添加到另一个列表的末尾。 ```scala def append[A](a1: List[A], a2: List[A]): List[A] = a1 match case Nil => a2 case Cons(h, t) => Cons(h, append(t, a2)) ``` 这个函数只复制第一个列表的元素，直到其耗尽，运行时间和内存使用仅由第一个列表的长度决定，剩余列表直接指向第二个列表，相比数组更高效。 - **init 函数**：返回一个列表，包含原列表除最后一个元素之外的所有元素。但由于单链表的结构，该函数无法像 tail 函数那样在常数时间内实现，因为替换最后一个 Cons 的尾节点时，必须复制所有前面的 Cons 对象。 ```scala def init[A](as: List[A]): List[A] ``` #### 2. 列表递归与高阶函数的泛化 我们来看 sum 和 product 函数的实现： ```scala def sum(ints: List[Int]): Int = ints match case Nil => 0 case Cons(x, xs) => x + sum(xs) def product(ds: List[Double]): Double = ds match case Nil => 1.0 case Cons(x, xs) => x * product(xs) ``` 可以发现这两个函数非常相似，只是在列表为空时返回的值和组合结果的操作不同。我们可以将这些重复的部分泛化，得到 foldRight 函数： ```scala def foldRight[A, B](as: List[A], acc: B, f: (A, B) => B): B = as match case Nil => acc case Cons(x, xs) => f(x, foldRight(xs, acc, f)) def sumViaFoldRight(ns: List[Int]) = foldRight(ns, 0, (x,y) => x + y) def productViaFoldRight(ns: List[Double]) = foldRight(ns, 1.0, _ * _) ``` foldRight 函数会遍历到列表的末尾，然后从右向左开始折叠元素。例如： ```scala foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0, (x,y) => x + y) 1 + foldRight(Cons(2, Cons(3, Nil)), 0, (x,y) => x + y) 1 + (2 + foldRight(Cons(3, Nil), 0, (x,y) => x + y)) 1 + (2 + (3 + (foldRight(Nil, 0, (x,y) => x + y)))) 1 + (2 + (3 + (0))) 6 ``` #### 3. 更多列表操作练习 - **练习 3.7**：使用 foldRight 实现的 product 函数能否在遇到 0.0 时立即停止递归并返回 0.0？这是一个较深入的问题，后续会进一步探讨。 - **练习 3.8**：将 Nil 和 Cons 本身传递给 foldRight，如 `foldRight(List(1, 2, 3), Nil: List[Int], Cons(_, _))`，这揭示了 foldRight 与列表数据构造函数之间的关系。 - **练习 3.9**：使用 foldRight 计算列表的长度。 ```scala def length[A](as: List[A]): Int ``` - **练习 3.10**：由于 foldRight 不是尾递归，对于大列表可能会导致栈溢出。我们可以实现一个尾递归的 foldLeft 函数： ```scala def foldLeft[A, B](as: List[A], acc: B, f: (B, A) => B): B ``` - **练习 3.11**：使用 foldLeft 实现 sum、product 和计算列表长度的函数。 - **练习 3.12**：编写一个函数返回列表的反转。可以尝试使用 fold 来实现。 - **练习 3.13**：能否用 foldLeft 实现 foldRight，反之亦然？使用 foldLeft 实现 foldRight 可以使其尾递归，处理大列表时不会栈溢出。 - **练习 3.14**：使用 foldLeft 或 foldRight 实现 append 函数，而不是使用结构递归。 - **练习 3.15**：编写一个函数将列表的列表连接成一个单列表，运行时间应与所有列表的总长度成线性关系，尝试使用已定义的函数。 - **练习 3.16**：编写一个函数将列表中的每个整数加 1。 - **练习 3.17**：编写一个函数将 List[Double] 中的每个值转换为 String。 - **练习 3.18**：编写 m