4. 函数式编程范式

在这一章中，我们学习函数式编程范例，示例和项目主要是用Scala编写的。

4.1. 使用内置类型和行为解决问题

与其他语言一样，Scala提供了大量的预定义类型和(泛型)类型构造函数以及一组丰富的行为。其中许多类型，特别是集合类型和某些实用程序类型， 代数数据类型 ，下面将更详细地讨论：

通过像使用脚本语言(如Python或Ruby)那样使用Scala，人们甚至无需定义自定义代数数据类型就可以解决许多问题，可能除了偶尔出现的元组之外。脚本式Scala中的主要构建块是我们刚才提到的集合和实用程序类型，以及

重要方法 map ， take / drop ， filter / withFilter ， find ， flatMap ， sum ， foldLeft / foldRight ， scanLeft ， zip ， groupBy ， collect
for 理解

待处理

详细说明 for 理解和理解 flatMap

4.1.1. 示例

使用可变状态循环有限集合或迭代器中的所有项：

final Iterator<String> incoming = ...;
var sum = 0;
var count = 0;
incoming.forEachRemaining(s -> {
  sum += s.length();
  count += 1;
});
final var result = (float) sum / count;

这段代码计算的是什么？

不可变的等价物使用 foldLeft ：：

val (sum, count) = incoming.foldLeft {
  (0, 0)
} { case ((sum, count), next) =>
  (sum + next.length, count + 1)
}
val result = sum.toFloat / count

注意，您不能“取消融合”这个等价的循环，因为迭代器是有状态的，并且您只能遍历它一次。另一方面，如果 incoming 是集合(始终是有限的)而不是迭代器(可能是无界的)，则可以使用 map 和 sum ，一个专门的文件夹，对于更简洁的等价物：：

val sum = incoming.map(s => s.length).sum
val count = incoming.size
val result = sum.toFloat / count

这相当于两个连续循环，其中一个循环用于 map 还有一个是为了 sum 。

无界循环，直到满足条件：：

final var input = new Scanner(System.in);
System.out.print("enter next expression: ");
while (input.hasNextLine()) {
  final var line = input.nextLine();
  processExpr(line)
  System.out.print("enter next expression: ");
}

不可变的等价物使用 continually ：：

Iterator continually {
  print("enter next expression: ")
  StdIn.readLine()
} takeWhile { line =>
  line != null
} foreach { line =>
  processExpr(line)
}

4.1.2. 其他对集合的重要操作

当迭代体生成 副作用 例如输出，我们可以使用 foreach 而不是 continually 。
如果我们想要计算一个 结果值 ，我们可以使用 foldLeft 而不是 foreach 。
如果我们想要计算一个 结果值序列 ，每个原始项目一个，我们可以使用 scanLeft (有示例可供选择 here )。
如果我们想要将一个 结果值的集合 通过对每个项单独应用相同的函数，同时保留集合的框架结构，我们可以使用 map 。
如果我们想要做同样的事情 map 但是不需要引入额外的结构嵌套级别(尽管该函数会这样做)，我们可以使用 flatMap ，它将内部结构展平到外部；例如，在关于控制台应用程序的一节中可以看到将行拆分为单词。 flatMap 相当于 map 紧随其后的是 flatten 。

下面的示例说明了 map 和 flatMap 从命令的角度看：

// map - the result is a nested collection

scala> Seq("hello world what up", "hola mundo", "hallo welt")
res0: Seq[String] = List(hello world what up, hola mundo, hallo welt)

scala> res0.map(s => s.split("\\s+"))
val res1: Seq[Array[String]] = List(Array(hello, world, what, up), Array(hola, mundo), Array(hallo, welt))

scala> val resultNested = scala.collection.mutable.ArrayBuffer.empty[Array[String]]
resultNested: scala.collection.mutable.ArrayBuffer[Array[String]] = ArrayBuffer()

scala> res0.foreach { line =>
     |   val words = line.split("\\s+")
     |   resultNested += words
     | }

scala> resultNested
res2: scala.collection.mutable.ArrayBuffer[Array[String]] = ArrayBuffer(Array(hello, world, what, up), Array(hola, mundo), Array(hallo, welt))

// flatMap - the result is a flat collection - this requires nested loops!

scala> res0.flatMap(s => s.split("\\s+"))
val res3: Seq[String] = List(hello, world, what, up, hola, mundo, hallo, welt)

scala> val resultFlat = scala.collection.mutable.ArrayBuffer.empty[String]
resultFlat: scala.collection.mutable.ArrayBuffer[String] = ArrayBuffer()

scala> res0.foreach { line =>
     |   val words = line.split("\\s+")
     |   words.foreach { word =>
     |     resultFlat += word
     |   }
     | }

scala> resultFlat
res4: scala.collection.mutable.ArrayBuffer[String] = ArrayBuffer(hello, world, what, up, hola, mundo, hallo, welt)

还要注意，所有这些都是方法，但由于Scala的语法，它们看起来像控制结构，这允许您在选择方法的某些情况下省略圆点，并使用大括号而不是圆括号来分隔参数列表。

4.1.3. 处理连续的故障

尝试一个接一个的选择，直到其中一个成功，或者一个都没有了，我们不得不放弃。嵌套的 try -``catch``语句通常用于实现此目的：：

AuthorizeRequestStrategy authorizeRequest = null;
try {
  logger.debug("looking for access token");
  ...
  logger.debug("found access token");
  authorizeRequest = (request) -> request.addHttpHeaders(authHeader);
} catch (final FileNotFoundException ex) {
  try {
    logger.debug("looking for API key in environment");
    final var apiKey = sys.env("API_KEY");
    logger.debug("found API key");
    authorizeRequest = (request) -> request.addQueryStringParameter("key", apiKey);
  } catch (final NoSuchElementException ex) {
    logger.debug("no authorization information found, exiting");
    System.exit(401);
  }
}

使用连续的不可变的等价物 Try 平链的块，使用 orElse ：：

val authorizeRequest = Try {
   logger.debug("looking for access token in property file")
   ...
   logger.debug("found access token")
   val authHeader = KeyAuthorization -> s"Bearer $accessToken"
   (request: WSRequest) => request.addHttpHeaders(authHeader)
 } orElse Try {
   logger.debug("looking for API key in environment")
   val apiKey = sys.env("API_KEY")
   logger.debug("found API key")
   (request: WSRequest) => request.addQueryStringParameters("key" -> apiKey)
 } getOrElse {
   logger.debug("no authorization information found, exiting")
   sys.exit(401)
 }

人们对各种预定义的构建块越熟悉，就越能更快、更高效地将问题的至少一个初始解决方案组合在一起。早期版本的 process tree 示例说明了这种风格，而更高版本反映了对代码质量的更多重视，特别是可测试性和避免代码重复。

待处理

for 使用用于嵌入有状态步骤(如日志记录)的块

4.1.4. 挑战

我们能(高效与否)写作吗？

length ， sum ， reverse ， filter ， find ， map 作为折叠体，即， foldLeft 或 foldRight ？
foldLeft 或 foldRight 作为 map ？！？
reverse 或 filter 作为一个 map ？

一些提示：

仔细查看各自的域和同域(参数和结果类型)。它们合身吗？
哪一个更一般， map 或 fold ？

4.1.5. 函数风格中的模块化和依赖项注入

在函数式编程范例中，第一类函数，即将函数作为参数值传递给其他函数、方法和构造函数的能力，为前面讨论的面向对象函数提供了一种替代的模块化组合机制。

这个 iterators example 说明ITS中的功能模块化 functional/modular 包裹。

4.2. 定义代数数据类型

大多数结构属于以下类别之一：

非递归/标量：布尔型、有限枚举(包括数值类型)、try
次线性结构：(无穷集合)自然数，选项
线性结构：列表、地图
非线性结构：树、图、许多自定义域模型

它们的基本构件是 代数数据类型 与中讨论的内容相关用命令式和面向对象语言定义域模型：

(不相交)求和：变化
给定数量的乘积(元组，记录)：聚合
递归(在类型级别)
类型参数(泛型)

使用这些构建块，我们可以表达 Shape 以上示例中的域模型作为代数数据类型：：

Shape = Circle(Int)
      | Rectangle(Int, Int)
      | Group(Seq(Shape))
      | Location(Int, Int, Shape)

我们可以将形状上的行为单独定义为函数。以下是说明此方法的示例：

我们确定了以下结构和行为问题：

结构
内容
遍历
正在处理中

到目前为止，结构和内容组合在代数数据类型的定义中，而遍历和处理组合在该代数数据类型的行为定义中。

4.2.1. 结构关注点分离

然而，我们可以在结构和内容的帮助下实现结构和内容的分离 参数多态性 即，将代数数据类型 通用的 就内容而言。预定义的集合是这种分离的一个示例，以及 generic org chart 举个例子。

4.3. 代数数据类型的行为

下面是代数数据类型上的其他行为示例。正如预期的那样，对于递归类型，行为通常也是递归的。

在这些示例中，上面标识的遍历和处理关注点仍然是组合的。

4.3.1. 基于递归思维的行为

为了理解递归思维，让我们来探索熟悉的 shapes example 。我们将从一个合适的代数类型定义和一些示例实例开始：

enum Shape:
  case Rectangle(width: Int, height: Int)
  // ...
  case Location(x: Int, y: Int, shape: Shape)
  case Group(shapes: Shape*)

val r = Rectangle(20, 40)
val q = Rectangle(20, 40)
val p = Rectangle(20, 30)

val g = Group(r, Group(q, p), Location(10, 15, r))

现在让我们尝试实现一个 countGroup 行为。这是不完整的，但应该编译； ??? 是“尚未实施”(Nyi)的方便占位符：

def countGroup(s: Shape): Int = s match
  case Rectangle(w, h) => 0
  case Location(x, y, c) => ???
  case Group(shapes @ _*) => ???

不出所料， countGroup 对于矩形返回0，但会引发 NYI 组或位置节点例外。

现在我们需要应用递归思维：

对于位置，子节点可能具有组节点。
对于GROUP，当前节点是组节点，再加上子节点可能具有组节点。

因此：：

def countGroup(s: Shape): Int = s match
  case Rectangle(w, h) => 0
  case Location(x, y, c) => countGroup(c)
  case Group(shapes @ _*) =>
    var sum = 1
    for c <- shapes do
      sum += countGroup(c)
    sum

现在 countGroup(g) 不出所料，返回2，尽管这是一个Java风格的命令式实现。同样，我们可以使用 foreach 方法而不是所谓的for complect：：

case Group(shapes @ _*) =>
  var sum = 1
  shapes.foreach { c =>
    sum += countGroup(c)
  }
  sum

现在……击鼓……我们有机会将这段代码转换成函数式的、适用的、不变的风格：：

case Group(shapes @ _*) =>
  1 + shapes.map { c => countGroup(c) } .sum

其中map转换集合中的每一项，结果是将给定函数应用于该项，sum将集合中的所有项相加。

以下是需要考虑的几点：

哪个设计模式描述了我们传递给 map 方法呢？
在您能想到的任何功能和/或非功能标准方面，您如何比较这三种实现？

4.3.2. 行为关注点分离

脑海中浮现的一个问题是，它们是否可以分开，类似于集合上的预定义高阶方法，例如 foldLeft ， foldRight ， map 这些方法比访问者模式或我们等效的递归行为更进一步：它们处理遍历对我们的关心，并将其与 正在处理中 关注点，我们通过提供合适的参数函数来处理该关注点。

这个问题有两个部分的答案：是的，我们可以为我们自己的代数数据类型定义此类高阶行为的自定义实现。此外，这就是它变得非常有趣的地方，我们可以有一个适用于所有代数数据类型的通用实现，其中任何节点的子节点在数量上都是固定的，或者存储在一个集合中，该集合具有 map 方法。

另一个看似深奥的问题是，我们是否可以将递归本身作为一种功能模式。是的，我们可以。在……里面 this factorial example ，即 Y -组合器处理递归令人担忧的问题 对于行为 并将其与递归的每一步中应该发生的事情的关注点分开。

我们很快就会在类型级别上研究等价的概念。

4.4. 仔细查看列表上的预定义行为

在本节中，我们将“在幕后”了解列表中的一些关键预定义行为。

就业绩而言，我们必须牢记 lists are head/tail-optimized 。换句话说，这些基本上是单链表，所以我们访问列表第一个节点的任何行为都是恒定时间的，而涉及列表后面节点的行为都是线性时间的。在实践中，可接受的性能通常意味着我们处理整个列表的行为的线性时间。

另外，我们需要意识到， 空间复杂性 。显然，我们已经为将要传递给行为的参数使用了空间，并且愿意将空间用于我们要返回的结果，所以重点放在 附加内容 堆栈上的临时空间，如果可能，我们希望保持不变。(此讨论与以下内容密切相关常量空间复杂性的重要性，其中假设存储了参数和结果对外。)

尾递归 ，其中方法或函数体中的最后一步是方法本身的递归调用，是实现恒定空间复杂性的有效技术，只要行为可以用尾递归方式表示即可。在某些情况下，我们可以用尾递归方式重写实现，方法是引入 累加器 参数，其中我们实质上在累加器中构建结果，然后在到达递归的基本情况后返回该结果。尾递归实现可以很容易地转换为 while 通过在列表结构中引入表示进度的可变变量来实现循环。这 reverse example 更详细地说明了这些概念和技术。

以下是一些观察结果：

foldLeft 通常是我们想要的： linear-time 和 constant-space (自然尾递归)。
foldRight 是 linear-time 和 linear-space ( not 尾部-递归)，但符合列表的自然头部-尾部结构。
xs.foldRight(z)(f) == xs.reverse.foldLeft(z)(g) 哪里 g 是 f 随着论据的转换。

要查看这些函数的实际Scala库实现，请首先在API文档中找到所需的方法，展开、查找 定义类 ，沿着最左边的Definition类的链接，然后是该类的Scala源代码的链接，最后查找实际的方法。出于性能原因，这些专业实现往往比我们预期的更复杂。以下是一些示例：

有关空间复杂度和尾部递归的更多详细信息，请查看以下参考资料：

4.5. 类型级别的关注点分离

备注

这一部分主要针对研究生，但也鼓励高级本科生学习。

总体方法是通过将代数数据类型形式化为初始F-代数来将递归与结构分开。

4.5.1. 关键概念

我们首先需要定义一些关键概念：

(Endo)functor: 类型构造函数(泛型集合)，其中 map 满足以下条件的方法身份和作文法律：：
```
c.map(identity) == c
c.map(g compose f) == c.map(f).map(g)
```
一些熟悉的内函数示例如下
- Option
- List
- 泛型树，如 org chart
这个 Fix -组合器处理递归令人担忧的问题 对于结构而言 并将其与结构本身的性质分开。
Generalized fold = catamorphism (cata) for breaking down a data structure to a result value.
F-algebra: 这就是 fold ，它有一个函数器 F 以及载体对象，即折叠的结果类型。
unfold = 变形作用 为建设来自其他值的数据结构。
F-coalgebra ：这是 unfold (生成器)，它也有一个函数器 F 以及载体对象，即包装在函数器中的种子和生成值的类型。
Initial F-algebra ：这是我们函数器的最小固定点 F 并且等同于我们原来的递归类型。我们通过应用 Fix -组合器到 F 。
我们通过组合以下命令来恢复原始的递归行为 cata 以及我们特定的F-代数版本的行为。

待处理

实际应用

4.5.2. 示例

也许最好并排查看一些常规示例和基于F代数的示例：

expressions-scala versus expressions-algebraic-scala
Sakai上的项目1a(形状)与项目1b(使用F-代数重做的形状)

还有一些其他的例子。 here 。

4.5.3. 什么 `Fix` 会吗？

Fix[F] 通过应用函数器，基本上打通了“递归结” F 对它自己来说。这形成了 固定点 函数的嵌套类型，允许从函数生成的所有结构具有相同的类型，而不是与结构的嵌套相对应的嵌套类型。

例如，我们可以使用函数器来表示熟悉的项和(可选)下一个节点的聚合 F[A] = (Int, Option[A]) 。这使我们能够定义链表：

(1, Some((2, Some((3, None)))))

问题是这些列表的类型是嵌套的：：

scala> (1, Some((2, Some((3, None)))))
res0: (Int, Some[(Int, Some[(Int, None.type)])]) = (1,Some((2,Some((3,None)))))

因此不同长度的列表具有不同的类型。

通过使用合适的 Fix 在我们的函数器上，他们最终都有 same 类型，即 Fix ：：

case class Fix(unFix: (Int, Option[Fix]))

scala> Fix((1, Some(Fix((2, Some(Fix((3, None))))))))
res1: Fix = Fix((1,Some(Fix((2,Some(Fix((3,None))))))))

这就是为什么我们通常一开始就以递归方式定义这样的类型。

4.5.4. 广义褶皱(变质作用)

下一个问题是实现通用折叠方法的目的是什么？ Fix 看起来像，也被称为 变质作用 。继续我们的 Fix 完毕 (Int, Option[A]) 例如，我们使用以下命令在此函数器上执行递归 map ，它保留第一个组件并调用合适的 map 在该对的第二个组件上：：

case class Fix(unFix: (Int, Option[Fix])):
  def cata[B](f: ((Int, Option[B])) => B): B = f((this.unFix._1, this.unFix._2.map(_.cata(f))))

现在我们可以定义代数在我们的函数器上，例如：

def sum(arg: (Int, Option[Int])): Int = arg match
  case (i, None) => i
  case (i, Some(s)) => i + s

res1.cata(sum) // 6

这些与没有责任穿越结构的参观者非常相似。这就是为什么它们不是递归的。相反，变质作用负责递归。

对于任意函数器 F ，代码如下所示：：

case class Fix(unFix: F[Fix]):
  def cata[B](f: F[B] => B): B = f(this.unFix.map(_.cata(f)))

对于任意的 载波类型 B ，这个论点 f 类型的 F[B] => B 是一种 F -代数。 Fix[F] 是不是 首字母 F -代数与变质作用 cata 之间产生唯一的结构保持映射(同态) Fix[F] 和 f 。

4.5.5. 关键见解

通过从F-代数的角度看待递归代数数据类型，我们能够识别它们之间以前不明显的结构共性。

非通用： Nat ， Expr ， Shape 等。
通用： List ， Tree ， OrgChart 等。

研究这些问题也很有帮助：

你觉得怎么样，比方说， Option ， List ，以及 Tree 有血缘关系吗？
你是怎么做到的
- Option relate to List
- List relate to Tree
- Tree 与什么有关？！？
- ..。
我们如何表示一个空的结构？
为什么在定义中没有多个分支 cata 上面？递归何时终止？
是 cata 尾部递归？可以还是应该是这样的呢？

在行为方面，我们认识到公共抽象带来的代码重用的巨大潜力：

有关F-代数和数据类型泛型编程的更多详细信息，请查看以下参考资料：

如果您想更深入地研究挖洞，请查看 map 被叫 traverse 。我们的一些示例包括以下实现 traverse 。

4.6. 其他有用的抽象

备注

这一部分主要针对研究生，但也鼓励高级本科生学习。

在本节中，我们将讨论几个更有用但相对简单的抽象。

4.6.1. 么半群

A Monoid 是具有关联二元运算和标识元素的类型。(这等效于具有单位元素的半群。)示例包括：

带加和零的整数
带乘一的整数
带有追加的列表和空列表
具有串联的字符串和空字符串

这个 么半群定律 源于么半群的定义：操作必须是关联的，并且标识元素必须是左标识和右标识。

下面是使用Scalaz库的么半群的示例 here

4.6.2. 单子

A Monad 是具有两个操作的类型构造函数(泛型集合)， point (也称为 return 或 unit )和 flatMap (也称为 bind )。单音节是一种有效的方式来表示 上下文 计算被“包装”在其中的计算。因此，单体抽象使得人们能够将计算本身及其上下文的关注点分开。示例包括：

Option 和 Try ：计算中的潜在故障
List ：计算中的不确定性，即计算可能有多个结果
Id ：Identity Monad，一个实际上不做任何事情的包装器
Future ：计算异步进行(在后台)

下面是使用Scalaz库的单体示例 here 。

4.6.3. 观察结果

Scala库包括各种有效的单体结构，特别是刚才提到的那些。Scala没有定义的是Monad抽象本身。
这就是Scalaz或Cats等库的用武之地：它们以这样一种方式定义这些抽象：我们可以将现有类型或我们自己的类型改造为所需抽象的实例，使用 Typeclass图案 ，这是一种表示Haskell样式类型类的技术。
Typeclass模式的示例包括 Functor 和 Traverse 我们的表达式和形状示例中的实例。
这是学习Scalaz的一个很好的参考资料，Scalaz是一个定义这些不同抽象的库 here 。

4.7. 参考文献

待处理

在此处放置章节级别的参考资料

4. 函数式编程范式

4.1. 使用内置类型和行为解决问题

4.1.1. 示例

4.1.2. 其他对集合的重要操作

4.1.3. 处理连续的故障

4.1.4. 挑战

4.1.5. 函数风格中的模块化和依赖项注入

4.2. 定义代数数据类型

4.2.1. 结构关注点分离

4.3. 代数数据类型的行为

4.3.1. 基于递归思维的行为

4.3.2. 行为关注点分离

4.4. 仔细查看列表上的预定义行为

4.5. 类型级别的关注点分离

4.5.1. 关键概念

4.5.2. 示例

4.5.3. 什么 Fix 会吗？

4.5.4. 广义褶皱(变质作用)

4.5.5. 关键见解

4.6. 其他有用的抽象

4.6.1. 么半群

4.6.2. 单子

4.6.3. 观察结果

4.7. 参考文献

4.5.3. 什么 `Fix` 会吗？