在Scala里,最常用的数据结构是列表,它是一种函数式的数据结构。
scala> val list = List(1,2,3,4)
list: List[Int] = List(1, 2, 3, 4)
scala> list.head
res1: Int = 1
scala> list.tail
res2: List[Int] = List(2, 3, 4)
对列表的任何操作不会影响本身的列表,列表一旦创建便不会发生改变,这会使得我们更好的推导数据的变化。作为一门Scalable的语言,Scala允许使用者也可以开发一个类似内置列表的数据结构。在这篇文章会简单的实现一个函数式双向队列,也以此来展示类型参数和如何做简单的信息隐藏。 Begin: 类型参数可以让我们编写泛型类和特质,例如列表就是泛型的,定义为List[T],它的实例可以为List[Int],List[String]等。作为双向队列的第一段代码输入:
class Deque[T]{
}
其中T可以是任何字母。现在Deque类还没有构造参数,再补充上:
class Deque[T](elems:List[T]){
}
为了简便实现,函数式双向队列采用了内置的列表,现在Deque类可以传入一个参数elems。加上第一个方法:
override def toString = elems match {
case List() => "Deque()"
case List(_*) => { val y = elems mkString ","
s"Deque($y)"}
}
这里使用了模式匹配,如果是空列表返回空,否则返回类似Deque(1,2,3)的文字。双向队列有四个基础方法popLeft,popRight,pushLeft,pushRight。(在这里暂时不考虑运行效率)
def popLeft: T = elems.head
def popRight: T = elems.last
def pushRight(x:T) = elems match {
case List() => new Deque(List(x))
case _ => new Deque(elems ::: List(x))
}
def pushLeft(x:T) = elems match {
case List() => new Deque(List(x))
case _ => new Deque(List(x) ::: elems)
}
将完整的Deque类输入到REPL:
scala> class Deque[T](elems:List[T]){
| override def toString = elems match {
| case List() => "Deque()"
| case List(_*) => { val y = elems mkString ","
| s"Deque($y)"}
| }
| def popLeft: T = elems.head
|
| def popRight: T = elems.last
|
| def pushRight(x:T) = elems match {
| case List() => new Deque(List(x))
| case _ => new Deque(elems ::: List(x))
| }
| def pushLeft(x:T) = elems match {
| case List() => new Deque(List(x))
| case _ => new Deque(List(x) ::: elems)
| }
| }
defined class Deque
现在的Deque长这样:
scala> val deque = new Deque(List(1,2,3,4))
deque: Deque[Int] = Deque(1,2,3,4)
scala> val deque2 = new Deque(List('a','b','c'))
deque: Deque[Char] = Deque(a,b,c)
原生的Scala数据结构是没有丑陋的new方法和指定List实例的,为了避免这个,还记得伴生对象吗?
object Deque {
def apply[T](xs:T*) = new Deque[T](xs.toList)
}
将这个对象和Deque类放在同一个源文件,而Deque()实际上Deque.apply()的语法糖,当使用Deque(1,2,3)构造双向队列时,调用的Deque对象的apply方法。现在再将这个输入REPL:(因为REPL每一行都是一个新的object,所以会warning)
scala> object Deque {
| def apply[T](xs:T*) = new Deque[T](xs.toList)
| }
defined module Deque
warning: previously defined class Deque is not a companion to object Deque.
Companions must be defined together; you may wish to use :paste mode for this.
scala> val deque = Deque(1,2,3,4)
deque: Deque[Int] = Deque(1,2,3,4)
scala> deque.popLeft
res0: Int = 1
scala> deque.popRight
res1: Int = 4
scala> deque.pushRight(5)
res2: Deque[Int] = Deque(1,2,3,4,5)
scala> deque.pushLeft(0)
res3: Deque[Int] = Deque(0,1,2,3,4)
看,借助了Scala强大的类型参数,现在这个函数式双向队列可以做到和原生列表一样的使用。