考虑对每个练习都自己实现一波，尽量使用最纯的方式，即不仅函数本身是纯的，内部也不有任何局部的副作用（这在工程实践中肯定是不好的）。

2.1 尾递归的斐波那契

题目要求写一个递归函数，获取第 n 个斐波那契数。第一个和第二个斐波那契数分别为 0，1。

这一题讨论了尾递归函数，以及嵌套（局部）函数定义，其实现是比较显然的。

def fib(n: Int): Int = {
  @tailrec
  def go(a: Int, b: Int, n: Int): Int = 
    if (n <= 1) a else go(b, a + b, n - 1)
  go(0, 1, n)
}

一般该尾递归的辅助函数会命名为 go 或 loop（Haskell 里似乎喜欢叫 helper）。应当显式地增加@tailrec注解，以保证编译器会将其进行尾递归优化。如果优化无法进行，则将无法通过编译。

2.2 isSorted

该题要求实现一个 isSorted 方法，签名为def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean。该题考查泛型（类型变量）的使用，类型变量就像函数参数一样，函数参数在函数体中引用，而类型变量在类型中引用。

也需要注意，这里使用的是 Array，因此不用考虑像 Haskell 中的 List 那样递归，使用索引进行递归即可。

def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
  def go(index: Int): Boolean = {
    if (index >= as.length) true // 基线条件
    else if (ordered(as(index - 1), as(index))) go(index + 1) // 每次比较 index - 1 和 index
    else false
  }
  go(1)
}

需要注意的是，这玩意如果要调用的话，直接写isSorted(Array(1,2,2),_ <= _)是不行的，这是 Scala 类型系统一个非常蛋疼的地方——仅从第一个参数 as 的类型输入里，它居然推不出第二个参数 ordered 的具体类型。就连 Java 也能干这个鸭！

解决方案有几个——指定函数的参数（也可以带上返回值，但没必要），强制指定类型 A，强制指定 ordered 的类型，使用柯里化函数重新定义 isSorted 并调用，它们的语法分别为：

isSorted(Array(1,2,2), (x: Int, y: Int) => x <= y)
isSorted[Int](Array(1,2,2),_ <= _)
isSorted(Array(1, 2, 2), (_ <= _) : (Int, Int) => Boolean)
isSorted(Array(1,2,2))(_ <= _)

显然，只有第二种和第四种是比较合适的，Scala 的几个高阶函数比如 fold 等使用第四种方法。

2.3 curry

这三个都是比较经典的题目了——柯里化，反柯里化，函数组合。

1	`def curry[A, B, C](f: (A, B) => C): A => B => C = a => b => f(a, b)`

2.4 uncurry

1	`def uncurry[A, B, C](fn: A => B => C): (A, B) => C = (a, b) => fn(a)(b)`

2.5 compose

Haskell 中的 compose 就是.函数。

1 2	`(.) :: (b -> c) -> (a -> b) -> (a -> c) f . g = \x -> f(g(x))`

1	`def compose[A, B, C](f: B => C, g: A => B): A => C = x => f(g(x))`

3.1 模式匹配

这就不是道编程题，答案是 3，模式匹配会从上往下匹配，找到第一个匹配到的。

3.2 tail

tail 也是一个经典的函数，这里有个问题，就是如果原 List 是 Nil 的时候，tail 该返回什么？在 Haskell 中，此举会抛出异常，可以写一个全函数——

def tail[A](l: List[A]): List[A] = l match {
  case Nil => Nil
  case _::xs => xs
}

其它选择是使用 Option，Try 等，抛出异常是中策，返回 null 是下下下策。

3.3 setHead

重设列表的 head。函数式的 setter 是怎样的呢？这样。

def setHead[A](l: List[A], neoHead: A): List[A] = l match {
  case Nil => Nil
  case _::xs => neoHead::xs
}

3.4 drop

移除掉前 n 个元素，返回剩下的就是 drop 函数。这里一个问题是如果 n 大于列表的长度时该怎么解决，这里返回 Nil。n 小于 0 的时候按等于 0 考虑。

def drop[A](l: List[A], n: Int): List[A] = l match {
  case Nil => Nil
  case _::xs if n > 0 => drop(xs, n - 1)
  case _ => l
}

3.5 dropWhile

有时候会把 take 和 drop 混淆，想象 take 把前面的元素“拿起来”，drop 把前面的元素“丢掉”。takeWhile 就是一直“拿”，直到不符合；dropWhile 就是一直“丢”，直到不符合。

def dropWhile[A](l: List[A], p: A => Boolean): List[A] = l match {
  case Nil => Nil
  case x::xs if p(x) => dropWhile(xs, p)
  case _ => l
}

3.6 init

在 List 头部增加元素是常量级的开销，但在尾部进行操作就不是如此了，为了在尾部进行操作，之前的每一个元素都要被修改。想象一下一个链表1 -> 2 -> 3 -> Nil，现在要在尾部添加一个元素 4，这时候若要保证原链表不变，则必须将整个链表复制一份，再在尾部添加一个元素；但是若在头部添加呢？直接上即可。新的链表是4 -> 1 -> 2 -> 3 -> Nil，对原链表1 -> 2 -> 3 -> Nil来说，它不需要做任何改变。同理，在尾部减少元素时，将整个列表拷贝一份也是必须的。

实现 init 时考虑和普通的递归函数一样的编写流程，对于[x]，这是基线条件，返回[]，然后对其它列表x::xs，则直接原样拼接即可。init 对于空列表就比较麻了，这里不多想，直接抛异常。

def init[A](l: List[A]): List[A] = l match {
  case Nil => throw new Exception("empty list")
  case _::Nil => l
  case x::xs => x :: init(xs)
}

3.7 foldRight 能否“短路”？

foldRight 的定义如下，只要记住 foldRight 并非尾递归就容易写出它，把 op 当作右结合的二元操作符来看待有奇效。

def foldRight[A, B](l: List[A], z: B)(op: (A, B) => B): B = l match {
  case Nil => z
  case x::xs => op(x, foldRight(xs, z)(op))
}

这也不是一个编程题，但是确实很有实践意义，在很多时候能发现这样的业务需求，即我迭代集合迭代一半，突然发现后面不需要再迭代了，想现在立刻就返回，但是目前我是没找到合适的方法，唯一感觉可行的方法是利用 break 来终止，但这并不优雅，期待该书能提出更好的解决方案。

3.8 foldRight 以 Nil 为初始值，以`::`为操作符？

关于为什么此书定义函数时没有遵循数据放到最后的原则，我猜测原因是因为 Scala 是面向对象语言，而这样的话数据和参数的位置和进行方法调用时相同。

foldRight(List(1,2,3),Nil:List[Int])(_::_)会发生什么？这里可以用我之前“发明”的方法来去理解——

1 >=> 2 >=> 3 >=> Nil
=> 1 >=> 2 >=> [3]
=> 1 >=> [2, 3]
=> [1, 2, 3]

3.9 使用 foldRight 实现 length

easy。

1 2	`def length[A](l: List[A]): Int = foldRight(l, 0){(x, acc) => 1 + acc}`

3.10 foldLeft

理解 foldLeft 为尾递归，op 为左结合的二元运算符对编写 foldLeft 有帮助。

但最具建设性的想法是，对于foldLeft(List(1,2,3,4), 0)(_ + _)，它显然为(((0 + 1) + 2) + 3) + 4，容易发现，它和((1 + 2) + 3) + 4结构是完全一样的，还原后就得到了foldLeft(List(2, 3, 4), 1)(_ + _)，这已经足够编写出实现了。

def foldLeft[A, B](l: List[A], z: B)(op: (B, A) => B): B = l match {
  case Nil => z
  case x::xs => foldLeft(xs, op(z, x))(op)
}

3.11 sum，product，length

使用 foldLeft 实现这几个方法。

def sum(l: List[Int]): Int = 
  foldLeft(l, 0)(_ + _)
def product(l: List[Int]): Int = 
  foldLeft(l, 1)(_ * _)
def length[A](l: List[A]): Int = 
  foldLeft(l, 0)((acc, _) => acc + 1)

3.12 使用 fold 实现 reverse

这也是之前实现过的东西，使用flip (::)作为 op，左折叠即可。

1 2	`def reverse[A](l: List[A]): List[A] = foldLeft(l, Nil: List[A])((acc, x) => x::acc)`

3.13 使用 foldLeft 实现 foldRight

foldRight 由于是递归形式，所以可能爆栈，能否使用 foldLeft 实现 foldRight 以防止爆栈呢？

这个问题确实很难，我想到的唯一的方式是先把原列表 reverse 再进行 foldLeft，看看之后该书会提出什么好玩的解决方案。

1 2	`def foldRight_[A, B](l: List[A], z: B)(op: (A, B) => B): B = foldLeft(reverse(l), z)((acc, x) => op(x, acc))`

3.14 使用 foldLeft 或 foldRight 实现 append

append 就是 Haskell 的++。

使用右折叠的话是比较容易实现的——第一个列表作为原列表，第二个列表作为 zero，op 为::。

1 2	`def append[A](l1: List[A], l2: List[A]): List[A] = foldRight(l1, l2)(_::_)`

左折叠的话救比较蛋疼，我想到的话还得先把原列表 reverse 再 append，但考虑到它说的是“或”……

3.15 flatten

虽然题目没明确，但这显然是一个 flatten，使用折叠和 append 可以解决。

1 2	`def flatten[A](l: List[List[A]]): List[A] = foldRight(l, Nil:List[A])(append)`

为什么使用Nil:List[A]？因为它默认会认为Nil的类型是List[Nothing]，需要做一下向上转型。

3.16 给列表的每个元素 +1

虽然这里可能并不是这个意思，但 map，filter，flatMap 都可以由 fold 操作实现，因此这里都使用 fold。可以发现，foldRight 虽然会导致爆栈，但实现特定函数还是比较方便的。使用 foldLeft 就需要 reverse 了。这里其实最合适的方法是使用循环来实现。

1 2	`def plus1(l: List[Int]): List[Int] = foldRight(l, Nil:List[Int])((x, acc) => (x + 1) :: acc)`

3.17 将 List[Double] 转成 List[String]

1 2	`def allToString(l: List[Double]): List[String] = foldRight(l, Nil:List[String])((x, acc) => x.toString :: acc)`

3.18 map

1 2	`def map[A, B](l: List[A])(f: A => B): List[B] = foldRight(l, Nil:List[B])((x, acc) => f(x) :: acc)`

顺带一提，原始的方法为——

def map[A, B](l: List[A])(f: A => B): List[B] = l match {
  case Nil => Nil
  case x::xs => f(x)::map(xs)(f)
}

3.19 filter

怎么不举例子啦？

1 2	`def filter[A](l: List[A])(p: A => Boolean): List[A] = foldRight(l, Nil: List[A]){(x, acc) => if (p(x)) x :: acc else acc}`

原始的方法为——

def filter[A](l: List[A])(p: A => Boolean): List[A] = l match {
  case Nil => Nil
  case x::xs => if (p(x)) x::filter(xs)(p) else filter(xs)(p)
}

移除所有奇数的调用类似filter(List(1, 2, 3))(_ % 2 == 0)。

3.20 flatMap

flatMap 是列表的 bind 操作。

1 2	`def flatMap[A, B](l: List[A])(f: A => List[B]): List[B] = foldRight(l, Nil:List[B])((x, acc) => append(f(x), acc))`

递归法很显然，懒得写了。

3.21 使用 flatMap 实现 filter（和 map）

Scala 的 flatMap 比隔壁 Haskell 的骚操作还多一些。

1 2	`def filter[A](l: List[A])(p: A => Boolean): List[A] = flatMap(l)(x => if (p(x)) List(x) else Nil)`

再给个杀必死，使用 flatMap 实现 map。

1 2	`def map[A, B](l: List[A])(f: A => B): List[B] = flatMap(l)(x => List(f(x)))`

3.22 两个列表相应元素相加

trival，但之前的玩意可没法再用了。

def plusList(l1: List[Int], l2: List[Int]): List[Int] = (l1, l2) match {
  case (x::xs, y::ys) => (x + y) :: plusList(xs, ys)
  case (_, _) => Nil
}

3.23 zipWith

def zipWith[A, B, C](l1: List[A], l2: List[B])(f: (A, B) => C): List[C] = 
  (l1, l2) match {
    case (x::xs, y::ys) => f(x, y) :: zipWith(xs, ys)(f)
    case (_, _) => Nil
  }

3.24 是否是子序列

给定两个列表 l1，sub，检查 sub 是否是 l1 的子序列。既然书中要求使用最自然的方式，那我就编写一个最自然的方式——从 l1 的每一个元素开始，检查从当前开始时 sub 是否是前缀。更高性能的方式之后再看。

def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
  @tailrec
  def startWith(l: List[A], prefix: List[A]): Boolean = (l, prefix) match {
    case (x::xs, y::ys) => if (x == y) startWith(xs, ys) else false
    case (_, Nil) => true
    case _ => false
  }
  sup match {
    case Nil => false
    case _::xs => if (startWith(sup, sub)) true else hasSubsequence(xs, sub)
  }
}

3.25 树的 size

这里引入了一个树的 ADT——

1
2
3

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

用 Haskell 的话来说，就是——

1	`data Tree a = Leaf a \| Branch (Tree a) (Tree a)`

我还没见过根结点没有值的二叉树。

求树的 size 是简单的，对叶子结点，size 为 1，对根结点，size 为 1 + 左右子树的 size。

def size[A](tree: Tree[A]): Int = tree match {
  case Leaf(_) => 1
  case Branch(left, right) => 1 + size(left) + size(right)
}

3.26 maximum

求一棵树Tree[Int]中最大的值，这也是十分显然的。

def maximum(tree: Tree[Int]): Int = tree match {
  case Leaf(x) => x
  case Branch(left, right) => maximum(left) max maximum(right)
}

3.27 depth

求树的最大深度，这也是很显然的。

def depth[A](tree: Tree[A]): Int = tree match {
  case Leaf(x) => 1
  case Branch(left, right) => 1 + depth(left).max(depth(right))
}

3.28 map

对一棵树的所有节点（其实只有叶子结点）应用相同的操作，仍旧是非常简单的。

def map[A, B](tree: Tree[A])(fn: A => B): Tree[B] = tree match {
  case Leaf(x) => Leaf(fn(x))
  case Branch(left, right) => Branch(map(left)(fn), map(right)(fn))
}

3.29 fold

对树进行折叠，这题就离谱了。考虑上面的 size，maximum，depth 函数，它们都是对叶子结点做一个映射，然后对根结点，它会先将其左右子树进行同样的操作，再进行一个“合并”，因此可以猜测签名类似这样：

1	`def fold[A, B](tree: Tree[A])(mapper: A => B)(combiner: (B, B) => B): B`

然后就容易得到实现了——

def fold[A, B](tree: Tree[A])(mapper: A => B)(combiner: (B, B) => B): B = tree match {
  case Leaf(x) => mapper(x)
  case Branch(left, right) => combiner(fold(left)(mapper)(combiner), fold(right)(mapper)(combiner))
}

可以发现，编写 List 的折叠时，我们需要考虑 Nil 和 Cons 的情况，编写 Tree 的折叠时，我们需要考虑叶结点和根结点的情况。

4.1 实现 Option

实现 Option，其实这里最复杂的地方是关于类型系统的一些问题。签名如下——

// 这是不是说，实现代数数据类型时都应当使用协变？
sealed trait Option[+A] {
  def map[B](f: A => B): Option[B]
  def flatMap[B](f: A => Option[B]): Option[B]
  def getOrElse[B >: A](default: => B): B
  def orElse[B >: A](default: => Option[B])
  def filter(f: A => Boolean): Option[A]
}

关于这里的 getOrElse 和 orElse 方法中 B 的约束，考虑一个情形——在 Java 中，我们试图从一个 List 中取出一个值：

1 2	`List<String> lst = new ArrayList<>(){{ /* some add statement */ }}; String i = lst.get(0);`

这个问题其实就是在问，这里的 i 的声明类型可以为哪些？容易发现它需要是 String 的父类，即 String 和 Object，因此这里签名中 B 为 A 的父类是合理的。

实现是比较简单的，不再多嘴：

case class Some[+A](value: A) extends Option[A] {
  override def map[B](f: A => B) = Some(f(value))
  override def flatMap[B](f: A => Option[B]) = f(value)
  override def getOrElse[B >: A](default: => B) = value
  override def orElse[B >: A](default: => Option[B]) = this
  override def filter(f: A => Boolean) = if (f(value)) this else None
}

case object None extends Option[Nothing] {
  override def map[B](f: Nothing => B): Option[B] = None
  override def flatMap[B](f: Nothing => Option[B]): Option[B] = None
  override def getOrElse[B >: Nothing](default: => B) = default
  override def orElse[B >: Nothing](default: => Option[B]) = default
  override def filter(f: Nothing => Boolean) = None
}

我们可以编写代码进行一些测试～

def getOption[K, V](map: Map[K, V], key: K): Option[V] =
  if (map.contains(key)) Some(map(key)) else None

val map = Map(
  1 -> 2,
  2 -> 3
)

for {
  i <- getOption(map, 1)
  j <- getOption(map, 2)
} yield i + j // Some(5)

书中对该题的描述非常诡异，不知所云（英文版的如此，中文版的更甚），在搜索一番后才知道，它是要求将所有实现的方法全都塞在 trait 里面！根据书中的要求——除了 map 和 getOrElse，其它都不使用模式匹配，最后的代码应该是这样：

sealed trait Option[+A] {
  case class Some[+A](value: A) extends Option[A]
  case object None extends Option[Nothing]
  def map[B](f: A => B): Option[B] = this match {
    case None => None
    case Some(value) => Some(f(value))
  }
  def flatMap[B](f: A => Option[B]): Option[B] =
    this.map(f).getOrElse(None)
  def getOrElse[B >: A](default: => B): B = this match {
    case None => default
    case Some(value) => value
  }
  def orElse[B >: A](default: => Option[B]): Option[B] =
    this.map(Some(_)).getOrElse(default)
  def filter(f: A => Boolean): Option[A] =
    this.flatMap(value => if (f(value)) this else None)
}

由于无法使用模式匹配，flatMap，orElse 和 filter 几个函数编写起来都是非常费劲的，但其中最重要的一个地方是，能够发现getOrElse(None)能起到flatten的效果。

对 flatMap，考虑对于一个Option[Option[Int]]，对Some(Some(1))抑或是Some(None)，我们对其调用this.getOrElse(None)，能发现它们会返回Some(1)和None；而对于None，返回的则是 None，该行为和flatten一致。有了 map，有了 flatten，我们就能够实现 flatMap。

对 orElse，它的行为是若 this 是 None，则返回 default，否则返回 this。为此我们又需要检查 this 的类型，为此我们又得包装成Option[Option[A]]，使用何种手段进行包装是显然的：对于 None，我们啥都做不了，只能整 None（Some(None)也行，但这里现有的工具做不到）；对于 Some(x)，我们必须要保留这个 x（之后还得用），为此我们返回Some(Some(x))，容易发现，使用this.map(Some(_))能做到这一点。

然后我们肯定得调用 getOrElse 对其展平。根据 orElse 的需求，对于Some(Some(x))，我们希望能得到Some(x)，对于None，我们希望得到 default，答案是字面的。

对于 filter，这种的之前也写过，不用多说。

顺带一提，getOrElse 中使用了非严格求值的语法，这使它能用于一些返回默认值之外的其它目的，比如getOption(map, 1).getOrElse(throw new Exception("you bad bad"))，倘若 Java 能引入=> A语法的话，就不需要为此定义好几个方法了。

4.2 使用 flatMap 实现一个求方差的函数

函数签名如下：

1	`def variance(xs: Seq[Double]): Option[Double]`

方差的公式请自己百度。为什么这题和 Option 扯上关系呢？这一章是关于错误处理的，而能够发现，对于空的序列求平均数是无法做到的，平均数的函数我们得这么写：

def mean(xs: Seq[Double]): Option[Double] =
  if (xs.isEmpty) None else {
    val (sum, length) = xs.foldLeft((0.0, 0))
      { case ((sum, length), x) => (sum + x, length + 1) }
    Some(sum / length)
  }

在求方差时，我们先求出序列的平均数，再对序列的每个元素做映射，求映射后的序列的平均数，这里有两次求平均数，如果第一次失败，则后一次计算不应该执行，我们可以得到这样的代码：

1 2	`def variance(xs: Seq[Double]): Option[Double] = mean(xs).flatMap(m => mean(xs.map(x => math.pow(x - m, 2))))`

使用 for 描述会更加清晰。

def variance(xs: Seq[Double]): Option[Double] = for {
  m <- mean(xs)                          // 求平均数
  ys = xs.map(x => math.pow(x - m, 2))   // 对序列做映射
  result <- mean(ys)                     // 求映射后的序列的平均数
} yield result

4.3 map2

实现一个 map2 函数，其行为是把(A, B) => C的函数提升为(Option[A], Option[B]) => Option[C]，签名和实现如下。

1 2	`def map2[A, B, C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] = a.flatMap(va => b.map(vb => f(va, vb)))`

对它的实现是显然的，关键问题就是如何同时让 a 和 b 中的值处在作用域中，这在之前已经学习过了。

当然，也可以用 for 去实现，或者同时对 a 和 b 做模式匹配，只有两个都为 Some 的时候再返回Some(f(va, vb))，否则返回 None。

4.4 sequence

把List[Option[A]]转换为Option[List[A]]，当原列表中存在任意None则返回 None，否则返回Some(List(...))。

该题在 Haskell 中做过，不用多说，重点是把::进行提升，转换为(Option[A], Option[B]) => Option[C]的函数。

1 2	`def sequence[A](xs: List[Option[A]]): Option[List[A]] = xs.foldRight(Some(Nil): Option[List[A]])((x, acc) => map2(x, acc)(_ :: _))`

4.5 traverse

traverse 的签名和实现如下，它相当于是把原列表先 map 成 Option 再执行 sequence 方法，但如此的话会遍历两次列表，效率不够好，这里只需要遍历一次。

1 2	`def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] = a.foldRight(Some(Nil): Option[List[B]])((x, acc) => map2(f(x), acc)(_ :: _))`

容易发现，traverse 可以实现 sequence：

1 2	`def sequence[A](xs: List[Option[A]]): Option[List[A]] = traverse(xs)(identity)`

4.6 map，flatMap，orElse，map2

实现 Either 的 map，flatMap，orElse，map2，注意 flatMap 和 orElse 的类型定义。

sealed trait Either[+E, +A] {
  def map[B](f: A => B): Either[E, B] = this match {
    case Right(value) => Right(f(value))
    case Left(value) => Left(value)
  }
  def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] = this match {
    case Right(value) => f(value)
    case Left(value) => Left(value)
  }
  def orElse[EE >: E, B >: A](default: => Either[EE, B]): Either[EE, B] = this match {
    case Right(value) => Right(value)
    case _ => default
  }
  def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): Either[EE, C] = this match {
    case Right(aa) => b.map(bb => f(aa, bb))
    case Left(value) => Left(value)
  }
}
case class Left[+E](value: E) extends Either[E, Nothing]
case class Right[+A](value: A) extends Either[Nothing, A]

4.7 sequence 和 traverse

实现 Either 的 sequence 和 traverse 函数。

def traverse[E, A, B](l: List[A])(f: A => Either[E, B]): Either[E, List[B]] = l match {
  case Nil => Right(Nil)
  case x :: xs => f(x).map2(traverse(xs)(f))(_ :: _) // 这里的 map2 使用函数形式的话更好看一些
}
def traverse_1[E, A, B](l: List[A])(f: A => Either[E, B]): Either[E, List[B]] = 
  l.foldRight(Right(Nil): Either[E, List[B]]){(x, acc) => f(x).map2(acc)(_ :: _)}

def sequence[E, A](l: List[Either[E, A]]): Either[E, List[A]] = 
  traverse(l, identity)

4.8 如何保留所有错误？

Either 有一个缺点，就是它是“Fail Fast”的，第一次出现 Left 时就直接终止掉了，但有时候我们希望能保留每个 Left 的信息。比如我们定义一个 Person，有两个字段 name 和 age，两者都有格式要求，我们定义一个函数去创建 Person，并要求每个错误的输入都要保存错误信息。

根据 Either 的使用方法，我们首先写出这样的代码：

case class Person(name: String, age: Int)
def mkName(name: String): Either[String, String] =
  if (name == null || name.isEmpty) Left("name can't be empty!")
  else Right(name)
def mkAge(age: Int): Either[String, Int] = 
  if (age < 0 || age > 150) Left("invalid age value!")
  else Right(age)
def mkPerson(name: String, age: Int): Either[String, Person] = for {
  n <- mkName(name)
  a <- mkAge(age)
} yield Person(n, a)

这能用，但是问题是如果 name 和 age 同时不合法，则只有 name 的错误消息得以保存。这里需要使用类似 Haskell 的 Writer 这样的类型，这时候 E 要求是 Monoid。我们把 E 的范围放窄到 List[E]，可以临时定义一个 map2All 函数并用以实现满足需求的 mkPerson：

def map2All[E, A, B, C](a: Either[List[E], A], b: Either[List[E], B])(f: (A, B) => C): Either[List[E], C] = (a, b) match {
  case (Right(aa), Right(bb)) => Right(f(aa, bb))
  case (Left(aa), Left(bb)) => Left(aa ++ bb)
  case (Left(aa), _) => Left(aa)
  case (_, Left(bb)) => Left(bb)
}

// mkName 和 mkAge 的类型也需要改变
def mkPerson(name: String, age: Int): Either[List[String], Person] =
  map2All(mkName(name), mkAge(age))(Person(_, _))

但这样的话就无法使用 for 和常用高阶函数了，还是另外定义一个新的 ADT（Monad）来干这活比较好。

5.1 toList

这一章就感觉整个都挺魔法的，之后还有更多魔法～

下面的代码都假设是使用 cons 函数而非 Cons 值构造器进行构造的，因此不考虑 thunk 重复计算的问题。

实现 Stream 的 toList 方法，其计算整个 Stream 并以 List 的形式返回结果，直接写最明显的递归。

def toList(): List[A] = this match {
  case Empty => Nil
  case Cons(h, t) => h() :: t().toList()
}

考虑到该方法可能有副作用，所以使用带括号的形式。

5.2 take，drop

def take(n: Int): Stream[A] = this match {
  case Cons(h, t) if n > 0 => Stream.cons(h(), t().take(n - 1))
  case _ => Empty
}

def drop(n: Int): Stream[A] = this match {
  case _ if n <= 0 => this
  case Empty => Empty
  case Cons(h, t) => t().drop(n - 1)
}

5.3 takeWhile

takeWhile 方法，可处理无穷列表。

def takeWhile(f: A => Boolean): Stream[A] = this match {
  case Cons(h, t) if f(h()) => Stream.cons(h(), t().takeWhile(f))
  case _ => Empty
}

5.4 forAll

forAll 方法，特点是一旦遇到 false 就直接短路终止，因此可处理无穷列表，但如果全部都是 true 的话会一直运行下去。

1 2	`def forAll(p: A => Boolean): Boolean = this.foldRight(true)((x, acc) => p(x) && acc)`

5.5 使用 foldRight 实现 takeWhile 方法

def takeWhile(p: A => Boolean): Stream[A] =
  this.foldRight(Empty: Stream[A]){(x, acc) =>
    if (p(x)) cons(x, acc)
    else Empty
  }

这玩意为啥这样实现？还是考虑我的那种表示法，比如对Nat.takeWhile(_ < 5)，会得到这样的序列：

1	`0 <=< 1 <=< 2 <=< 3 <=< ... <=< n <=< []`

对后面的任意大于等于 5 的 n，n <=< []都返回[]，因此最后得到的计算序列仍旧是：

1	`0 <=< 1 <=< 2 <=< 3 <=< 4 <=< 5 <=< []`

由此便得到了正确结果。但容易发现，惰性列表的 foldRight 仍旧是会爆栈的。

5.6 使用 foldRight 实现 headOption 方法

这题……哪里难了？

1 2	`def headOption: Option[A] = this.foldRight(None: Option[A])((x, _) => Some(x))`

5.7 使用 foldRight 实现 map，filter，append，flatMap

def map[B](f: A => B): Stream[B] =
  this.foldRight(Empty: Stream[B])((x, acc) => Stream.cons(f(x), acc))
def filter(p: A => Boolean): Stream[A] =
  this.foldRight(Empty: Stream[A])((x, acc) => if (p(x)) Stream.cons(x, acc) else acc)
def append[B >: A](ys: Stream[B]): Stream[B] =
  this.foldRight(ys)(Stream.cons(_, _))
def flatMap[B](f: A => Stream[B]): Stream[B] =
  this.foldRight(Empty: Stream[B])((x, acc) => f(x).append(acc))

关于 append 奇怪的类型参数，这再次关系到协变和逆变的机制，当前还没有学习。

5.8 repeat

返回一个无穷流，每个元素都为一个给定值。

1 2	`def constant[A](n: A): Stream[A] = Stream.cons(n, constant(n))`

5.9 from

给定一个整数 n，返回 n，n + 1，n + 2……的无穷流。答案是挺显然的，这里有一个模式：之后的值由之前的值去生成。

1 2	`def from(n: Int): Stream[Int] = Stream.cons(n, from(n + 1))`

5.10 fibs

斐波那契数列的无限流。实现类似 from——对于每个元素，我们求它的时候需要知道之前的两个元素，为此这两个元素需要当作状态去传递。

def fibs: Stream[Int] = {
  def from(a: Int, b: Int): Stream[(Int, Int)] =
    Stream.cons((a, b), from(b, a + b))
  from(0, 1).map(_._1)
}

5.11 unfold

从上面的 from 和 fibs 抽象出一个更广泛的流构造函数，其不断地去维护一个状态，每一次这个状态都将生成一个新的状态以及要添加到流中的值，也可以终止该操作（当返回 None 时）。

def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] = f(z) match {
  case None => Empty
  case Some((value, nextState)) => Stream.cons(value, unfold(nextState)(f))
}

但这个函数最有趣的地方其实是它叫”unfold”。

这书的翻译真差劲！太差劲了！

5.12 使用 unfold 实现 fibs，from，constant，ones

题目本身是不难的。根据书中描述，原生的 constant，ones 只需要使用常量的内存，而 unfold 实现的无法如此，但这是可以容忍的。

// Stream function
def fibs: Stream[Int] =
  unfold((0, 1)){ case (a, b) => Some((a, (b, a + b))) }

def from(n): Stream[Int] = 
  unfold(n)(x => Some(x, x + 1))

def constant[A](elem: A): Stream[A] = 
  unfold(elem)(x => Some(x, x))

def ones: Stream[Int] = constant(1)

5.13 使用 unfold 实现 map，take，takeWhile，zipWith，zipAll

我承认，作者十分擅长给读者造成惊吓。看起来，unfold 和 fold 就“原子性”来说具有十分类似的地位。但 unfold 无法实现像 filter 这样的操作，它只能取“前缀”。它们各有所长，各有有趣之处。

unfold 实现 map，为此需要再次回忆 unfold 的机制——根据当前的状态生成一个值以及新的状态，这些值将构成新的流。答案是显然的：我们用原列表作为初始状态，每次将头部的元素做映射，然后作为返回的值，剩下的列表作为新的状态。

// Stream function
// 这个函数写着就很不爽——这里需要进行解构，但解构的话会多一层括号，只能使用偏函数语法，但偏函数的话无法得到编译器的帮助，如果写错了那错误只能在运行时发现
// 另外，f 作为第一个参数的话 Scala 无法进行类型推导，实践中不能这么干
def map[A, B](f: A => B)(xs: Stream[A]): Stream[B] =
  unfold(xs) {
    case Cons(h, t) => Some( (f(h()), t()) )
    case Empty => None
  }

takeWhile 的编写是显然的：

// Stream function
def takeWhile[A](f: A => Boolean)(xs: Stream[A]): Stream[A] =
  unfold(xs) {
    case Cons(h, t) if f(h()) => Some((h(), t()))
    case _ => None
  }

根据前面编写 take 的实践，take 需要先将原值和 index 做 zip，因此先实现 zipWith。zipWith 在其中一个流没有元素的时候终止：

// Stream function
def zipWith[A, B, C](f: (A, B) => C)(xs: Stream[A], ys: Stream[B]): Stream[C] =
  unfold((xs, ys)) {
    case (Cons(hx, tx), Cons(hy, ty)) => Some((f(hx(), hy()), (tx(), ty())))
    case _ => None
  }

然后是 take，也是显然的：

// Stream function
def take[A](n: Int)(xs: Stream[A]): Stream[A] =
  zip(xs, Stream.Nat)
    .takeWhile {case (_, index) => index < n }
    .map(_._1)

当然，也可以一个 unfold 直接解决问题。

// Stream function
def take[A](n: Int)(xs: Stream[A]): Stream[A] = 
  unfold((xs, Stream.Nat)) {
    case (Cons(hx, tx), Cons(hy, ty)) if hy() < n => Some(hx(), (tx(), ty()))
    case _ => None
  }

zipAll 函数的行为从它的签名就能看出来——相较于 zipWith，它会在其中一个流没有元素时仍旧进行操作，因此 zipAll 无法使用 zipWith 进行实现，其行为不同。

// Stream function
def zipAll[A, B](xs: Stream[A], ys: Stream[B]): Stream[(Option[A], Option[B])] = {
  def tail[X](zs: Stream[X]): Stream[X] = zs match {
    case Empty => Empty
    case Cons(_, t) => t()
  }
  unfold((xs, ys)) {
    case (Empty, Empty) => None
    case (xs, ys) => Some((xs.headOption, ys.headOption), (tail(xs), tail(ys)))
  }
}

这里别想用 for 或者 Option 的方法去做实现，Option 的组合策略和这个无关。

5.14 startsWith

检查一个流是否以另一个流为起始，这题确实挺复杂。

// Stream method
// 为啥我写这种方法都要问我要确定协变逆变呢……
def startsWith[B >: A](ys: Stream[B]): Boolean =
  Stream.zipAll(this, ys).foldRight(true){(pair, acc) =>
    pair match {
      case (Some(x), Some(y)) => x == y && acc  // 如果当前元素相等，去判断接下来的元素
      case (Some(_), None) => true              // 如果当前流有值，另一个流没有值，则 true
      case _ => false                           // 其它情况都是 false
    }
  }

5.15 tails

tails，行为类似 scan 操作，得到流的每一个元素的 tail 并组成新的流，比如对Stream(1, 2, 3)，会得到Stream(Stream(1, 2, 3), Stream(2, 3), Stream(3), Empty)。

// Stream method
def tails: Stream[Stream[A]] =
  Stream.cons(this, Stream.unfold(this) {
    case Empty => None
    case Cons(h, t) => Some((t(), t()))
  })

这个 tails 感觉很不优雅……

借助 tails 和 startsWith 方法，我们能方便地去表述 hasSubSequence 方法：

1
2
3

// Stream method
def hasSubSequence[B >: A](ys: Stream[B]): Boolean =
  tails exists (_ startsWith s)

这个 hasSubSequence 和之前写的显式递归的方法的效率是一致的，区别在于这里使用高阶函数的组合去进行表述，这是惰性列表的优越之处。放到普通列表，tails 和 startsWith 都会有额外的计算。

5.16 scanRight

实现 scan 方法。scan 方法的签名和 fold 一致，但返回值为列表，其作用效果相当于是对列表本身以及每一个 tail 进行 fold 操作并拼接成结果的列表，但性能是线性的；也可以说是每一次折叠都去暂存结果。

// Stream method
def scanRight[B](z: => B)(f: (A, B) => B): Stream[B] =
  this.foldRight(Stream.cons(z, Empty)){ case (x, acc@Cons(h, _)) => 
    Stream.cons(f(x, h()), acc) }

unfold 能实现 scanRight 吗？当然能实现，每次都从当前的状态进行折叠即可，但它无法做到线性的时间复杂度，因为之前的状态无法被储存，比如对于Stream(1, 2, 3).scanRight(0)(_ + _)，在之前已经计算过2 + 3，因此计算1 + 2 + 3的时候只需要让1加上2 + 3的结果即可。

6.1 nonNegativeInt

获得一个随机非负整数，注意当拿到的随机数正巧为Int.MinValue时，Math.abs调用仍会返回这个最小值，因此在遇到这个值的时候重新随机。

@tailrec
def nonNegativeInt(rng: RNG): (Int, RNG) = {
  val (v, r) = rng.nextInt
  if (v == Int.MinValue) nonNegativeInt(r)
  else (Math.abs(v), r)
}

6.2 double

获得一个随机的0到1的double，仍旧比较容易。

def double(rng: RNG): (Double, RNG) = {
  val (v, r) = nonNegativeInt(rng)
  (v / Int.MaxValue.toDouble, r)
}

6.3 intDouble，doubleInt，double3

这三个函数的实现都是比较简单的，主要目的是考虑它之中重复出现的模式——我们手动维护了状态的变化，即rng，r1，r2等变量。这写起来非常蛋疼，且容易出bug，难以维护。

def intDouble(rng: RNG): ((Int, Double), RNG) = {
  val (v1, r1) = rng.nextInt
  val (v2, r2) = double(r1)
  ((v1, v2), r2)
}

def doubleInt(rng: RNG): ((Double, Int), RNG) = {
  val (v1, r1) = double(rng)
  val (v2, r2) = r1.nextInt
  ((v1, v2), r2)
}

def double3(rng: RNG): ((Double, Double, Double), RNG) = {
  val (v1, r1) = double(rng)
  val (v2, r2) = double(r1)
  val (v3, r3) = double(r2)
  ((v1, v2, v3), r3)
}

6.4 ints

返回一个Int的列表，这种题目显然需要使用递归，感觉这好像是一个unfold操作，但既然书中没有对此进行进一步抽象，那我也就敬谢不敏了。

def ints(count: Int)(rng: RNG): (List[Int], RNG) =
  if (count == 0) (Nil, rng)
  else {
    val (v, r) = rng.nextInt
    val (last, s) = ints(count - 1)(r)
    (v :: last, s)
  }

6.5 使用map实现double

不难，用于熟悉抽象。

1 2	`val double$: Rand[Double] = map(nonNegativeInt)(_ / Int.MaxValue.toDouble)`

6.6 map2

实现map2，该操作（组合子）的形式非常熟悉。

def map2[A, B, C](a: Rand[A], b: Rand[B])(f: (A, B) => C): Rand[C] = rng => {
  val (v1, r1) = a(rng)
  val (v2, r2) = b(r1)
  (f(v1, v2), r2)
}

6.7 sequence

sequence就是将一连串的Rand按序执行，可以注意到这操作的形式和折叠很像。

def sequence[A](fs: List[Rand[A]]): Rand[List[A]] = rng => fs match {
  case Nil => (Nil, rng)
  case x :: xs => map2(x, sequence(xs))(_ :: _)(rng)
}

使用sequence实现ints也是简单的：

1 2	`def ints$(count: Int): Rand[List[Int]] = sequence(List.fill(count)(_.nextInt))`

6.8 flatMap

flatMap的实现就很有趣了，可以将flatMap理解为顺序的计算，先将当前的计算进行执行，再将计算后得到的状态传递给后一个计算。这样理解大概对一切monad都适用。

def flatMap[A, B](a: Rand[A])(f: A => Rand[B]): Rand[B] = rng => {
  val (v, r) = a(rng)
  f(v)(r)
}

6.9 使用flatMap实现map和map2

def map$[A, B](a: Rand[A])(f: A => B): Rand[B] = flatMap(a) { i => unit(f(i)) }

def map2$[A, B, C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] =
  flatMap(ra)(a => map(rb)(b => f(a, b))) // 或者 flatMap(ra)(a => flatMap(rb)(b => unit(f(a, b))))

6.10 泛化unit，map，map2，flatMap，sequence

将纯函数式状态（转移）抽象出来，并实现相应方法或函数：

final case class State[S, +A](run: S => (A, S)) {
  // map方法就是构造一个新的State，该State为当前State执行后对结果进行一个映射
  def map[B](f: A => B): State[S, B] = State { s =>
    val (r, nextS) = run(s)
    (f(r), nextS)
  }

  def map2[B, C](b: State[S, B])(f: (A, B) => C): State[S, C] = State { s =>
    val (r1, s1) = run(s)
    val (r2, s2) = b.run(s1)
    (f(r1, r2), s2)
  }

  // 先执行当前计算，将下一个值传给f，对生成的State执行计算
  def flatMap[B](f: A => State[S, B]): State[S, B] = State { s =>
    val (r1, s1) = run(s)
    f(r1).run(s1)
  }
}

case object State {
  def unit[S, A](a: A): State[S, A] = State((a, _))
  def sequence[S, A](a: List[State[S, A]]): State[S, List[A]] = a match {
    case Nil => State((Nil, _))
    case x :: xs => x.map2(sequence(xs))(_ :: _)
  }
}

6.11 实现一个简单的有穷状态自动机

这题虽然说着难，但是操作起来还是挺简单的，主要是要根据规则编写状态转移的函数。当编写完状态转移的函数后，便能够编写接受一连串命令的函数了（我看这个函数好像又是个折叠操作）：

sealed trait Input
case object Coin extends Input
case object Turn extends Input

case class Machine(locked: Boolean, coins: Int, candies: Int)
case object Machine {
  def operate(input: Input): State[Machine, (Int, Int)] = State { state =>
    def deconstruct(state: Machine): ((Int, Int), Machine) = ((state.coins, state.candies), state)
    // 有三个参数：Input，locked，candies <= 0?
    (input, state.locked, state.candies) match {
      case (input, _, candies) if candies <= 0 => input match {
        case Coin => deconstruct(state.copy(coins = state.coins + 1))
        case Turn => deconstruct(state)
      }
      case (Coin, _, _) => deconstruct(state.copy(locked = false, coins = state.coins + 1))
      case (Turn, false, candies) => deconstruct(state.copy(locked = true, candies = candies - 1))
      case (Turn, true, _) => deconstruct(state)
    }
  }

  def simulateMachine(input: List[Input]): State[Machine, (Int, Int)] = input match {
    case Nil => State.get[Machine].map(s => (s.coins, s.candies))
    case x :: xs => operate(x).flatMap(_ => simulateMachine(xs))
  }
}

暂且到此，感觉对学到的东西仍旧不太清晰，待之后学习完第二第三部分后整个回过头来再看一遍吧。

FP Scala

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 协议，转载请注明出处！

todo.txt 简明教程上一篇

关于 foldRight 为何能操作无穷列表下一篇

《Scala 函数式编程》解题笔记——第一部分