函数式数据结构入门

### 函数式数据结构入门 #### 1. 函数式数据结构概述 在函数式编程中，程序不会更新变量或修改可变数据结构。那么，我们可以使用哪些数据结构呢？又如何在 Scala 中定义和操作它们呢？函数式数据结构仅使用纯函数进行操作，纯函数不会原地更改数据或产生其他副作用，因此函数式数据结构本质上是不可变的。例如，空列表（在 Scala 中写作 `List()` 或 `Nil`）就像整数 3 或 4 一样永恒且不可变。将两个列表连接（语法为 `a ++ b`）会生成一个新列表，而不会修改原始输入。 #### 2. 定义函数式数据结构 我们以单链表为例，它是最常见的函数式数据结构之一。以下是自定义 `List` 数据类型的代码： ```scala package fpinscala.datastructures enum List[+A]: case Nil case Cons(head: A, tail: List[A]) object List: def apply[A](as: A*): List[A] = if as.isEmpty then Nil else Cons(as.head, apply(as.tail*)) ``` - `enum` 关键字用于定义数据类型，它由一系列数据构造函数组成，每个构造函数由 `case` 关键字定义。 - `List` 数据类型是多态的，通过 `[+A]` 类型参数，我们可以创建不同元素类型的列表，如 `List[Int]`、`List[Double]` 等。`+` 表示类型参数 `A` 是协变的。 - `Nil` 表示空列表，`Cons` 表示非空列表，由一个头元素和一个尾列表组成。 - `List` 伴生对象中的 `apply` 方法是一个可变参数函数，用于方便地创建列表，例如 `List(1, 2, 3)`。 下面是一些使用示例： ```scala val ex1: List[Double] = List.Nil val ex2: List[Int] = List.Cons(1, List.Nil) val ex3: List[String] = List.Cons("a", List.Cons("b", List.Nil)) ``` #### 3. 模式匹配 模式匹配是函数式编程中强大的工具，常用于处理递归数据类型。以下是 `List` 伴生对象中 `sum` 和 `product` 函数的定义： ```scala object List: def sum(ints: List[Int]): Int = ints match case Nil => 0 case Cons(x, xs) => x + sum(xs) def product(doubles: List[Double]): Double = doubles match case Nil => 1.0 case Cons(0.0, _) => 0.0 case Cons(x, xs) => x * product(xs) ``` - `sum` 函数计算列表中所有元素的和，空列表的和为 0，非空列表的和是头元素加上尾列表的和。 - `product` 函数计算列表中所有元素的积，空列表的积为 1.0，以 0.0 开头的列表的积为 0.0，其他非空列表的积是头元素乘以尾列表的积。 模式匹配的工作方式类似于高级的