Further extension with LazyList

Demonstrates how to integrate lazy non-view collections
in the framework.

2 files changed, 562 insertions, 105 deletions

diff --git a/tests/run/colltest6/CollectionStrawMan6_1.scala b/tests/run/colltest6/CollectionStrawMan6_1.scala
index 2596d2a4a..b5776433e 100644
--- a/tests/run/colltest6/CollectionStrawMan6_1.scala
+++ b/tests/run/colltest6/CollectionStrawMan6_1.scala
@@ -8,9 +8,11 @@ import annotation.tailrec
 class LowPriority {
   import CollectionStrawMan6._
 
-  implicit def arrayToView[T](xs: Array[T]): ArrayView[T] =
-    new ArrayView[T](xs)
+  /** Convert array to iterable via view. Lower priority than ArrayOps */
+  implicit def arrayToView[T](xs: Array[T]): ArrayView[T] = new ArrayView[T](xs)
 
+  /** Convert string to iterable via view. Lower priority than StringOps */
+  implicit def stringToView(s: String): StringView = new StringView(s)
 }
 
 /** A strawman architecture for new collections. It contains some
@@ -21,9 +23,74 @@ class LowPriority {
  *
  *  For a test file, see tests/run/CollectionTests.scala.
  *
- *  Strawman6 is like strawman5, and adds arrays and some utilitity methods
- *  (tail, mkString). TODO: Generalize Builders.
+ *  Strawman6 is like strawman5, and adds lazy lists (i.e. lazie streams), arrays
+ *  and some utilitity methods (take, tail, mkString, toArray). Also, systematically
+ *  uses builders for all strict collections.
  *
+ *  Types covered in this strawman:
+ *
+ *  1. Collection base types:
+ *
+ *         IterableOnce, Iterable, Seq, LinearSeq, View, IndexedView
+ *
+ *  2. Collection creator base types:
+ *
+ *         FromIterable, IterableFactory, Buildable, Builder
+ *
+ *  3. Types that bundle operations:
+ *
+ *         IterableOps, IterableMonoTransforms, IterablePolyTransforms, IterableLike
+ *         SeqMonoTransforms, SeqLike
+ *
+ *  4. Concrete collection types:
+ *
+ *         List, LazyList, ListBuffer, ArrayBuffer, ArrayBufferView, StringView, ArrayView
+ *
+ *  5. Decorators for existing types
+ *
+ *         StringOps, ArrayOps
+ *
+ *  6. Related non collection types:
+ *
+ *         Iterator, StringBuilder
+ *
+ *  Operations covered in this strawman:
+ *
+ *   1. Abstract operations, or expected to be overridden:
+ *
+ *      For iterables:
+ *
+ *         iterator, fromIterable, fromLikeIterable, knownLength, className
+ *
+ *      For sequences:
+ *
+ *         apply, length
+ *
+ *      For buildables:
+ *
+ *         newBuilder
+ *
+ *      For builders:
+ *
+ *         +=, result
+ *
+ *   2. Utility methods, might be overridden for performance:
+ *
+ *      Operations returning not necessarily a collection:
+ *
+ *         foreach, foldLeft, foldRight, indexWhere, isEmpty, head, size, mkString
+ *
+ *      Operations returning a collection of a fixed type constructor:
+ *
+ *         view, to, toArray, copyToArray
+ *
+ *      Type-preserving generic transforms:
+ *
+ *         filter, partition, take, drop, tail, reverse
+ *
+ *      Generic transforms returning collections of different element types:
+ *
+ *         map, flatMap, ++, zip
  */
 object CollectionStrawMan6 extends LowPriority {
 
@@ -47,13 +114,21 @@ object CollectionStrawMan6 extends LowPriority {
 
   /** Base trait for generic collections */
   trait Iterable[+A] extends IterableOnce[A] with IterableLike[A, Iterable] {
+
+    /** The collection itself */
     protected def coll: Iterable[A] = this
+
+    /** The length of this collection, if it can be cheaply computed, -1 otherwise. */
     def knownLength: Int = -1
-    def size: Int =
-      if (knownLength >= 0) knownLength
-      else foldLeft(0)((len, x) => len + 1)
+
+    /** The class name of this collection. To be used for converting to string.
+     *  Collections generally print like this:
+     *
+     *       <className>(elem_1, ..., elem_n)
+     */
     def className = getClass.getName
-    override def toString = this.mkString(className ++ "(", ", ", ")")
+
+    override def toString = s"$className(${mkString(", ")})"
   }
 
   /** Base trait for sequence collections */
@@ -62,27 +137,75 @@ object CollectionStrawMan6 extends LowPriority {
     def length: Int
   }
 
-  /** Base trait for strict collections */
-  trait Buildable[+A, +To <: Iterable[A]] extends Iterable[A] {
-    protected[this] def newBuilder: Builder[A, To]
-    override def partition(p: A => Boolean): (To, To) = {
+  /** Base trait for linearly accessed sequences */
+  trait LinearSeq[+A] extends Seq[A] { self =>
+
+    def iterator = new Iterator[A] {
+      private[this] var current: Seq[A] = self
+      def hasNext = !current.isEmpty
+      def next = { val r = current.head; current = current.tail; r }
+    }
+
+    def apply(i: Int): A = {
+      require(!isEmpty)
+      if (i == 0) head else tail.apply(i - 1)
+    }
+
+    def length: Int = if (isEmpty) 0 else 1 + tail.length
+
+    /** Optimized version of `drop` that avoids copying */
+    final override def drop(n: Int) = {
+      var current: Seq[A] = this
+      var i = n
+      while (i > 0) {
+        current = current.tail
+        i -= 1
+      }
+      current
+    }
+  }
+
+  /** Base trait for strict collections that can be built using a builder.
+   *  @param  A    the element type of the collection
+   *  @param Repr  the type of the underlying collection
+   */
+  trait Buildable[+A, +Repr] extends Any with IterableMonoTransforms[A, Repr]  {
+
+    /** Creates a new builder. */
+    protected[this] def newBuilder: Builder[A, Repr]
+
+    /** Optimized, push-based version of `partition`. */
+    override def partition(p: A => Boolean): (Repr, Repr) = {
       val l, r = newBuilder
-      iterator.foreach(x => (if (p(x)) l else r) += x)
+      coll.iterator.foreach(x => (if (p(x)) l else r) += x)
       (l.result, r.result)
     }
+
     // one might also override other transforms here to avoid generating
     // iterators if it helps efficiency.
   }
 
   /** Base trait for collection builders */
-  trait Builder[-A, +To] {
+  trait Builder[-A, +To] { self =>
+
+    /** Append an element */
     def +=(x: A): this.type
+
+    /** Result collection consisting of all elements appended so far. */
     def result: To
 
+    /** Bulk append. Can be overridden if specialized implementations are available. */
     def ++=(xs: IterableOnce[A]): this.type = {
       xs.iterator.foreach(+=)
       this
     }
+
+    /** A builder resulting from this builder my mapping the result using `f`. */
+    def mapResult[NewTo](f: To => NewTo) = new Builder[A, NewTo] {
+      def +=(x: A): this.type = { self += x; this }
+      override def ++=(xs: IterableOnce[A]): this.type = { self ++= xs; this }
+      def result: NewTo = f(self.result)
+    }
   }
 
   /* ------------ Operations ----------------------------------- */
@@ -103,98 +226,181 @@ object CollectionStrawMan6 extends LowPriority {
        with IterableOps[A]
        with IterableMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote
        with IterablePolyTransforms[A, C] {
+
+    /** Create a collection of type `C[A]` from the elements of `coll`, which has
+     *  the same element type as this collection.
+     */
     protected[this] def fromLikeIterable(coll: Iterable[A]): C[A] = fromIterable(coll)
   }
 
   /** Base trait for Seq operations */
   trait SeqLike[+A, +C[X] <: Seq[X]]
-  extends IterableLike[A, C] with SeqMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote
+  extends IterableLike[A, C]
+     with SeqMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote
 
+  /** Operations over iterables. No operation defined here is generic in the
+   *  type of the underlying collection.
+   */
   trait IterableOps[+A] extends Any {
-    def iterator: Iterator[A]
+    protected def coll: Iterable[A]
+    private def iterator = coll.iterator
+
+    /** Apply `f` to each element for tis side effects */
     def foreach(f: A => Unit): Unit = iterator.foreach(f)
+
+    /** Fold left */
     def foldLeft[B](z: B)(op: (B, A) => B): B = iterator.foldLeft(z)(op)
+
+    /** Fold right */
     def foldRight[B](z: B)(op: (A, B) => B): B = iterator.foldRight(z)(op)
+
+    /** The index of the first element in this collection for which `p` holds. */
     def indexWhere(p: A => Boolean): Int = iterator.indexWhere(p)
+
+    /** Is the collection empty? */
     def isEmpty: Boolean = !iterator.hasNext
-    def head: A = iterator.next
+
+    /** The first element of the collection. */
+    def head: A = iterator.next()
+
+    /** The number of elements in this collection. */
+    def size: Int =
+      if (coll.knownLength >= 0) coll.knownLength else foldLeft(0)((len, x) => len + 1)
+
+    /** A view representing the elements of this collection. */
     def view: View[A] = View.fromIterator(iterator)
-    def mkString(lead: String, sep: String, follow: String): String = {
+
+    /** A string showing all elements of this collection, separated by string `sep`. */
+    def mkString(sep: String): String = {
       var first: Boolean = true
-      val b = new StringBuilder(lead)
+      val b = new StringBuilder()
       foreach { elem =>
-        if (!first) b.append(sep)
+        if (!first) b ++= sep
         first = false
-        b.append(elem)
+        b ++= String.valueOf(elem)
       }
-      b.append(follow).toString
+      b.result
+    }
+
+    /** Given a collection factory `fi` for collections of type constructor `C`,
+     *  convert this collection to one of type `C[A]`. Example uses:
+     *
+     *      xs.to(List)
+     *      xs.to(ArrayBuffer)
+     */
+    def to[C[X] <: Iterable[X]](fi: FromIterable[C]): C[A @uncheckedVariance] =
+      // variance seems sound because `to` could just as well have been added
+      // as a decorator. We should investigate this further to be sure.
+      fi.fromIterable(coll)
+
+    /** Convert collection to array. */
+    def toArray[B >: A: ClassTag]: Array[B] =
+      if (coll.knownLength >= 0) copyToArray(new Array[B](coll.knownLength), 0)
+      else ArrayBuffer.fromIterable(coll).toArray[B]
+
+    /** Copy all elements of this collection to array `xs`, starting at `start`. */
+    def copyToArray[B >: A](xs: Array[B], start: Int = 0): xs.type = {
+      var i = start
+      val it = iterator
+      while (it.hasNext) {
+        xs(i) = it.next()
+        i += 1
+      }
+      xs
     }
   }
 
+  /** Type-preserving transforms over iterables.
+   *  Operations defined here return in their result iterables of the same type
+   *  as the one they are invoked on.
+   */
   trait IterableMonoTransforms[+A, +Repr] extends Any {
     protected def coll: Iterable[A]
     protected[this] def fromLikeIterable(coll: Iterable[A]): Repr
+
+    /** All elements satisfying predicate `p` */
     def filter(p: A => Boolean): Repr = fromLikeIterable(View.Filter(coll, p))
+
+    /** A pair of, first, all elements that satisfy prediacte `p` and, second,
+     *  all elements that do not. Interesting because it splits a collection in two.
+     *
+     *  The default implementation provided here needs to traverse the collection twice.
+     *  Strict collections have an overridden version of `partition` in `Buildable`,
+     *  which requires only a single traversal.
+     */
     def partition(p: A => Boolean): (Repr, Repr) = {
       val pn = View.Partition(coll, p)
       (fromLikeIterable(pn.left), fromLikeIterable(pn.right))
     }
+
+    /** A collection containing the first `n` elements of this collection. */
+    def take(n: Int): Repr = fromLikeIterable(View.Take(coll, n))
+
+    /** The rest of the collection without its `n` first elements. For
+     *  linear, immutable collections this should avoid making a copy.
+     */
     def drop(n: Int): Repr = fromLikeIterable(View.Drop(coll, n))
+
+    /** The rest of the collection without its first element. */
     def tail: Repr = drop(1)
-    def to[C[X] <: Iterable[X]](fi: FromIterable[C]): C[A @uncheckedVariance] =
-      // variance seems sound because `to` could just as well have been added
-      // as a decorator. We should investigate this further to be sure.
-      fi.fromIterable(coll)
   }
 
+  /** Transforms over iterables that can return collections of different element types.
+   */
   trait IterablePolyTransforms[+A, +C[A]] extends Any {
     protected def coll: Iterable[A]
     def fromIterable[B](coll: Iterable[B]): C[B]
+
+    /** Map */
     def map[B](f: A => B): C[B] = fromIterable(View.Map(coll, f))
+
+    /** Flatmap */
     def flatMap[B](f: A => IterableOnce[B]): C[B] = fromIterable(View.FlatMap(coll, f))
+
+    /** Concatenation */
     def ++[B >: A](xs: IterableOnce[B]): C[B] = fromIterable(View.Concat(coll, xs))
+
+    /** Zip. Interesting because it requires to align to source collections. */
     def zip[B](xs: IterableOnce[B]): C[(A @uncheckedVariance, B)] = fromIterable(View.Zip(coll, xs))
        // sound bcs of VarianceNote
   }
 
+  /** Type-preserving transforms over sequences. */
   trait SeqMonoTransforms[+A, +Repr] extends Any with IterableMonoTransforms[A, Repr] {
-    def reverse: Repr = {
-      var xs: List[A] = Nil
-      var it = coll.iterator
-      while (it.hasNext) xs = new Cons(it.next, xs)
-      fromLikeIterable(xs)
+    def reverse: Repr = coll.view match {
+      case v: IndexedView[A] => fromLikeIterable(v.reverse)
+      case _ =>
+        var xs: List[A] = Nil
+        var it = coll.iterator
+        while (it.hasNext) xs = new Cons(it.next(), xs)
+        fromLikeIterable(xs)
     }
   }
 
   /* --------- Concrete collection types ------------------------------- */
 
   /** Concrete collection type: List */
-  sealed trait List[+A] extends Seq[A] with SeqLike[A, List] with Buildable[A, List[A]] { self =>
+  sealed trait List[+A] extends LinearSeq[A] with SeqLike[A, List] with Buildable[A, List[A]] { self =>
+
     def isEmpty: Boolean
     def head: A
     def tail: List[A]
-    def iterator = new Iterator[A] {
-      private[this] var current = self
-      def hasNext = !current.isEmpty
-      def next = { val r = current.head; current = current.tail; r }
-    }
+
     def fromIterable[B](c: Iterable[B]): List[B] = List.fromIterable(c)
-    def apply(i: Int): A = {
-      require(!isEmpty)
-      if (i == 0) head else tail.apply(i - 1)
-    }
-    def length: Int =
-      if (isEmpty) 0 else 1 + tail.length
-    protected[this] def newBuilder = new ListBuffer[A]
+
+    protected[this] def newBuilder = new ListBuffer[A].mapResult(_.toList)
+
+    /** Prepend operation that avoids copying this list */
     def ++:[B >: A](prefix: List[B]): List[B] =
       if (prefix.isEmpty) this
       else Cons(prefix.head, prefix.tail ++: this)
+
+    /** When concatenating with another list `xs`, avoid copying `xs` */
     override def ++[B >: A](xs: IterableOnce[B]): List[B] = xs match {
       case xs: List[B] => this ++: xs
       case _ => super.++(xs)
     }
-    @tailrec final override def drop(n: Int) =
-      if (n > 0) tail.drop(n - 1) else this
+
     override def className = "List"
   }
 
@@ -214,29 +420,43 @@ object CollectionStrawMan6 extends LowPriority {
   object List extends IterableFactory[List] {
     def fromIterable[B](coll: Iterable[B]): List[B] = coll match {
       case coll: List[B] => coll
-      case _ => ListBuffer.fromIterable(coll).result
+      case _ => ListBuffer.fromIterable(coll).toList
     }
   }
 
   /** Concrete collection type: ListBuffer */
-  class ListBuffer[A] extends Seq[A] with SeqLike[A, ListBuffer] with Builder[A, List[A]] {
+  class ListBuffer[A]
+  extends Seq[A]
+     with SeqLike[A, ListBuffer]
+     with Buildable[A, ListBuffer[A]]
+     with Builder[A, ListBuffer[A]] {
+
     private var first, last: List[A] = Nil
     private var aliased = false
+
     def iterator = first.iterator
+
     def fromIterable[B](coll: Iterable[B]) = ListBuffer.fromIterable(coll)
+
     def apply(i: Int) = first.apply(i)
+
     def length = first.length
 
+    protected[this] def newBuilder = new ListBuffer[A]
+
     private def copyElems(): Unit = {
       val buf = ListBuffer.fromIterable(result)
       first = buf.first
       last = buf.last
       aliased = false
     }
-    def result = {
+
+    /** Convert to list; avoids copying where possible. */
+    def toList = {
       aliased = true
       first
     }
+
     def +=(elem: A) = {
       if (aliased) copyElems()
       val last1 = Cons(elem, Nil)
@@ -247,6 +467,9 @@ object CollectionStrawMan6 extends LowPriority {
       last = last1
       this
     }
+
+    def result = this
+
     override def className = "ListBuffer"
   }
 
@@ -256,18 +479,31 @@ object CollectionStrawMan6 extends LowPriority {
 
   /** Concrete collection type: ArrayBuffer */
   class ArrayBuffer[A] private (initElems: Array[AnyRef], initLength: Int)
-  extends Seq[A] with SeqLike[A, ArrayBuffer] with Builder[A, ArrayBuffer[A]] {
+  extends Seq[A]
+     with SeqLike[A, ArrayBuffer]
+     with Buildable[A, ArrayBuffer[A]]
+     with Builder[A, ArrayBuffer[A]] {
+
     def this() = this(new Array[AnyRef](16), 0)
+
     private var elems: Array[AnyRef] = initElems
     private var start = 0
     private var end = initLength
+
     def apply(n: Int) = elems(start + n).asInstanceOf[A]
+
     def length = end - start
     override def knownLength = length
+
     override def view = new ArrayBufferView(elems, start, end)
+
     def iterator = view.iterator
+
     def fromIterable[B](it: Iterable[B]): ArrayBuffer[B] =
       ArrayBuffer.fromIterable(it)
+
+    protected[this] def newBuilder = new ArrayBuffer[A]
+
     def +=(elem: A): this.type = {
       if (end == elems.length) {
         if (start > 0) {
@@ -285,8 +521,13 @@ object CollectionStrawMan6 extends LowPriority {
       end += 1
       this
     }
+
     def result = this
+
+    /** New operation: destructively drop elements at start of buffer. */
     def trimStart(n: Int): Unit = start += (n max 0)
+
+    /** Overridden to use array copying for efficiency where possible. */
     override def ++[B >: A](xs: IterableOnce[B]): ArrayBuffer[B] = xs match {
       case xs: ArrayBuffer[B] =>
         val elems = new Array[AnyRef](length + xs.length)
@@ -296,10 +537,18 @@ object CollectionStrawMan6 extends LowPriority {
       case _ => super.++(xs)
     }
 
+    override def take(n: Int) = {
+      val elems = new Array[AnyRef](n min length)
+      Array.copy(this.elems, this.start, elems, 0, elems.length)
+      new ArrayBuffer(elems, elems.length)
+    }
+
     override def className = "ArrayBuffer"
   }
 
   object ArrayBuffer extends IterableFactory[ArrayBuffer] {
+
+    /** Avoid reallocation of buffer if length is known. */
     def fromIterable[B](coll: Iterable[B]): ArrayBuffer[B] =
       if (coll.knownLength >= 0) {
         val elems = new Array[AnyRef](coll.knownLength)
@@ -315,98 +564,173 @@ object CollectionStrawMan6 extends LowPriority {
       }
   }
 
-  class ArrayBufferView[A](val elems: Array[AnyRef], val start: Int, val end: Int) extends RandomAccessView[A] {
+  class ArrayBufferView[A](val elems: Array[AnyRef], val start: Int, val end: Int) extends IndexedView[A] {
     def apply(n: Int) = elems(start + n).asInstanceOf[A]
     override def className = "ArrayBufferView"
   }
 
-  /** Concrete collection type: String */
+  class LazyList[+A](expr: () => LazyList.Evaluated[A])
+  extends LinearSeq[A] with SeqLike[A, LazyList] { self =>
+    private[this] var evaluated = false
+    private[this] var result: LazyList.Evaluated[A] = _
+
+    def force: LazyList.Evaluated[A] = {
+      if (!evaluated) {
+        result = expr()
+        evaluated = true
+      }
+      result
+    }
+
+    override def isEmpty = force.isEmpty
+    override def head = force.get._1
+    override def tail = force.get._2
+
+    def #:: [B >: A](elem: => B): LazyList[B] = new LazyList(() => Some((elem, self)))
+
+    def fromIterable[B](c: Iterable[B]): LazyList[B] = LazyList.fromIterable(c)
+
+    override def className = "LazyList"
+
+    override def toString =
+      if (evaluated)
+        result match {
+          case None => "Empty"
+          case Some((hd, tl)) => s"$hd #:: $tl"
+        }
+      else "?"
+  }
+
+  object LazyList extends IterableFactory[LazyList] {
+
+    type Evaluated[+A] = Option[(A, LazyList[A])]
+
+    def fromIterable[B](coll: Iterable[B]): LazyList[B] = coll match {
+      case coll: LazyList[B] => coll
+      case _ => new LazyList(() => if (coll.isEmpty) None else Some((coll.head, fromIterable(coll.tail))))
+    }
+
+    object Empty extends LazyList[Nothing](() => None)
+
+    object #:: {
+      def unapply[A](s: LazyList[A]): Evaluated[A] = s.force
+    }
+  }
+
+  // ------------------ Decorators to add collection ops to existing types -----------------------
+
+  /** Decorator to add collection operations to strings.
+   */
   implicit class StringOps(val s: String)
   extends AnyVal with IterableOps[Char]
      with SeqMonoTransforms[Char, String]
-     with IterablePolyTransforms[Char, List] {
+     with IterablePolyTransforms[Char, List]
+     with Buildable[Char, String] {
+
     protected def coll = new StringView(s)
     def iterator = coll.iterator
+
     protected def fromLikeIterable(coll: Iterable[Char]): String = {
       val sb = new StringBuilder
-      for (ch <- coll) sb.append(ch)
-      sb.toString
+      for (ch <- coll) sb += ch
+      sb.result
     }
+
     def fromIterable[B](coll: Iterable[B]): List[B] = List.fromIterable(coll)
+
+    protected[this] def newBuilder = new StringBuilder
+
+    /** Overloaded version of `map` that gives back a string, where the inherited
+     *  version gives back a sequence.
+     */
     def map(f: Char => Char): String = {
       val sb = new StringBuilder
-      for (ch <- s) sb.append(f(ch))
-      sb.toString
+      for (ch <- s) sb += f(ch)
+      sb.result
     }
+
+    /** Overloaded version of `flatMap` that gives back a string, where the inherited
+     *  version gives back a sequence.
+     */
     def flatMap(f: Char => String): String = {
       val sb = new StringBuilder
-      for (ch <- s) sb.append(f(ch))
-      sb.toString
+      for (ch <- s) sb ++= f(ch)
+      sb.result
     }
+
+    /** Overloaded version of `++` that gives back a string, where the inherited
+     *  version gives back a sequence.
+     */
     def ++(xs: IterableOnce[Char]): String = {
-      val sb = new StringBuilder(s)
-      for (ch <- xs.iterator) sb.append(ch)
-      sb.toString
+      val sb = new StringBuilder() ++= s
+      for (ch <- xs.iterator) sb += ch
+      sb.result
     }
+
+    /** Another overloaded version of `++`. */
     def ++(xs: String): String = s + xs
   }
 
-  case class StringView(s: String) extends RandomAccessView[Char] {
+  class StringBuilder extends Builder[Char, String] {
+    private val sb = new java.lang.StringBuilder
+
+    def += (x: Char) = { sb.append(x); this }
+
+    /** Overloaded version of `++=` that takes a string */
+    def ++= (s: String) = { sb.append(s); this }
+
+    def result = sb.toString
+
+    override def toString = result
+  }
+
+  case class StringView(s: String) extends IndexedView[Char] {
     val start = 0
     val end = s.length
     def apply(n: Int) = s.charAt(n)
     override def className = "StringView"
   }
 
+  /** Decorator to add collection operations to arrays.
+   */
   implicit class ArrayOps[A](val xs: Array[A])
   extends AnyVal with IterableOps[A]
-     with SeqMonoTransforms[A, Array[A]] {
+     with SeqMonoTransforms[A, Array[A]]
+     with Buildable[A, Array[A]] {
 
     protected def coll = new ArrayView(xs)
     def iterator = coll.iterator
 
-    private def fill[B](xs: Array[B], coll: Iterable[B]): Array[B] = {
-      val it = coll.iterator
-      var i = 0
-      while (it.hasNext) {
-        xs(i) = it.next
-        i += 1
-      }
-      xs
-    }
-
     override def view = new ArrayView(xs)
 
-    protected def fromLikeIterable(coll: Iterable[A]): Array[A] =
-      fill(
-        java.lang.reflect.Array.newInstance(xs.getClass.getComponentType, coll.size)
-          .asInstanceOf[Array[A]],
-        coll)
+    def elemTag: ClassTag[A] = ClassTag(xs.getClass.getComponentType)
+
+    protected def fromLikeIterable(coll: Iterable[A]): Array[A] = coll.toArray[A](elemTag)
 
-    def fromIterable[B: ClassTag](coll: Iterable[B]): Array[B] =
-      fill(new Array[B](coll.size), coll)
+    def fromIterable[B: ClassTag](coll: Iterable[B]): Array[B] = coll.toArray[B]
 
-    def fromIterable1[B: ClassTag](coll: Iterable[B]): Array[B] =
-      fill(new Array[B](coll.size), coll)
+    protected[this] def newBuilder = new ArrayBuffer[A].mapResult(_.toArray(elemTag))
 
-    def map[B: ClassTag](f: A => B): Array[B] = fromIterable1(View.Map(coll, f))
+    def map[B: ClassTag](f: A => B): Array[B] = fromIterable(View.Map(coll, f))
     def flatMap[B: ClassTag](f: A => IterableOnce[B]): Array[B] = fromIterable(View.FlatMap(coll, f))
     def ++[B >: A : ClassTag](xs: IterableOnce[B]): Array[B] = fromIterable(View.Concat(coll, xs))
     def zip[B: ClassTag](xs: IterableOnce[B]): Array[(A, B)] = fromIterable(View.Zip(coll, xs))
   }
 
-  case class ArrayView[A](xs: Array[A]) extends RandomAccessView[A] {
+  case class ArrayView[A](xs: Array[A]) extends IndexedView[A] {
     val start = 0
     val end = xs.length
     def apply(n: Int) = xs(n)
     override def className = "ArrayView"
   }
 
-/* ---------- Views -------------------------------------------------------*/
+  /* ---------- Views -------------------------------------------------------*/
 
   /** Concrete collection type: View */
   trait View[+A] extends Iterable[A] with IterableLike[A, View] {
     override def view = this
+
+    /** Avoid copying if source collection is already a view. */
     override def fromIterable[B](c: Iterable[B]): View[B] = c match {
       case c: View[B] => c
       case _ => View.fromIterator(c.iterator)
@@ -414,57 +738,76 @@ object CollectionStrawMan6 extends LowPriority {
     override def className = "View"
   }
 
-  /** View defined in terms of indexing a range */
-  trait RandomAccessView[+A] extends View[A] {
-    def start: Int
-    def end: Int
-    def apply(i: Int): A
-    def iterator: Iterator[A] = new Iterator[A] {
-      private var current = start
-      def hasNext = current < end
-      def next: A = {
-        val r = apply(current)
-        current += 1
-        r
-      }
-    }
-    override def knownLength = end - start max 0
-  }
-
+  /** This object reifies operations on views as case classes */
   object View {
     def fromIterator[A](it: => Iterator[A]): View[A] = new View[A] {
       def iterator = it
     }
+
+    /** The empty view */
     case object Empty extends View[Nothing] {
       def iterator = Iterator.empty
       override def knownLength = 0
     }
+
+    /** A view with given elements */
     case class Elems[A](xs: A*) extends View[A] {
       def iterator = Iterator(xs: _*)
       override def knownLength = xs.length
     }
+
+    /** A view that filters an underlying collection. */
     case class Filter[A](val underlying: Iterable[A], p: A => Boolean) extends View[A] {
       def iterator = underlying.iterator.filter(p)
     }
+
+    /** A view that partitions an underlying collection into two views */
     case class Partition[A](val underlying: Iterable[A], p: A => Boolean) {
+
+      /** The view consisting of all elements of the underlying collection
+       *  that satisfy `p`.
+       */
       val left = Partitioned(this, true)
+
+      /** The view consisting of all elements of the underlying collection
+       *  that do not satisfy `p`.
+       */
       val right = Partitioned(this, false)
     }
+
+    /** A view representing one half of a partition. */
     case class Partitioned[A](partition: Partition[A], cond: Boolean) extends View[A] {
       def iterator = partition.underlying.iterator.filter(x => partition.p(x) == cond)
     }
+
+    /** A view that drops leading elements of the underlying collection. */
     case class Drop[A](underlying: Iterable[A], n: Int) extends View[A] {
       def iterator = underlying.iterator.drop(n)
       override def knownLength =
         if (underlying.knownLength >= 0) underlying.knownLength - n max 0 else -1
     }
+
+    /** A view that takes leading elements of the underlying collection. */
+    case class Take[A](underlying: Iterable[A], n: Int) extends View[A] {
+      def iterator = underlying.iterator.take(n)
+      override def knownLength =
+        if (underlying.knownLength >= 0) underlying.knownLength min n else -1
+    }
+
+    /** A view that maps elements of the underlying collection. */
     case class Map[A, B](underlying: Iterable[A], f: A => B) extends View[B] {
       def iterator = underlying.iterator.map(f)
       override def knownLength = underlying.knownLength
     }
+
+    /** A view that flatmaps elements of the underlying collection. */
     case class FlatMap[A, B](underlying: Iterable[A], f: A => IterableOnce[B]) extends View[B] {
       def iterator = underlying.iterator.flatMap(f)
     }
+
+    /** A view that concatenates elements of the underlying collection with the elements
+     *  of another collection or iterator.
+     */
     case class Concat[A](underlying: Iterable[A], other: IterableOnce[A]) extends View[A] {
       def iterator = underlying.iterator ++ other
       override def knownLength = other match {
@@ -474,6 +817,10 @@ object CollectionStrawMan6 extends LowPriority {
           -1
       }
     }
+
+    /** A view that zips elements of the underlying collection with the elements
+     *  of another collection or iterator.
+     */
     case class Zip[A, B](underlying: Iterable[A], other: IterableOnce[B]) extends View[(A, B)] {
       def iterator = underlying.iterator.zip(other)
       override def knownLength = other match {
@@ -485,6 +832,32 @@ object CollectionStrawMan6 extends LowPriority {
     }
   }
 
+  /** View defined in terms of indexing a range */
+  trait IndexedView[+A] extends View[A] { self =>
+    def start: Int
+    def end: Int
+    def apply(i: Int): A
+
+    def iterator: Iterator[A] = new Iterator[A] {
+      private var current = start
+      def hasNext = current < end
+      def next: A = {
+        val r = apply(current)
+        current += 1
+        r
+      }
+    }
+
+    def reverse = new IndexedView[A] {
+      def start = self.start
+      def end = self.end
+      def apply(i: Int) = self.apply(end - 1 - i)
+    }
+
+    override def knownLength = end - start max 0
+    def length = knownLength
+  }
+
 /* ---------- Iterators ---------------------------------------------------*/
 
   /** A core Iterator class */
@@ -555,6 +928,16 @@ object CollectionStrawMan6 extends LowPriority {
       def hasNext = current.hasNext
       def next() = current.next()
     }
+    def take(n: Int): Iterator[A] = new Iterator[A] {
+      private var i = 0
+      def hasNext = self.hasNext && i < n
+      def next =
+        if (hasNext) {
+          i += 1
+          self.next()
+        }
+        else Iterator.empty.next()
+    }
     def drop(n: Int): Iterator[A] = {
       var i = 0
       while (i < n && hasNext) {
@@ -575,7 +958,7 @@ object CollectionStrawMan6 extends LowPriority {
       def hasNext = false
       def next = throw new NoSuchElementException("next on empty iterator")
     }
-    def apply[A](xs: A*): Iterator[A] = new RandomAccessView[A] {
+    def apply[A](xs: A*): Iterator[A] = new IndexedView[A] {
       val start = 0
       val end = xs.length
       def apply(n: Int) = xs(n)
diff --git a/tests/run/colltest6/CollectionTests_2.scala b/tests/run/colltest6/CollectionTests_2.scala
index 659bfb953..3304ffb22 100644
--- a/tests/run/colltest6/CollectionTests_2.scala
+++ b/tests/run/colltest6/CollectionTests_2.scala
@@ -49,7 +49,7 @@ object Test {
     println(xs9)
     println(xs10)
     println(xs11)
-     println(xs12)
+    println(xs12)
     println(xs13)
     println(xs14)
     println(xs15)
@@ -211,6 +211,79 @@ object Test {
     println(xs16.view)
   }
 
+  def lazyListOps(xs: Seq[Int]) = {
+    val x1 = xs.foldLeft("")(_ + _)
+    val y1: String = x1
+    val x2 = xs.foldRight("")(_ + _)
+    val y2: String = x2
+    val x3 = xs.indexWhere(_ % 2 == 0)
+    val y3: Int = x3
+    val x4 = xs.head
+    val y4: Int = x4
+    val x5 = xs.to(List)
+    val y5: List[Int] = x5
+    val (xs6, xs7) = xs.partition(_ % 2 == 0)
+    val ys6: Seq[Int] = xs6
+    val ys7: Seq[Int] = xs7
+    val xs8 = xs.drop(2)
+    val ys8: Seq[Int] = xs8
+    val xs9 = xs.map(_ >= 0)
+    val ys9: Seq[Boolean] = xs9
+    val xs10 = xs.flatMap(x => Cons(x, Cons(-x, Nil)))
+    val ys10: Seq[Int] = xs10
+    val xs11 = xs ++ xs
+    val ys11: Seq[Int] = xs11
+    val xs12 = xs ++ Nil
+    val ys12: Seq[Int] = xs12
+    val xs13 = Nil ++ xs
+    val ys13: Seq[Int] = xs13
+    val xs14 = xs ++ Cons("a", Nil)
+    val ys14: Seq[Any] = xs14
+    val xs15 = xs.zip(xs9)
+    val ys15: Seq[(Int, Boolean)] = xs15
+    val xs16 = xs.reverse
+    val ys16: Seq[Int] = xs16
+    println("-------")
+    println(x1)
+    println(x2)
+    println(x3)
+    println(x4)
+    println(x5)
+    println(xs6)
+    println(xs6.to(List))
+    println(xs7)
+    println(xs7.to(List))
+    println(xs8)
+    println(xs8.to(List))
+    println(xs9)
+    println(xs9.to(List))
+    println(xs10)
+    println(xs10.to(List))
+    println(xs11)
+    println(xs11.to(List))
+    println(xs12)
+    println(xs12.to(List))
+    println(xs13)
+    println(xs13.to(List))
+    println(xs14)
+    println(xs14.to(List))
+    println(xs15)
+    println(xs15.to(List))
+    println(xs16)
+    println(xs16.to(List))
+
+    import LazyList.#::
+    val xs17 = 1 #:: 2 #:: 3 #:: LazyList.Empty
+    println(xs17)
+    xs17 match {
+      case a #:: b #:: xs18 =>
+        println(s"matched: $a, $b, $xs18")
+      case _ =>
+    }
+    println(xs17)
+    println(xs17.to(List))
+  }
+
   def main(args: Array[String]) = {
     val ints = Cons(1, Cons(2, Cons(3, Nil)))
     val intsBuf = ints.to(ArrayBuffer)
@@ -222,5 +295,6 @@ object Test {
     viewOps(intsView)
     stringOps("abc")
     arrayOps(Array(1, 2, 3))
+    lazyListOps(LazyList(1, 2, 3))
   }
 }