#技术 #Scala #函数式编程

Overview

第一部分主要使用Scala来函数式编程，介绍了核心概念。
我们的目标是追求使用『纯函数』编程。

我的练习题

背景知识：Scala是在JVM上运行的一门语言，是带有自动类型推断的静态类型语言。使用它即可以使用与Java类似的命令式编程（甚至兼容Java库），也可实现纯的函数式编程。

什么是函数式编程

核心理解：通过对比命令式编程与函数式编程，来体会函数式编程的优点。
场景：实现一个使用咖啡厅付款的程序，实现buyCoffee的功能，输入信用卡，我们对他扣款，最后获得一杯咖啡

// 命令式实现
class Cafe {
  def buyCoffee(cc: CreditCard): Coffee = {
    val cup = new Coffee()
    cc.charge(cup.price) // 这里发生了状态变化
    cup
  }
}
// 或者高级一点：使用一个单独的类来支付
class Cafe {
  def buyCoffee(cc: CreditCard, p: Payments): Coffee = {
    val cup = new Coffee()
    p.charge(cc,cup.price)  // 通过p来发起支付，这里也发生了状态变化
    cup
  }
}

问题是

函数式的方法如下：


// 函数式实现
class Cafe {
  // 没有副作用
  def buyCoffee(cc: CreditCard): (Coffee, Charge) = {
    val cup = new Coffee()
    (cup,Charge(cc,cup.price)) // 没有实际扣款，我们只是把状态变化这个行为封装后输出了。
  }
}

把支付这个『副作用』推迟。本质上，支付是引起了外部某个状态的变化，我们这种状态的变化通过返回值传递出去（把状态变化抽象了）。

// charge定义
case class Charge(cc: CreditCard, amount: Double){
  // 合并付款的函数
  def combine(other: Charge): Charge = 
    if (cc == other.cc)
      Charge(cc, amount + other.amount)
    else
      throw new Exception("can't combine chareges to different cards")
}

class Cafe {
  // 买多杯咖啡
  def buyCoffees(cc: CreditCard,n: Int): (List[Coffee], Charge) = {
    val purchases: List[(Coffee, Charge)] = List.fill(n)(buyCoffee(cc))
    val (coffees, charges) = purchases.unzip
    // 合并了付款，依然没有副作用
    (coffees,charges.reduce((c1, c2) => c1.combine(c2))) 
  }
  // 更复杂的需求：比如买了N被咖啡，用了多个不同信用卡，合并相同信用卡的付款。
  def coalesce(charges: List[Charge]): List[Charge]= {
    charges.groupBy(_.cc).values.map(_.reduce(_ combine _)).toList
  }
}

上面我们所有操作的目标就是吧副作用去除，这样写出的函数可以叫做『纯函数』
由此，我们很容易得到纯函数的几个特点

纯函数的定义：如果一个函数的参数是引用透明且函数调用也是引用透明，那么他就纯函数

纯函数的优点：

函数式编程

核心理解：

scala的程序的基本组成

一般当我们说模块时，就是指的object xxx {}定义的单例对象，我们import xxx表示导入这个module。在shell中load包含object的文件，系统会提示defined module xxx

此外，我们也会import XXX 其中XXX是类class XXX{}。这表示引入类，他不是模块！。在shell中load包含class的文件，系统会提示defined class XXX

模块 && 对象 && 命名空间

理解这三个概念是一个东西，

高阶函数

核心实现：函数像变量一样，可以再赋值给其他变量，存储在数据结构，当做参数传递
用乘积的例子，分别用普通递归和尾递归实现。其中尾递归是一种Loop的方式。

一个理解『函数也是值』的角度是：Scala中定义匿名函数（也叫函数字面量）：(x:Int) => x==9本质上是定义了一个Function2[Int, Int, Boolean]的对象。

val lessThan = new Function2[Int, Int, Boolean] {
 def apply(a: Int, b: Int) = a < b
}

高阶函数的参数的命名约定：f g h来命名函数
匿名函数作为高阶函数的参数时，匿名函数的参数的类型如果可以自动推到出，即可省略(a,b)=>a<b

练习

多态函数（泛型函数）

// 一个多态的例子
def findFirst[A](as: Array[A], p: A=>Boolean):Int={
  @annotation.tailrec
  def loop(n: Int): Int={
    if (n >= as.length) -1
    else if (p(as(n))) n
    else loop(n+1)
  }
  loop(0)
}

习惯上，用大写字母[A,B,C]表示泛型参数

通过类型实现多态

下面是一下常见的函数变换：

由于=>是右结合的操作符，A => B => C 与 A => (B => C) 等价。含义是输入是一个值，输出是一个函数

其他技巧

函数与过程：我们一般用『过程』表示有副作用的方法，用函数表示没有副作用的方法

函数式数据结构

核心理解：

本书第一部分中，除了List的定义的函数都是在外部的伴生对象里以独立函数的形式提供，其他的结构（Option，Stream，State）都尽量把相关方法放在了接口中。（List没有特殊的原因，只是示例，一般都应该在接口里定义）

定义函数式数据结构：List

实现一个List:

涉及的技术细节如下

scala定义class/trait

Nothing的使用

参考这篇，对比了Scala常见的『空』

case object vs case class

用Python实现链表

https://python.freelycode.com/contribution/detail/1021
同样是cons结构

List的各种函数的实现

基本知识：模式匹配

定义：可以侵入到表达式的数据结构内部，对这个结构进行检验和提取子表达式。

数据共享

List中减少赋值，对比tail与init（如何实现高效的init，需要改变数据结构，参考vector，使用了trie）

类型推导的改进

基本函数的实现

实现基本函数sum，product

泛化高阶函数的实现与应用

重要实现：

其他实现
zipWith

组合应用:

flatmap后面的map在这里用链式调用也行。之所以嵌套调用，是为了和后面Option等应用兼容

效率问题

（题3.24）
hasSubsequence：使用if语句显式提前终止递归。写法不太『优美』，Stream有更好的写法，效率和提前终止类似

标准库中的List

树的数据结构

遗留问题

  1. 3.7 foldRight实现product时如何短路（第五章解答:使用Stream的foldRight）
  2. 3.24 如何高效实现hasSubsequence（第五章：使用Stream的tails方法）

不用异常来错误处理

核心理解：

抛出异常的问题

参考示例4.1的例子，很容易发现下面的问题
抛出异常的缺点：

除了抛出异常，还可以怎么做?

我们还可以使用类似于C语言的方法：返回一个特定的普通值（或者默认值）来表示异常。
缺点也很明显

使用Option方案，也是基于返回普通值的方式，但是解决了上面的问题：

科普： 部分函数 VS 完全函数。抛出异常的函数就是部分函数，使用Option就是把部分函数转化为了完全函数。
部分函数的定义：对于一些输入没有结果的函数。例如：抛出异常的函数，case语句定义的函数。

Option数据类型定义 && 常用函数

Option使用模式分析

Option的使用场景是什么？
使用在部分函数的返回值中，典型地

一旦我们把某个方法改造为返回Option的函数如def func():Option[A]
我们可以使用func().map(f).getOrElse 这种模式处理并获得结果。
如果func()是一个数据库查询函数，

转化

错误处理

我们多某个Option对象，可以像处理List那样处理

  1. 1个输入，1个值输出链式处理：func().map.getOrElse ，其中func()返回一个Option
  2. 2个输入，1个值输出：map2(op1,op2)(f)，只要一个None，结果就是None
  3. n个输入，1个值输出：只要一个None，结果就是None
  1. n个输入，n个输出（一个List输出）

我们可以把一个带着Option的调用过程（即把上面1/2/3合并）描述为：
从n个Option取出里面的值，来调用函数f(a1,a2...an)。任何一个a为None则结果为None
这都可以用for推导 来表示！！！

注意

一个常识：实现了map&&flatMap的对象可以支持for推导

Either

严格求值与惰性求值

核心目标：实现一个更好的List--Stream（更高效）
核心理解：

List的一个问题

观察下面的List的链式使用方法

List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)

有一个明显的效率问题，我们会：

然而，一个显而易见的优化方式是，合并这3个步骤成为单个函数。（虽然filter不是很好合并，这里从概念是上感受）我们希望这个步骤能自动完成

严格与非严格求职

惰性列表Stream

数据结构定义

sealed trait Stream[+A] 
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

object Stream {
 def cons[A](h: => A, t: => Stream[A]): Stream[A] = {
    lazy val h1 = h
    lazy val t1 = t
    Cons(() => h1, () => t1)
  }

  def empty[A]: Stream[A] = Empty

  def apply[A](as: A*): Stream[A] = {
    if (as.isEmpty) empty
    else cons(as.head, apply(as.tail: _*))
  }
}

对比List几个重要的不同点：

Helper函数

helper函数是从Stream中获取一部分数据的方法：

描述与求值的分离：Stream关键函数的实现

理解Stream的FoldRight函数

对比Stream的foldRight和List的foldRight，参考代码

应用：可以使用Stream版本的FoldRight实现『中断』效果。提高类似exists、forAll函数的效率。一个极端的例子如下（没必要用这个方法实现）：

  def headOption_foldRight(): Option[A] = {
    foldRight(None: Option[A])((x, _) => Some(x))
  }

Stream的链式调用&&优点--一等循环

对应的，我们可以基于foldRight实现Stream版本的map，flatMap，append等函数。

这些惰性版本的函数有一个巨大的优势：一等循环（first-class loops）。

Stream(1,2,3,4).map(_ + 10).filter(_ %2 == 0).toList

一等循环解决了本章开头的提出的问题：如何自动多个函数。当面执行上述代码时，在map调用后立即遍历Stream，在filter调用后也不会执行，而是在最后toList时实际发生操作。你会发现循环延迟执行。最终，只在一次循环中完成了多步计算（相当于自动合并了）。

一个有趣的应用：

  // 虽然filter的含义是过滤整个链表，但是由于是惰性求值，我们只用了head，所以过滤出head之后就不会往后遍历了
  def find(p: A => Boolean): Option[A] = {
    filter(p).headOption()
  }

Stream应用：无限流

因为Stream的惰性（增量）的特点，可以用它来实现一个无限长度的Stream

    def constant[A](a: A): Stream[A] = {
      lazy val repeat: Stream[A] = Stream.cons(a, repeat)
      repeat
    }
    val ones: Stream[Int] = constant(1)

另外一个有趣的应用是里有无限流生成一个无限斐波那契数列

Stream应用：共递归 && unfold

unfold是这么一个函数：

  def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] = {
    f(z) match {
      case None => empty[A] // 如果新状态为None，这结束
      case Some((a, s)) => Stream.cons(a, unfold(s)(f))
    }
  }

unfold就是共递归函数。
对比『递归』与『共递归』：

共递归也叫守护递归，生成能力（f控制的的结束）也叫共结束

unfold的应用

对比foldRight和unfold（参考书笔记p65）

Stream应用：tails函数实现hasSubsequence

纯函数式状态

这章很难理解，慢慢体会。建议状态转化函数（Rand/State）类比Option。
核心：使用函数式编程实现带状态的编程

理解：

副作用版本的随机数生成器

Scala函数库 scala.until.Random就是一个带副作用的随机函数

val rng= new scala.util.Random // 可以用带种子的版本
rng.nextInt 
rng.nextInt // 返回不同的值

缺点：
我们很难预测得到的值，就很难测试&&复现bug。因为即使相同Random的种子，我们还必须保证调用nextInt的次数相同（伪随机）。本质上，是Random内部封装了一个状态，每次我们调用nextInt时，他内部会存储这个状态（副作用）
我补充：
有状态更困难的是在并发的时候，对共享状态的变化不可控！容易导致难以复现bug。

纯函数版本的随机数生成器

核心：显示 传递状态，把状态和值一起返回。

trait RNG {
  def nextInt: (Int, RNG)
}

这种做法导致我们不行每次使用新的RNG对象来生成随机数。

val rng = SimpleRNG(22)
val (n1,rng1) = rng.nextInt
val (n2,rng2) = rng1.nextInt // 注意这里用的上面的新的RNG对象rng1

其中SimpleRNG实现使用了『线性同余生成器』
优点是：对于某个确定的RNG实例，每次调用都会返回相同的值。

上面我们成功改造了nextInt为『纯函数式』的实现。其实这个改造方法是通用的。

// 带副作用的版本，s就是共享的状态
class Foo {
  private var s:FooState = ...
  def bar: Bar // 假设，他是一个会改变s的函数
  def baz: Int // 假设，他是一个会改变s的函数
}
// 纯函数的版本
trait Foo {
  def bar: (Bar, Foo) // Foo包含了新状态
  def baz: (Int, Foo) // Foo包含了新状态
}

一个效率问题：我们返回的状态是一个新的值（SimpleRNG实现），相当于拷贝了一个值。相比与『副作用』的版本，直接修改内存中的状态，比较低效。有两种办法：

用纯函数实现带有状态的API

核心：实现输入状态，输出（新）状态的函数式API。

我继续用随机数生成器作为例子，上面我们实现了RNG中的nextInt方法，我建议分下来看：

目的：我们接着实现和状态相关的其他状态转换API：与改造后的nextInt类似，所有API函数都需要接受一个状态，输出一个新状态，这样我们就可以链式地传递状态了。

另一个角度看：都改造成放在RNG类里面的方法也是可以的

我们这里还是基于之前的nextInt（在RNG类里面的）那个，来实现其他随机数生成器：

这些函数都是：输入是一个RNG（实现了nextInt的）。用它生成新的值和状态，然后对生成的值进行处理，返回处理后值&&刚才生成的状态。
即：RNG=>(value,RNG)

  def nonNegativeInt(rng: RNG): (Int, RNG) = {
    val (n1, rng1) = rng.nextInt
    val n = if (n1 < 0) -(n1 + 1) else n1 // 仅仅转换了生成是数字，依然有上面的状态
    (n, rng1)
  }  
  def randomPair(rng: RNG): ((Int, Int), RNG) = {
    val (n1, rng1) = rng.nextInt
    val (n2, rng2) = rng1.nextInt // 注意状态的串联
    ((n1, n2), rng2)
  }

类似的随机数生成器有很多，参考github

可以发现这些所有的实现有通用的模式：
RNG=>(value,RNG)，这里的RNG可以理解成状态，它就是一个值，与nextInt无关，nextInt看成一个无关的函数就行，输入是seed输出一个数）

注：书中的随机数的例子不好理解，RNG本质就是个状态，夹杂了nextInt方法实在令人费解，不如最后的一到习题中的状态定义。

更好方法实现带状态的API

核心：上面实现的nonNegativeInt， randomPair方法比较『笨』，实现这两个方法都用到了nextInt，都是显示传递了rng状态。如果我们已经实现了一个状态函数，其他的函数可以由它衍生而来。具体来说，直接由生成的随机数Int的函数，得到nonNegativeInt或者randomPair。而不是每次都要调用nextInt，然后传递状态。因此我们需要：

我们把RNG=>(value,RNG)这个函数，看做一个整体定义为：

type Rand[+A] = RNG => (A, RNG)

一定注意：他是个函数！！！

首先，把生成随机数int的函数改造为符合RNG=>(value,RNG)的状态转换函数：

val int: Rand[Int] = rng => rng.nextInt // 注意理解int与nextInt函数的不同

定义unit函数，返回常量值与状态

def unit[A](a: A): Rand[A] = rng => (a, rng)

下面我们基于这个int函数可以生成nonNegativeInt randomDouble等等。可以使用map函数可以帮助我们实现状态/函数之间的转化--map（输入是函数，输出也是函数）：

我们还可以把多个状态/函数组合起来--map2：

除此之外，还有状态/函数的嵌套--flatmap：

通用状态行为数据类型

我们泛化Rand，定义了更通用的类型：

// 本质上是一个函数
type State[S, +A] = S => (A, S)

为了后续支持for推导，我们使用另一种等价的表示方法

/**
 * 用class内的函数对象(run变量)来代表上面的函数
 */
case class State[S, +A](run: S => (A, S)) {
    def map = ...
    def flatMap = ...
}

// Rand的定义
type Rand[+A] = State[RNG, A]

相似的，我们可以对State实现在上面Rand里面实现的所有函数。因为使用了run来代表函数，因此有些差别。

纯函数式命令编程

for推导

当上面的State对象实现了map、flatMap时，我们可以使用for的语法糖

val ns: Rand[List[Int]] =
	int.flatMap(x =>
                int.flatMap( y=>
                            ints(x).map(xs =>  // ints为生成x个随机整数
                                       xs.map(_ % y))
                           )
               )
// 等价
val ns: Rand[List[Int]] = for {
    x <- int
    y <- int
    xs <- int(x)
} yield xs.map(_ % y)

状态修改

modify的基本的想法是，

def get[S]: State[S, S] = State(s => (s, s))

def set[S](s: S): State[S, Unit] = State(_ => ((), s))

def modify[S](f: S => S): State[S, Unit] = {
  get.flatMap(s1 => {
    val x = set(f(s1))
    x
  })
}

有限状态机

基于上面定义的函数我们可以实现一个有限自动机状态机

一个例子（书中练习）投币的机器(p61 6.11)
练习参考

其他：

总结：重要的抽象函数

如果把函数式编程看成一个数据的pipeline

关注分离：