Code Examples for

Programming in Scala, Second Edition

Return to chapter index

22 Implementing Lists

Sample run of chapter's interpreter examples

22.1 The List class in principle


// In file list-impl/Misc.scala package scala abstract class List[+T] {
scala> val xs = List(1, 2, 3) xs: List[Int] = List(1, 2, 3) scala> var ys: List[Any] = xs ys: List[Any] = List(1, 2, 3)
// In file list-impl/Misc.scala def isEmpty: Boolean def head: T def tail: List[T]
// In file list-impl/Misc.scala case object Nil extends List[Nothing] { override def isEmpty = true def head: Nothing = throw new NoSuchElementException("head of empty list") def tail: List[Nothing] = throw new NoSuchElementException("tail of empty list") }
// In file list-impl/Misc.scala final case class ::[T](hd: T, tl: List[T]) extends List[T] { def head = hd def tail = tl override def isEmpty: Boolean = false }
// In file list-impl/Misc.scala final case class ::[T](head: T, tail: List[T]) extends List[T] { override def isEmpty: Boolean = false }
// In file list-impl/Misc.scala def length: Int = if (isEmpty) 0 else 1 + tail.length
// In file list-impl/Misc.scala def drop(n: Int): List[T] = if (isEmpty) Nil else if (n <= 0) this else tail.drop(n - 1)
// In file list-impl/Misc.scala def map[U](f: T => U): List[U] = if (isEmpty) Nil else f(head) :: tail.map(f)
abstract class Fruit class Apple extends Fruit class Orange extends Fruit
scala> val apples = new Apple :: Nil apples: List[Apple] = List(Apple@585fa9) scala> val fruits = new Orange :: apples fruits: List[Fruit] = List(Orange@cd6798, Apple@585fa9)
def ::[U >: T](x: U): List[U] = new scala.::(x, this)
// In file list-impl/Misc.scala def ::[U >: T](x: U): List[U] = new ::(x, this)
// A thought experiment (which wouldn't work) def ::(x: T): List[T] = new scala.::(x, this)
// In file list-impl/Misc.scala def :::[U >: T](prefix: List[U]): List[U] = if (prefix.isEmpty) this else prefix.head :: prefix.tail ::: this
prefix.head :: prefix.tail ::: this equals (because :: and ::: are right-associative) prefix.head :: (prefix.tail ::: this) equals (because :: binds to the right) (prefix.tail ::: this).::(prefix.head) equals (because ::: binds to the right) this.:::(prefix.tail).::(prefix.head)

22.2 The ListBuffer class


// In file list-impl/Misc.scala def incAll(xs: List[Int]): List[Int] = xs match { case List() => List() case x :: xs1 => x + 1 :: incAll(xs1) }
for (x <- xs) // ??
// In file list-impl/Misc.scala var result = List[Int]() // a very inefficient approach for (x <- xs) result = result ::: List(x + 1) result
// In file list-impl/Misc.scala import scala.collection.mutable.ListBuffer
// In file list-impl/Misc.scala val buf = new ListBuffer[Int] for (x <- xs) buf += x + 1 buf.toList

22.3 The List class in practice


final override def map[U](f: T => U): List[U] = { val b = new ListBuffer[U] var these = this while (!these.isEmpty) { b += f(these.head) these = these.tail } b.toList }
// In file list-impl/Misc.scala final case class ::[U](hd: U, private[scala] var tl: List[U]) extends List[U] { def head = hd def tail = tl override def isEmpty: Boolean = false }
// In file list-impl/Misc.scala package scala.collection.immutable final class ListBuffer[T] extends Buffer[T] { private var start: List[T] = Nil private var last0: ::[T] = _ private var exported: Boolean = false ...
// In file list-impl/Misc.scala override def toList: List[T] = { exported = !start.isEmpty start }
override def += (x: T) { if (exported) copy() if (start.isEmpty) { last0 = new scala.::(x, Nil) start = last0 } else { val last1 = last0 last0 = new scala.::(x, Nil) last1.tl = last0 } }

22.4 Functional on the outside


// In file list-impl/Misc.scala val ys = 1 :: xs val zs = 2 :: xs
ys.drop(2).tail = Nil // can't do this in Scala!

22.5 Conclusion

For more information about Programming in Scala, Second Edition (the "Stairway Book"), please visit:

http://www.artima.com/shop/programming_in_scala_2ed

and:

http://booksites.artima.com/programming_in_scala_2ed

Copyright © 2007-2010 Artima, Inc. All rights reserved.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.