In [3]:
import java.io.FileReader
import java.io.BufferedReader
import java.io.File
class FileLineTraversable(file: File) extends Traversable[String] {
override def foreach[U](f: String => U): Unit = {
println("Opening file")
val input = new BufferedReader(new FileReader(file))
try {
var line = input.readLine
while (line != null) {
f(line)
line = input.readLine
}
println("Done iterating file")
} finally {
println("Closing file")
input.close()
}
}
}
上面定义了一个Traversable,它打开一个文件,遍历文件的每一行。
In [4]:
val x = new FileLineTraversable(new File("test.txt"))
In [5]:
// 遍历文件,并且遍历每一行,把行拆分成词,最后构造一个词的列表,结果是一个Traversable[String]
for {
line <- x
word <- line.split("\\s+")
} yield word
In [6]:
for {
line <- x.take(2)
word <- line.split("\\s+")
} yield word
FileLineTraversable调用了take方法抽取集合的前n个元素,这里“Done iterating file”没有打印。
这是因为Traversable类有一个在必要时高效停止foreach的手段,就是抛出scala.util.control.ControlThrowable。这是一种预分配的异常,JVM能够高效地抛出和捕获它。这样做法的缺点是take方法实际上会多取一个元素才抛出异常终止迭代。
由于foreach方法不支持高效的随机访问,所以其对很多算法都是次优的选择,我们可以通过Iterable的外部迭代器来解决。
In [7]:
val names = Iterable("Josh", "Jim")
val address = Iterable("123 Anyroad", "125 Anyroad")
val n = names.iterator
val a = address.iterator
In [8]:
while(n.hasNext && a.hasNext) {
println(n.next + " lives at " + a.next)
}
Scala提供了zip方法,用来把两个集合压缩成一个pair的集合
In [9]:
names.iterator zip address.iterator map {
case (n, a) => n+ " lives at " + a
} foreach println
当在可变集合上使用外部迭代器时候,可能迭代器不知道集合发生了变化
In [10]:
val x = collection.mutable.ArrayBuffer(1, 2, 3)
val i = x.iterator
In [11]:
x.remove(0, 3)
i.hasNext
In [12]:
i.next
上面remove移除了集合中的全部元素,由于迭代器是外部的,它不知道背后集合已经变化,hasNext方法返回了true,调用next方法时却抛出了异常。
In [13]:
// 该示例是通过滑动窗口计算元素和
val x = Seq(2, 1, 30, -2, 20, 1, 2, 0)
x.tails map(_.take(2)) filter(_.length > 1) map (_.sum) toList
滑动窗口是通过使用tails方法创建的,tails方法返回一个集合的tail迭代器。也就是说,tails产生的迭代器组的每个迭代器都比前一个迭代器少一个元素。此外,还可以使用Scala提供的sliding方法来代替tails:
In [15]:
x.sliding(2) map (_.sum) toList
In [1]:
// define a binary tree structure
sealed trait BinaryTree[+A]
case object NilTree extends BinaryTree[Nothing]
case class Branch[+A](value: A,
lhs: BinaryTree[A],
rhs: BinaryTree[A]) extends BinaryTree[A]
case class Leaf[+A] (value: A) extends BinaryTree[A]
In [5]:
// define algorithm to traverse the binary tree
import scala.collection.LinearSeq
import scala.annotation.tailrec
def traverse[A, U](t: BinaryTree[A])(f: A => U): Unit = {
@tailrec
def traverseHelper(current: BinaryTree[A],
next: LinearSeq[BinaryTree[A]]): Unit =
current match {
case Branch(value, lhs, rhs) =>
f(value)
traverseHelper(lhs, rhs +: next)
case Leaf(value) if !next.isEmpty =>
f(value)
traverseHelper(next.head, next.tail)
case Leaf(value) => f(value)
case NilTree if !next.isEmpty =>
traverseHelper(next.head, next.tail)
case NilTree => ()
}
traverseHelper(t, LinearSeq())
}
traverseHelper实现了遍历树的核心功能,该方法接受当前要遍历的树和下一个LinearSeq,其中包含之后要迭代的二叉树元素。模式匹配的规则是:
In [7]:
val atree = Branch(1, Leaf(2), Branch(3, Leaf(4), NilTree))
traverse(atree)(println)
当需要把一个普通递归的算法转化成尾递归或循环算法时,在堆(heap)上手工创建个栈(stack),然后用这个栈来完成实际功能是一种常见的做法。在使用函数式风格的尾递归算法时,LinearSeq是个恰当的选择。
In [8]:
val x = IndexedSeq(1, 2, 3)
x.updated(1, 5)
上面使用IndexedSeq对象定义的工厂方法创建IndexedSeq实例,默认情况下,这会创建一个不可变的Vector。IndexedSeq有个update方法,该方法接受一个下标和新值,返回用新值修改了下标位置上的值的新集合。
IndexedSeq用apply方法来根据下标取值,在Scala里,apply方法调用可以省略。
In [9]:
x.apply(2)
In [10]:
x(2)
Set集合类型代表一种其每个元素都是唯一的结合,至少对==方法来说是唯一。当需要测试一个集合是否包含某个元素或者要确保集合里没有重复元素的时候,Set是很好用的集合类型。
Scala支持三种类型的不可变和可变Set:TreeSet、HashSet和BitSet:
- TreeSet用红黑树实现,具有O(logn)的随机访问复杂度。要创建一个TreeSet,必须提供隐式的Ordering类型类,以便能执行小于和大于比较(因为查找元素时需要比较期望值大小)
- HashSet也是用树结构实现的集合。最大的区别是HashSet用元素的hash值决定把元素放在树的哪个节点上,这意味着hash值相同的元素会被放在相同的节点上。如果hash算法的碰撞几率很小,那么HashSet在查找时的性能一般优于TreeSet
- BitSet是用Long型值的序列实现的。BitSet只能保存整数。BitSet通过把其底层的Long值与欲保存的整数值对应的位置为true来保存整数。BitSet经常用来高效地在内存里跟踪和保存一大批标志位
In [11]:
val errorcodes = Map(1 -> "O NOES", 2 -> "KTHXBAI", 3 -> "ZOMG")
In [12]:
errorcodes(1)
In [13]:
// Map能用做从键类型到值类型的偏函数
List(1, 3) map errorcodes
Scala还提供了当键不存在时返回默认值的能力
In [14]:
val errorcodes = Map(1 -> "O NOES", 2 -> "KTHXBAI", 3 -> "ZOMG").withDefaultValue("Error key")
In [15]:
errorcodes(4)