queue函数式队列，三种操作方式的数据结构：
head
tail
append
函数式队列添加元素时不改变其内容，而是返回一个包含这个元素的新队列。
//基本的函数式队列
//队列在任何时刻的所有内容都可以表达为“leading ::: trailing.reverse”
//想要添加新的元素，只要使用::操作符把它cons到trailing，append是常量时间
//当原始的空队列通过后继的append操作构建起来时，trailing将不断增加，而leading始终是空白的。于是，在对空的leading第一次执行head或者tail操作之前，trailing应该被反转并复制给leading，这个操作称为mirror。
object Queues3 {
class Queue[T](
private val leading: List[T],
private val trailing: List[T]
) {
private def mirror =
if (leading.isEmpty)
new Queue(trailing.reverse, Nil)
else
this
def head = mirror.leading.head
def tail = {
val q = mirror
new Queue(q.leading.tail, q.trailing)
}
def append(x: T) =
new Queue(leading, x :: trailing)
override def toString =
leading ::: trailing.reverse mkString ("Queue(", ", ", ")")
}
object Queue {
// constructs a queue with initial elements `xs'
def apply[T](xs: T*) = new Queue[T](xs.toList, Nil)
}
def main(args: Array[String]) {
val q = Queue[Int]() append 1 append 2
println(q)
}
}
用两个List leading和trailing，leading包含前段元素，trailing包含了反向排列的后段元素
object Queues3 {
class Queue[T](
private val leading: List[T],
private val trailing: List[T]
) {
private def mirror =
if (leading.isEmpty)
new Queue(trailing.reverse, Nil)
else
this
def head = mirror.leading.head
def tail = {
val q = mirror
new Queue(q.leading.tail, q.trailing)
}
def append(x: T) =
new Queue(leading, x :: trailing)
override def toString =
leading ::: trailing.reverse mkString ("Queue(", ", ", ")")
}
object Queue {
// constructs a queue with initial elements `xs'
def apply[T](xs: T*) = new Queue[T](xs.toList, Nil)
}
def main(args: Array[String]) {
val q = Queue[Int]() append 1 append 2
println(q)
}
}
信息隐藏
私有构造器及工厂方法
使用私有类的方法可以更彻底的把类本身隐藏掉，仅提供能够暴露类公共接口的特质。
object Queues4 {
//通过私有化隐藏主构造器
class Queue[T] private (
private val leading: List[T],
private val trailing: List[T]
)
{
private def mirror =
if (leading.isEmpty) new Queue(trailing.reverse, Nil)
else this
def head =
mirror.leading.head
def tail = {
val q = mirror;
new Queue(q.leading.tail, q.trailing)
}
def append(x: T) =
new Queue(leading, x :: trailing)
override def toString() =
(leading ::: trailing.reverse) mkString ("Queue(", ", ", ")")
}
//伴生对象的apply工厂方法
object Queue {
// constructs a queue with initial elements `xs'
def apply[T](xs: T*) = new Queue[T](xs.toList, Nil)
}
def main(args: Array[String]) {
val q = Queue[Int]() append 1 append 2
println(q)
}
}
变化型注解
object Misc {
class Cell[T](init: T) {
private[this] var current = init
def get = current
def set(x: T) { current = x }
}
trait OutputChannel[-T] {
def write(x: T)
}
trait Function1[-S, +T] {
def apply(x: S): T
}
}
变化型注解
class Cell[T](init: T) {
private[this] var current = init
def get = current
def set(x: T) { current = x }
}
检查变化型注解
//创建指定元素类型为Int类型的队列子类，并重载append方法
class StrangeIntQueue extends Queue[Int] {
override def append(x: Int) = {
println(Math.sqrt(x))
super.append(x)
}
}
//StrangeIntQueue的append方法在执行本身的添加操作之前，首先打印输出它的（整数）参数的方根
val x: Queue[Any] = new StrangeIntQueue
x.append("abc")
下届
class Queue[+T] (private val leading: List[T],
private val trailing: List[T] ) {
def append[U >: T](x: U) =
new Queue[U](leading, x :: trailing)
}
逆变
object Misc {
class Cell[T](init: T) {
private[this] var current = init
def get = current
def set(x: T) { current = x }
}
//逆变的输出通道
trait OutputChannel[-T] {
def write(x: T)
}
//Functional的协变呵逆变
trait Function1[-S, +T] {
def apply(x: S): T
}
}
//函数类型参数变化型的演示
class Publication(val title: String)
class Book(title: String) extends Publication(title)
object Library {
val books: Set[Book] =
Set(
new Book("Programming in Scala"),
new Book("Walden")
)
def printBookList(info: Book => AnyRef) {
for (book <- books) println(info(book))
}
}
object Customer extends Application {
def getTitle(p: Publication): String = p.title
Library.printBookList(getTitle)
}
上界
//混入了Ordered特质的Person类
//第一个参数是一个比较函数，第二个是curry化参数，是待排序的列表
class Person(val firstName: String, val lastName: String)extends Ordered[Person] {
def compare(that: Person) = {
val lastNameComparison =
lastName.compareToIgnoreCase(that.lastName)
if (lastNameComparison != 0)
lastNameComparison
else
firstName.compareToIgnoreCase(that.firstName)
}
override def toString = firstName +" "+ lastName
}
val robert = new Person("Robert", "Jones")
//robert: Person = Robert Jones
val sally = new Person("Sally", "Smith")
//sally: Person = Sally Smith
robert < sally
//res30: Boolean = true
//带有上界的归并排序
def orderedMergeSort[T <: Ordered[T]](xs: List[T]): List[T] = {
def merge(xs: List[T], ys: List[T]): List[T] =
(xs, ys) match {
case (Nil, _) => ys
case (_, Nil) => xs
case (x :: xs1, y :: ys1) =>
if (x < y) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}
val n = xs.length / 2
if (n == 0) xs
else {
val (ys, zs) = xs splitAt n
merge(orderedMergeSort(ys), orderedMergeSort(zs))
}
}
网友评论