在函数式设计中，递归是一种重要的思维。本文通过List的实现为例，阐述Scala在设计具有「不变性」数据结构的思路和技巧。

递归的数据结构

sealed abstract class List[+A]

final case class ::[A](head: A, tail: List[A]) extends List[A]
final case object Nil extends List[Nothing]

递归的的算法

sealed abstract class List[+A] {
  ...
  
  def map[B](f: A => B): List[B] = this match {
    case Nil => Nil
    case h :: t => f(h) :: t.map(f)
  }

  def filter(f: A => Boolean): List[A] = this match {
    case Nil => Nil
    case h :: t => if(f(h)) h :: t.filter(f) else t.filter(f)
  }

  def foreach[U](f: A => U): Unit = this match {
    case Nil => ()
    case h :: t => { f(h); t.foreach(f) }
  }
  
  def forall(f: A => Boolean): Boolean = this match {
    case Nil => true
    case h :: t => f(h) && t.forall(f)
  }
  
  def exists(f: A => Boolean): Boolean = this match {
    case Nil => false
    case h :: t => f(h) || t.exists(f)
  }
}

最终类

不能在类定义的文件之外定义List的任何新的子类。List只有两个子类：

• case class ::[A]
• case object Nil

这使得List.map, filter, foreach等方法可以使用「模式匹配」的原因。

协变

List[+A]的类型参数是「协变」的。

• Nothing是任何类的子类；
• List[Nothing]，或Nil也是List[A]的子类；

:结尾的方法

定义::的Cons操作，其具有特殊的结合性；

结合性

sealed abstract class List[+A] {
  def ::[B >: A] (x: B): List[B] = new ::(x, this)
  ...
}

:结尾的方法，Scala具有特殊的结合性。

1 :: 2 :: 3 :: Nil      // List(1, 2, 3)

等价于：

Nil.::(3).::(2).::(1)  // List(1, 2, 3)

逆变点

参数x在List方法::中定义本来是一个「逆变点」，这与List[+A]的协变相矛盾，为此通过提供类型「下界」，并保证其「不变性」，使得这两个现象得以和谐。

def ::[B >: A] (x: B): List[B] = new ::(x, this)