Question

1. Iterable 特质的所有方法都是用抽象方法 iterator 来定义的，该抽象方法的作用是逐个交出集合的元素。从 Traversable 继承下来的 foreach 方法在 Iterable 中的定义就用到了 iterator ：

   
   xxxxxxxxxx
   def foreach[U](f: Elem => U): Unit={
     val it = iterator
     while (it.hasNext) f(it.next())
   }

   很多 Iterable 的子类都重写了这个在 Iterable 中的 foreach 的标准实现， 因为它们可以提供更高效的实现。

   注意： foreach 是 Traversable 中所有操作实现的基础，因此它的性能表现非常重要。

2. Iterable 还有两个方法返回迭代器： grouped 和 sliding 。 但是这两个迭代器并不返回单个元素， 而是原始集合的某个子序列。

   可以通过入参来指定这些子序列的最大长度。grouped 方法将元素进行分段， 而 sliding 交出的是对元素的一个滑动窗口。

   
   xxxxxxxxxx
   val xs = List(1, 2, 3, 4, 5)
   val g1 = xs grouped 3 // 迭代的结果为： List(1,2,3)， List(4,5)
   val g2 = xs sliding 3 // 迭代的结果为： List(1,2,3)， List(2，3,4)， List(3,4,5)

3. Iterable 特质还对 Traversable 特质添加了其它的一些方法， 这些方法只有在有迭代器存在的情况下才能得以高效的实现。

   Iterable 包含的操作：

   • 抽象方法：

     • xs.iterator ： 按照与 foreach 遍历元素的顺序交出 xs 中每个元素的迭代器。

   • 其它迭代器：

     • xs grouped size： 交出该集合固定大小片段的迭代器。
     • xs sliding size ：交出该集合固定大小滑动窗口的迭代器。

   • 子集合：

     • xs takeRight n ： 包含 xs 的后 n 个元素的集合。如果未定义顺序， 则为任意的 n 个元素。

       Traversable 定义的 xs take n 获取 xs 的前 n 个元素的集合。

     • xs dropRight n ： 集合移除 xs takeRight n 的部分。

   • 拉链：

     • xs zip ys ： 由 xs 和 ys 对应位置元素的元组组成的 Iterable 。
     • xs zipAll (ys， x，y) ： 由 xs 和 ys 对应位置元素的元组组成的 Iterable， 其中较短的序列用 x (如果 xs 较短) 或者 y (如果 ys 较短) 的元素值扩展到相同的元素。
     • xs.zipWithIndex ： 由 xs 中的元素及其下标的对偶组成的 Iterable 。

   • 比较：

     • xs sameElements ys ： 测试 xs 是否和 ys 包含相同顺序的相同元素。

4. 为什么要在 Iterable 之上增加一个 Traversable 特质？因为有时候 Traversable 提供的 foreach 要比 iterator 的性能更好。

   例如我们有以下的二叉树：

   
   xxxxxxxxxx
   sealed abstract class Tree
   case class Branch(left: Tree， right: Tree) extends Tree
   case class Node(elem: Int) extends Tree

   如果我们让 Tree 继承自 Traversable[Int]， 则我们可以这样定义一个 foreach 方法：

   
   xxxxxxxxxx
   sealed abstract class Tree extends Traversable[Int]{
     def foreach[U](f: Int => U) = this match{
       case Node(elem) => 
         f(elem)
       case Branch(left, right) => 
         left foreach f 
         right foreach f
     }
   }

   这种遍历方式非常高效， 时间复杂度为 $ O(N) $ ，其中 $ N $ 为叶子结点数量。

   如果我们让 Tree 继承自 Iterable[Int]， 则我们可以这样定义一个 iterator 方法：

   
   xxxxxxxxxx
   sealed abstract class Tree extends Iterable[Int]{
     def iterator: Iterator[Int] = this match{
       case Node(elem) => Iterator.single(elem)
       case Branch(left, right) => left.iterator ++ right.iterator
     }
   }

   表面上看起来这个实现并不复杂。 但是对于 ++ 的实现而言， 存在一个运行效率的问题： 像 left.iterator ++ right.iterator 这样拼接起来的迭代器， 每交出一个元素， 都需要多一层计算来判断是用哪个迭代器(left.iterator 还是 right.iterator )。 因此总体而言， 其计算复杂度为 $ O(N\log N) $ 。

5. Iterable 下面的三个特质 Seq、Set、Map 的共同特点是： 它们都实现了 PartialFunction 特质， 定义了相应的 apply 方法和 isDefinedAt 方法。 不过， 每种特质实现 PartialFunction 的方式各不相同。

   例如： 对于Seq 而言 apply 是位置下标， 元素下标从 0 开始；对于 Set， apply 是成员测试；对于 Map， apply 是选择指定key 的值。

   
   xxxxxxxxxx
   Seq(1,2,3)(0) // 返回 1
   Set(1,2,3)(0) // 返回 false
   Map(1-> "a", 0 -> "b")(0) // 返回 "a"