Scala 函数式数据结构与递归的艺术

本章起的主要内容源自于 Paul Chiusano 所著的《Functional Programming in Scala》。笔者将以 Scala 的视角逐步地深入了解函数式编程部分，并且尝试着充分利用 Scala 提供的语言特性 —— 隐式转换，形变，高阶类型，模式匹配等内容。

有关于高阶函数，函数柯里化，纯函数，非纯函数，副作用等概念笔者曾在之前的 Scala 之：函数式编程之始介绍过，这里不再赘述。

Why FP

函数式编程 ( Functional Programming，简称 “FP” ) 构造在纯函数的基础之上，而纯函数隔绝了副作用。我们因此至少获得了最显著的好处：程序的运行环境不会影响到计算过程，因此也不会影响到计算结果。最简单的纯函数例子是数学的加 (+) 函数。比如给定一个 1 + 2 的表达式，它的运算结果永远是结果 3 。这个表达式不会有任何副作用，换句话说，代码中任何出现了 1 + 2 的式子，都可以简单地使用它的结果 3 代替。

引用透明与纯函数

上面的例子描述的是纯函数具备的引用透明 ( referential transparency ) 特性：一切对纯函数的调用都可以替换成它的计算结果。这种限制使得推导程序的求值结果变得更加简单而自然，我们称之为代换模型 ( substitution model )：推导计算结果就像简单地解数学题一样，不断地对参数进行等价代换，直到规约到最简单的格式。引用透明使得程序具备了等式推理的能力 ( equational reasoning ) 。这里再举出两个例子来说明：

第一个正例是 Java 和 Scala 中的字符串 String 。它是一种不可变的数据结构，所有的变换只会产生新的结果，而不会更改自身：

1
2
3

scala复制代码val x = "hello"
val r1 = x.reverse  // => "olleh"
val r2 = x.reverse  // => "olleh"

显然，无论在何处调用了 x.reverse ，这个结果永远保持不变。因此我们称 x.reverse 是一个引用透明的表达式，在任何调用了 x.reverse 的代码中，我们都可以使用其结果 olleh 替换之。

第二个反例是 java.lang.StringBuilder::append 方法。这个方法会改变 StringBuilder 自身，这意味着每调用一次 append 方法，它之前的状态就会被破坏：

1
2
3

scala复制代码val x = new StringBuilder("hello")
val r1 = x.append(",world")  //=> "hello,world"
val r2 = x.append(",world")  //=> "hello,world,world"

显然这个函数破坏了引用透明原则。r2 在调用 x.append(",world") 之前，原先的状态已经被 r1 的副作用改变了。虽然 r1 和 r2 都描述了同一个表达式，但是却得到了不同的结果，副作用使得程序行为的推理变得更加困难。

与之相对的就是代数模型更加容易推理，因为我们无需担心函数执行前后的环境变化。

模块化编程

FP 的另一个好处是让程序变得更加模块化。一个系统由多个模块所组成，这些模块应该可被独立出来理解，并支持复用的。在 FP 的世界中，一个系统的功能仅取决于这些模块本身的功能和组成顺序，而和其它的任何因素都没有关系。比如说，我们可以用 “加减乘除” 的任意组合表达出任意一个足够复杂的表达式。同样，函数之间可以相互组合 ( composite ) ，并最终形成功能强大的计算系统。

重返递归

笔者极力建议先阅读此篇文章：有趣的 Scala 语言 – 使用递归去思考。

大部分抽象逻辑都能够使用递归思维来简洁地表述。以快速排序为例子，只需要一小段描述就能够概括它：在序列中任选一个基准点并以此分出前后两个数组：前面是所有小于此基准点的元素，后面是所有大于此基准点的元素。为了让列表整体有序，继续深入到前后两个子序列中递归重复的过程，直到某一时刻选中的基准点前后没有再需要排序的子序列了。

多亏 Scala 提供的模式匹配，实现它只需要一行代码：

1
2
3

scala复制代码def quickSort(xs: List[Int]): List[Int] = {
    if (xs.isEmpty) Nil else quickSort(xs.filter(_ > xs.head) ::: xs.head :: xs.filter(_ < xs.head))
}

如果说命令式编程是使用 while 或者 for 循环细心地交代程序每一步都应该怎么做，那么函数式编程的递归只需要说清两件事：做什么，到什么时候为止 ( 边界条件 ) 。感兴趣的同学还可以去上述的文章翻阅 “零钱兑换问题”，并感受更复杂的问题是如何用递归巧妙解决的。

拥抱递归，似乎一切都会变得美好。但是这里有一个不可忽视的新问题：每调用一次函数，就需要新创建一个栈帧，对于深度的递归调用，这有栈空间溢出的风险。针对这个问题，笔者下面要引入尾调用和尾递归的相关概念：

尾调用与尾递归

假定有两个函数 f(·) 和 g(·)，如果函数 f(·) 最终仅返回对 g(·) 的调用而没有任何额外赋值或者计算操作，则称 f(·) 进行了尾调用。

scala复制代码def f(x: Int, acc : Int): Int = {
  // 允许有其它的操作
  // 尾调用
  g(x + 1, acc + 1)
}

def g(x: Int, acc: Int): Int = 3 * x + acc

下面的情况不能称之尾调用，因为 f(·) 调用 g(·) 之后还要进行一步赋值操作：

scala复制代码  def f(a : Int, acc : Int) : Int = {
    val result = g(a + 1,acc + 1)
    result
  }
  def g(x: Int, y: Int): Int = 3 * x + y

下面的情况同样不能称之尾调用，因为 f(·) 调用 g(·) 之后还需要后续的 + 1 计算：

1 2	scala复制代码 def k(a : Int, acc : Int) : Int = g(a + 1,acc + 1) + 1 def g(x: Int, y: Int): Int = 3 * x + y

如果 f(·) 以尾调用的方式进行了递归，则称 f(·) 是一个尾递归函数。下面的函数代表一个阶乘计算：

scala复制代码def f(a : Int,acc : Int) : Int = {
    if (a <= 1) acc
    else f(a-1,a * acc)
}

该函数要么返回值 acc 中断递归，要么就只返回对自身的一个新调用 f(a - 1,a * acc)。而下面的函数不能称为尾递归：

scala复制代码def f(a : Int) : Int = {
	if(a <= 1) 1
	else a * f(a -1)
}

这是阶乘函数的另外一种写法，而 f(a-1) 不再是尾部，因为它还要参与到另一个乘运算当中。

为何强调尾递归优化

假使 f(·) 对 g(·) 进行了尾调用，当解释器为 g(·) 创建新的栈帧时，就可以将原来的 f(·) 从栈中弹出，因为 f(·) 没有任何后续计算了。同样，若 g(·) 尾调用了函数 h(·) ，则运行 h(·) 时，g(·) 也可以从栈中弹出。很容易就能推导出来，由于这种 “边进边出” 的机制，尾递归的整个过程实际上只占用一个栈帧。

但如果 f(·) 并没有进行尾调用，那么就需要等待 g(·) 返回值之后再进行后续的计算，f(·) 才算执行完毕。因此程序将g(·) 引入栈时， f(·) 不可以从栈帧弹出。此 “只进不出” 的非尾递归的情况，解释器需要为此创建和递归次数等量的栈帧，这种情况下就存在 Stack overflow 的风险。

CSDN:尾递归与尾调用 | CSDN:函数式编程-尾递归与尾调用

Scala 对尾递归函数的处理

对于尾递归函数，Scala 编译器通常都会尝试着将它翻译成是等效的迭代循环，但并不会通知你是否尝试成功。Scala 提供一个用于函数上的注解：@tailrec ，它用于显式地检查该函数是否是尾递归函数。如果不是，则会直接提示编译错误。

对于使用 IntelliJ IDEA 的程序员，IDE 会使用符号标记出尾递归 ( 或尾调用) 函数，而非尾递归的函数则使用符号。

定义函数式数据结构

函数式数据结构，只能被纯函数操作，并且仅返回一个新的值，而不改变原来的状态，因此 FP 范式中所操作的数据结构天生就是不可变的。这一章，我们仿写 Scala 的 List —— 以直观方式了解最普遍存在的函数式数据结构，单向链表。

在 Scala 提供的原生 List 中，非空结点为 :: ( 我们后续去分析这个熟悉的操作符究竟是什么来头，以及为什么要这么命名 )，而空结点为 Nil 。不过，出于 “避嫌” 的目的，笔者在命名上有所区别。一个链表 Chain 可包含两种类型：非空的结点类型 Cons 和代表 “空结点” 的 Vain 类型。

1
2
3

scala复制代码sealed trait Chain[+A]
case object Vain extends Chain[Nothing]
case class Cons[+A](head: A, tail: Chain[A]) extends Chain[A]

除此之外，Chain 还内置了一个与之协变的类型参数 A ，这样继承于 Chain[Nothing] 的 “链表底类型” Vain 能够用在任何一个 Chain[A] 类型的链表中充当 “空结点” 的角色。表示 “空” 的结点需要有一个就够了，因此我们还将 Vain 设置为了单例对象。

Head 与 Tail

在以往的链表定义中，我们常常为每个结点都设置一个 “前一个结点” 或者是 “后一个结点”。但此处 Cons 的定义有所不同，head 代表当前链表的首元素，而 tail 则代表除了首元素剩下的部分。

在之前的认知中，链表是 “一环接一环” 的，而在此处变成了 “一层套一层” 。对于一切的链表操作，都可以拆分成对 head 的操作和剩余链表 tail 的递归操作，这样的定义方式和后续的各类转换器实现完美契合。

下面给出 head 和 tail 的方法，它们都是很容易被理解的模式匹配。我们这里以 “第三人称” 的视角对链表进行操作，因此后续所有的函数 ( 或者称之为 “方法” ) 全部定义到伴生对象中。

scala复制代码object Chain { 
    
def getHead[A](chain: Chain[A]): A = {
    chain match {
      case Vain => throw new NullPointerException("there's nothing in this chain.")
      case Cons(head, _) => head
    }
  }

  def getTail[A](chain: Chain[A]): Chain[A] = {
    chain match {
      case Vain => Vain  
      case Cons(_, tail) => tail
    }
  }
  //TODO ...   
}

为了能够方便地通过变参形式创建链表并使用，我们还需要在伴生对象中定义一个 apply 方法。根据链表的递归定义，其逻辑如下：

scala复制代码 //  非尾递归实现，但是不依赖其它函数
def apply[A](items: A*): Chain[A] = {
    if (items.isEmpty) Vain else Cons(items.head, apply(items.tail: _*))
}

每从 items 当中提取出一个参数，就构造出一个以它为首元素的子链表，然后递归装入剩下的参数，直到所有的参数都被链入这个链表中，并以 Vain 元素作为链表的结尾。它目前还不是尾递归函数，不过我们先不着急优化它。

尝试着创建并打印这个自定义的链表，观察它的构造。其中 _* 表示将一个 Seq[_] 内的元素提取出来并作为多个参数传入：

1 2	scala复制代码val chain: Chain[Int] = Chain(1 to 3: _*) println(chain) // Cons(1,Cons(2,Cons(3,Vain)))

通过打印结果能观察到，这个自定义链表是嵌套结构。对于至少有一个元素的链表，屏幕会打印 Cons(_,Vain) ，而对于空链表，则根据定义，屏幕只会打印一个 Vain 。

函数式数据结构中的数据共享

当数据不可变时，该如何实现对数据的删除，增加之类的功能？通过上述模式匹配的代码块可以发现，如果想要在一个已有的 xs 链表前面再添加元素1 ，这仅仅需要返回一个 Cons(1,xs) 。由于链表 Chain[A] 是不可变的，那我们不需要对原先的 xs 链表重新做一遍复制来避免对其修改和污染，而是放心地直接复用它，这种做法称之为数据共享。

同样，如果要返回 xs 的 tail 部分，我们仅需要借助模式匹配 Cons(_,tail) 返回链表 xs 除了首部以外的所有元素，而原始的 xs 链表不会受到任何影响。我们说函数式的数据结构是持久，可推理的，这意味着已存在的引用不会因为后续的操作而发生改变。

除了添加，删除等基本操作，在下文我们还将尝试着逐步去实现 Scala 原生 List 中提供的各种转换器功能。

折叠操作

我们先假设有一个 Chain[Int] 类型的链表，然后思考如何用递归的方式实现元素累加 sum 和累乘 product 操作，并最终仅返回一个 Int 型结果。

回顾笔者刚刚提到的：”对于一切的链表操作，都可以拆分成对 head 的操作和剩余链表 tail 的递归操作” 。实际上我们需要考虑的只有两件事：首先是对 head 的操作，然后对 tail 做递归即可；另一件事是当递归处于临界条件时的返回值。

scala复制代码// 对 Chain[Int] 链表的累加方法
def sum(ints: Chain[Int]): Int = {
    ints match {
        case Vain => 0
        case Cons(head, tail) => head + sum(tail)  // Can be generalized
    }
}

// 对 Chain[Int] 边表的累乘方法
def product(ints: Chain[Int]): Int = {
    ints match {
        case Vain => 1
        case Cons(head, tail) => head * product(tail) // Can be generalized
    }
}

很明显，这两个代码在结构上有高度的一致性，唯一的区别在于到达临界条件时的返回值，以及递归过程中对中间结果的累积方式 ( 笔者使用 Can be generalized 标注出的地方 ) 。

现在尝试着将它泛化成更加一般的 foldRight 右折叠方法：将累积操作 op 抽象成满足 (A,B)=>B 类型的函数。这里假设我们最后的累积结果是 B 类型，在每次的递归过程中，把所有的元素全部向右累积。

scala复制代码//更加泛化的高阶函数，非尾递归
 def foldRight[A,B](chain: Chain[A])(init: B)(op: (A, B) => B): B = {
   chain match {
     case Vain => init
     case Cons(head, tail) => op(head, foldRight(tail)(init)(op))
   }
 }

这里我们还对 foldRight 进行了两步柯里化操作，其目的是当我们分开传入 chain 和 init 时，Scala 编译器能够自动推导出 op 实际的类型。比如说：

1 2	scala复制代码val chain: Chain[Int] = Chain(1 to 3: _*) println(Chain.foldRight(chain)(0)(_+_))

这段程序将以 0 作为初始值，并不断地将链表内的元素向右边聚合，显然，这个结果应当是 6。

优化非尾递归函数的思路

不过，这依旧不令人满意，因为目前的递归并不是尾递归。原因在于每一步递归调用时都需要 “保存现场” ，直到下一个递归返回结果时才会继续计算，这导致了一连串的 “等待链”：

1 2	scala复制代码// 需要等待下一次递归的 foldRight(tail)(init)(op) 返回结果 case Cons(head,tail) => op(head,foldRight(tail)(init)(op))

它的效率并不高，原因是每一层递归除了展开 op 操作然后将 init “抛给” 下一个递归调用之外，它什么都没有做。直到递归已经展开到边界时，程序才开始使用 init 逐级返回运算结果。

那不妨在每次递归过程中，直接将 head 元素右规约到 init 并作为本次的运算结果，然后将它作为参数传入到下次递归调用。这样，每层递归不再需要相互等待运算结果，尾递归函数就构造出来了。或许可以这样理解：我们将运算过程从 “先后向传播再前向传播” 直接改造成了 “向后边传播边计算” 的过程。

scala复制代码def foldRight[A, B](chain: Chain[A], acc: B)(op: (A, B) => B): B = {
    chain match {
        case Vain => acc
        case Cons(head, tail) => foldRight(tail, op(head, acc))(op)
    }
}
//同理，可以实现左规约，所有的参数向左累积。
def foldLeft[A, B](chain: Chain[A], init: B)(op: (B, A) => B): B = {
    chain match {
        case Vain => init
        case Cons(head, tail) => foldLeft(tail, op(init, head))(op)
    }
}
//通过左规约实现的右规约。
def foldLeftByfR[A, B](chain: Chain[A], init: B)(op: (B, A) => B): B = {
    foldRight(reverse(chain), init)((a, b) => op(b, a))
}

现在，当右折叠达到递归条件时，将直接返回累积结果。这种将非尾递归转化为尾递归函数的套路可以推广开来，比如说实现倒置链表元素的 reverse 方法，以及基于此尾递归函数的 apply 方法。

scala复制代码def reverse[A](chain: Chain[A]): Chain[A] = {
    def loop(chain: Chain[A], acc: Chain[A]): Chain[A] = {
        chain match {
            case Vain => acc
            case Cons(head, tail) => loop(tail, Cons(head, acc))
        }
    }
    loop(chain, Vain)
}

// 只依赖尾递归的 reverse 的新 apply 方法。
def apply[A](items: A*)(implicit acc: Chain[A] = Vain): Chain[A] = {
    if (items.isEmpty) reverse(acc) else apply(items.tail: _*)(Cons(items.head, acc))
}

reverse 函数的思想是：”先装入的元素会排到后面” ( 想象一个空链表不断头插值的过程 )。此外，非尾递归都可以优化成一个 “套壳函数” 提供初始值，并尾调用另一个尾递归的形式。

不过对于 Scala 而言，我们还可以利用隐式参数简化这段代码。这本质上是省略了第一次调用 loop 函数时提供初始值的步骤，因此也就不再需要外部的一层 “套壳函数” 了。

scala复制代码def reverse[A](chain: Chain[A])(implicit acc : Chain[A] = Vain): Chain[A] = {
    chain match {
      case Vain => acc
      case Cons(head, tail) => reverse1(tail)(Cons(head, acc))
    }
  reverse(chain)
}

隐式参数的精髓在于 “隐藏” ：对于代码的调用者而言，隐式参数意味着他不需要主动提供一个初始值 ( 最好让他对此毫无感知 ) ，在某些场合下用起来非常合适。比如，一个定义在伴生对象的求链表长度 size 方法。作为代码的使用者，他很自然地认为这个方法入参只需要一个被计算长度的链表，而不是由自己再额外提供一个 “用于累积求链表长度的初始值 0”。

scala复制代码def size(chain: Chain[_],depth: Int): Int = {
  def loop(chain: Chain[_],depth : Int) : Int = {
    chain match {
      case Vain => depth
      case Cons(_, tail) => size(tail)(depth + 1)
    }
  }
  loop(chain,depth)
}
//一个不好的设计,初始值不需要也不应该由用户来提供。
Chain.size(chain,0)

除此之外，这需要对 Scala 的隐式值机制有足够的了解，避免隐式变量被上下文的隐式值 “覆盖” 而得到预期外的结果。下面以一个例子说明：

1 2	scala复制代码def f(i : Int)(implicit a : Int = 5) : Int = g(i) def g(int: Int)(implicit b : Int = 0): Int = int + b

如果调用函数 f(1) ，最终得到的结果将是 6 而非 1 。从结构上看，可以认为函数 f(·) 是函数 g(·) 的闭包。若函数 f(·) 的隐式变量 a 被赋值为 5 ，这会隐含地表达了 “f(·) 的作用域内所有 Int 类型的隐式值都应是 5“。因此，其作用域内的函数 g(·) 的隐式变量 b 的值也将默认取 5 ，而不是 0 ，除非以 g(i)(0) 的形式覆盖掉上下文环境中默认定义的隐式值。

从追加元素抽象到聚合列表

设有 Chain[Chain[A]] 类型的嵌套列表，设计一个 flat 函数将它 “展平” 成一个 Chain[A] 类型。以现有的函数来看，直接实现这个功能有点困难。我们可以分步骤来执行：

考虑如何实现尾部追加单个元素的 append 方法；
考虑如何实现合并两个链表的 concat 方法；
最终实现对嵌套链表的 flat 方法。

这三个方法的逻辑是递进关系：高级的方法可以借助低级的方法来便捷实现。

对于 append 方法有两种方式实现，第一种是重新复制一份原有的链表并在最后添加新元素 ( 因为不能修改原有的链表 )；第二种方法是调用两次尾递归函数 reverse：先将链表 “倒过来” ，头插入新元素，然后再将链表 “正过来”，思路很清晰，但是运行效率较低。笔者在这里选择的是前者：

scala复制代码def append[A](chain:Chain[A],last:A)(implicit acc : Chain[A] = Vain) : Chain[A] = {
    chain match {
        case Vain => Cons(last,acc)
        case Cons(head,tail) => append(tail,last)(Cons(head,acc))
    }
}

//  def append[A](chain: Chain[A], last: A): Chain[A] = reverse(Cons(last, reverse(chain)))

对于两个链表 ca 和 cb ，一个直观的想法是：只要利用 append 方法不断地将 cb 的首元素追加到 ca 的尾部 ( 实际上返回的是新的链表，而不是 ca 本身被改变了 )，最终就可以实现 concat 方法的效果了。

scala复制代码  def concat[A](ca: Chain[A], cb: Chain[A]): Chain[A] = {
      
    def concatTail(ca: Chain[A], cb: Chain[A]): Chain[A] = {
      cb match {
        // 当 cb 为空,则不需要合并，这时直接返回前者。
        case Vain => ca
        case Cons(head, tail) => concatTail(append(ca, head), tail)
      }
    }

    (ca, cb) match {
      case (Vain, nonVainB) => nonVainB
      case (nonVainA, Vain) => nonVainA
      case _ => concatTail(ca, cb)
    }
  }

至于 flat 方法，可以想象成它是一个特化的右 ( 左 ) 叠加过程：将 Chain[Chain[A]] 内部的多个 Chain[A] 以两两的形式通过 concat 方法规约，并最终达到将 Chain[Chain[_]] “降维” 到 Chain[A] 的目的。

1 2	scala复制代码//这里 Vain:Chain[A] 表示将单例对象 Vain 看作成 Chain[A] 的一个特殊实例 def flat[A](l: Chain[Chain[A]]): Chain[A] = foldRight(l, Vain: Chain[A])(concat)

这里涉及到了一个 Scala 的语法现象，为了编译器能够正确地推导出期望的 op 类型，此处我们将单例对象 Vain 特指为了 Chain[A] 的一个实例。否则，编译器将认为 op 应当是一个 (Chain[A],Vain.type) => Vain.type 类型而提示传入的 concat 是 “错误” 的函数类型。

一切均可从折叠方法中抽象

实际上，一切对链表的操作都可以视作是左折叠/右折叠的演化版本。下面是基于折叠操作或其它已有的尾递归函数实现的 map ，flatMap ，和 fiter 方法。

scala复制代码def map[A, B](chain: Chain[A])(a2b: A => B): Chain[B] = {
    //可以简写成:foldLeft(chain,Vain:Chain[B])((t,h) => Cons(a2b(h),t))
    val trans: (Chain[B], A) => Cons[B] = (chain, head) => Cons(a2b(head), chain)
    foldLeft(chain, Vain: Chain[B])(trans)
}

def filter[A](chain: Chain[A])(whether: A => Boolean): Chain[A] = {
    //可以简写成:foldLeft(chain,Vain:Chain[A])((chain,a) => if(whether(a)) Cons(a,chain) else chain)
    val trans: (Chain[A], A) => Chain[A] = (chain, a) => if (whether(a)) Cons(a, chain) else chain
    foldLeft(chain, Vain: Chain[A])(trans)
}

def flatMap[A](chain: Chain[A])(toChain: A => Chain[A]): Chain[A] = link(map(chain)(toChain))
//基于 flatMap 实现的过滤器 filter
def filterByFm[A](chain: Chain[A])(whether: A => Boolean): Chain[A] = {
    val trans: A => Chain[A] = (a: A) => if (whether(a)) Chain(a) else Vain
    flatMap(chain)(trans)
}

至此，我们所有实现的函数已经具备了下列的层次关系：

更加复杂的例子：匹配子序列

要求：给定一个长序列和一个短序列，它们同属于 Chain[A] 类型，要求判定短序列是否是长序列的子序列。

同样，我们先考虑 Chain[Int] 类型的情形，然后再考虑怎么给出泛化版本。你可以将它想象成是 “对齐游标卡尺” 的过程：首先对齐长短序列的一端，然后继续尝试对齐长短序列的剩下部分。如果失败了，那么就 “滑动” 到后面的序列中继续寻找长短序列开头对齐的部分，然后如此递归。

如果长序列的剩余长度已经比短序列还要短了，我们可以断言该短序列一定不是长序列的子序列。另外一个关键点是：在滑动的过程中，短序列一定不能被更改。下面用一段动画来表述这段逻辑：检查 064 是否是 37064 的子序列。

用代码描述这段逻辑则是：

scss复制代码def contains(long : Chain[Int],short : Chain[Int]): Boolean = {
    if(Chain.size(long) < Chain.size(short)) return false
    (long,short) match {
        case (Cons(lh,lt),Cons(sh,st)) if lh == sh =>
            if(compareLeft(lt,st)) true else contains(lt,short)
        case (Cons(_,lt),Cons(_,_)) => contains(lt,short)
        case _ => false
    }
}
def compareLeft(longLeft : Chain[Int],shortLeft: Chain[Int]) : Boolean = {
    (longLeft,shortLeft) match {
        case (Cons(lh,_),Cons(sLast,Vain)) if lh == sLast => true
        case (Cons(lh,lt),Cons(sh,st)) if lh == sh => compareLeft(lt,st)
        case _ => false
    }
}

在完成了 Chain[Int] 版本的子序列匹配之后，我们再去推广类型为 A 时的一般情形。显然，这里要求 A 是可比较的类型，否则我们就无法用 == 准确描述出 “相同，相等” 的概念。

因此这里使用了上下文界定的方式提供由 A => Ordered[A] 的一个适配器：

scala复制代码/**
  * 通过上下文界定将它改写成适配任何元素列表的子序列查找方法。
  *
  * @param long    长序列
  * @param short   短序列
  * @param adaptor 转换器
  * @tparam A 列表元素
  * @return 若在长序列中找到了满足条件的子序列，则返回 true 。
  */
def contains_generic[A](long: Chain[A], short: Chain[A])(implicit adaptor: A => Ordered[A]): Boolean = {
  if (Chain.size(long) < Chain.size(short)) return false
  (long, short) match {
    case (Cons(lh, lt), Cons(sh, st)) if lh == sh =>
      if (compareLeft_generic(lt, st)) true else contains_generic(lt, short)
    case (Cons(_, lt), Cons(_, _)) => contains_generic(lt, short)
    case _ => false
  }
}

def compareLeft_generic[A](longLeft: Chain[A], shortLeft: Chain[A])(implicit adaptor: A => Ordered[A]): Boolean = {
  (longLeft, shortLeft) match {
    case (Cons(lh, _), Cons(sLast, Vain)) if lh == sLast => true
    case (Cons(lh, lt), Cons(sh, st)) if lh == sh => compareLeft_generic(lt, st)
    case _ => false
  }
}

优雅的符号表示法

Scala 的 “开明之处” 是允许使用符号组合来作为标识符来提升代码的可读性，以至于用户有时认为你设计出了新一套 DSL 。在原生的 Scala List 列表中，空列表使用 Nil 表示，而非空列表则是 :: 符号。当我们使用 List(1,2,3) 构造出一个不可变列表时，它实际上是 ::(1,::(2,::(3,Nil))) 。

样例类作为中缀符号匹配的情形

这里还需引入 Scala 提供的另一个语法特性。对于样例类而言，如果它仅有两个参数，比如：

1	scala复制代码case class Operator(a : Int, b : Int)

那么当进行模式匹配时，它可以被当作是一个中缀运算符来处理：

1
2
3

scala复制代码case a Operator b => ... 
// 这是之前学过的对象匹配模式，两者等效。
case Operator(a,b) => ...

Scala 将非空列表命名为 :: 的 “良苦用心”，就是为了用户能以简明方式表述出对列表的复杂匹配。观察下面表达相同意思的四个匹配语句，显然第一行的可读性最强。

scala复制代码case 1 :: 2 :: Nil => ...
// case ::(1,::(2,Nil)) => ...
// case Cons(1,Cons(2,Vain)) => ...
// case 1 Cons 2 Cons Nil => ...

向右操作符

另一个特殊的机制是，Scala 将所有以冒号 : 为结尾的操作符视作是右操作符，它的意思是这个符号会绑定在右操作元上。比如说表达式 1 :: xs ，按照常规的 Scala 中缀表达式表示法来理解，这应当是 1.::(xs) 。但作为元素的 Int 类型并没有 :: 方法，这说不通。实际的情况是： :: 作为右操作符，这个式子表达的意义是 xs.::(1) 。

此外，在非模式匹配的场合，仍然能够以类似 1 :: 2 :: 3 :: Nil 的方式构造 List(1,2,3) ，这是因为 List 提供了同名 :: 方法：

1 2	scala复制代码// 返回以新元素为 head，以自身 (this) 为 tail 的新 :: 实例。 def ::[U>:T](x:U): List[U] = new Scala.::(x,this)

我们也不难理解为何当使用 :: 符号构造列表时，编译器要求最右侧一定是 List 类型了，因为该方法的 this 关键字总是指向一个 List 对象。

笔者这次以符号形式给出了Scala 原生 List 的另一个仿写版本，它是仅包含了 apply 方法以及所依赖的 reverse 方法的精简版本。同时，为了避免协变的类型 A 出现在逆变点上，笔者使用上界对其进行了等效替换 ( 详情见笔者之前介绍的 Scala：形变章节 )。

scala复制代码sealed trait Link[+A]{
  // 为了避免 ~>:(e,this) 在此处被误认为是递归函数，因此这个 new 关键字不能省略。
  def ~>:[O>:A](e : O) : Link[O] = { new ~>:(e,this)}  
  def reverse[O>:A]: Link[O] = {
    @tailrec
    def loop(left : Link[O], acc : Link[O]) :Link[O] = {
       left match {
         case Empty => acc
         case h~>:tail => loop(tail,h->:acc)
       }
    }
    loop(this,Empty)
  }
}
case object Empty extends Link[Nothing]
case class ~>:[+A](head : A, tail : Link[A]) extends Link[A]
object Link {
  def apply[A](a: A) : Link[A] = a~>:Empty
  def apply[A](as:A*)(implicit result : Link[A] = Empty) : Link[A] = {
    if(as.isEmpty)  result.reverse
    else apply(as.tail:_*)(as.head~>:result)
  }
}

现在，我们也可以用 ~> 符号构造出一个非空列表：

1
2
3

scala复制代码//先运算 2~>: Empty  = ~>:(2,Empty)
//然后运算 1~>:(~>:(2,Empty)) = ~>:(1,~>:(2,Empty))
1 ~>: 2 ~>: Empty

或者在模式匹配中直接用符号形式表述出匹配逻辑：

scala复制代码  1 ~>: 2 ~>: Empty match {
    case 1~>:Empty => println("has only one element: 1.")
    case 1~>:_ => println("starts with element: 1.")
  }

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有