在函數(shù)式設(shè)計中册倒，遞歸是一種重要的思維婴谱。本文通過List的實現(xiàn)為例甜橱，闡述Scala在設(shè)計具有「不變性」數(shù)據(jù)結(jié)構(gòu)的思路和技巧。
遞歸的數(shù)據(jù)結(jié)構(gòu)
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等方法可以使用「模式匹配」的原因厨剪。
協(xié)變
List[+A]的類型參數(shù)是「協(xié)變」的。
-
Nothing是任何類的子類友存； -
List[Nothing]祷膳，或Nil也是List[A]的子類；
:結(jié)尾的方法
定義::的Cons操作屡立，其具有特殊的結(jié)合性直晨；
結(jié)合性
sealed abstract class List[+A] {
def ::[B >: A] (x: B): List[B] = new ::(x, this)
...
}
:結(jié)尾的方法，Scala具有特殊的結(jié)合性。
1 :: 2 :: 3 :: Nil // List(1, 2, 3)
等價于：
Nil.::(3).::(2).::(1) // List(1, 2, 3)
逆變點
參數(shù)x在List方法::中定義本來是一個「逆變點」勇皇，這與List[+A]的協(xié)變相矛盾罩句，為此通過提供類型「下界」，并保證其「不變性」敛摘，使得這兩個現(xiàn)象得以和諧门烂。
def ::[B >: A] (x: B): List[B] = new ::(x, this)
