可折叠数据结构与幺半群的组合应用

### 可折叠数据结构与幺半群的组合应用 #### 1. 幺半群的定义与实例 幺半群是一种纯粹的代数结构，由一个满足结合律的二元运算和该运算的单位元组成。在编程中，我们可以将幺半群建模为具有 `combine` 和 `empty` 操作的特质。以下是一些常见类型的幺半群实例： ```scala val intMultiplication: Monoid[Int] = new: def combine(a1: Int, a2: Int) = a1 * a2 val empty = 1 given string: Monoid[String] with def combine(a1: String, a2: String) = a1 + a2 val empty = "" val booleanOr: Monoid[Boolean] = new: def combine(x: Boolean, y: Boolean) = x || y val empty = false val booleanAnd: Monoid[Boolean] = new: def combine(x: Boolean, y: Boolean) = x && y val empty = true ``` 当调用使用上下文参数的函数时，我们可以通过 `using` 关键字提供自己的实例，而不是使用给定的实例。例如： ```scala val allPositive = foldMap(List(1, 2, 3))(_ > 0)(using Monoid.booleanAnd) val existsNegative = foldMap(List(1, 2, 3))(_ < 0)(using Monoid.booleanOr) ``` #### 2. 可折叠数据结构 在处理数据时，我们常常不关心数据结构的具体形状、是否为惰性结构或是否提供高效的随机访问。为了捕捉这些数据结构的共性，我们可以定义一个类型类 `Foldable`： ```scala trait Foldable[F[_]]: extension [A](as: F[A]) def foldRight[B](acc: B)(f: (A, B) => B): B def foldLeft[B](acc: B)(f: (B, A) => B): B def foldMap[B](f: A => B)(using m: Monoid[B]): B def combineAll(using m: Monoid[A]): A = as.foldLeft(m.empty)(m.combine) ``` 这里的 `F[_]` 是一个类型构造器，类似于高阶函数，`Foldable` 是一个高阶类型构造器或高阶类型。 ##### 练习实现 - **练习 10.12**：实现 `Foldable[List]`、`Foldable[IndexedSeq]` 和 `Foldable[LazyList]`。 ```scala given Foldable[List] with extension [A](as: List[A]) override def foldRight[B](acc: B)(f: (A, B) => B) = as.foldRight(acc)(f) override def foldLeft[B](acc: B)(f: (B, A) => B) = as.foldLeft(acc)(f) given Foldable[IndexedSeq] with extension [A](as: IndexedSeq[A]) override def foldRight[B](acc: B)(f: (A, B) => B) = as.foldRight(acc)(f) override def foldLeft[B](acc: B)(f: (B, A) => B) = as.foldLeft(acc)(f) override def foldMap[B](f: A => B)(using mb: Monoid[B]): B = Monoid.foldMapV(as, mb)(f) given Foldable[LazyList] with extension [A](as: LazyList[A]) override def foldRight[B](acc: B)(f: (A, B) => B) = as.foldRight(acc)(f) override def foldLeft[B](acc: B)(f: (B, A) => B) = as.foldLeft(acc)(f) ``` - **练习 10.13**：实现 `Foldable[Tree]`。 ```scala given Foldable[Tree] with import Tree.{Leaf, Branch} extension [A](as: Tree[A]) override def foldRight[B](acc: B)(f: (A, B) => B) = as match case Leaf(a) => f(a, acc) case Branch(l, r) => l.foldRight(r.foldRight(acc)(f))(f) override def foldLeft[B](acc: B)(f: (B, A) => B) = as match case Leaf(a) => f(acc, a) case Branch(l, r) => r.foldLeft(l.foldLeft(acc)(f))(f) override def foldMap[B](f: A => B)(using mb: Monoid[B]): B = as match case Leaf(a) => f(a) case Branch(l, r) => mb.combine(l.foldMap(f), r.foldMap(f)) ``` - **练习 10.14**：实现 `Foldable[Option]`。 ```scala given Foldable[Option] with extension [A](as: Option[A]) override def foldRight[B](acc: B)(f: (A, B) => B) = as match case None => acc case Some(a) => f(a, acc) override def foldLeft[B](acc: B)(f: (B, A) => B) = as match case None => acc case Some(a) => f(acc, a) override def foldMap[B](f: A => B)(using mb: Monoid[B]): B = as match case None => mb.empty case Some(a) => f(a) ``` - **练习 10.15**：为 `Foldable` 特征添加 `toList` 扩展方法。 ```scala trait Foldable[F[_]]: extension [A](as: F[A]) def toList: List[A] = as.foldRight(List.empty[A])(_ :: _) g ```