101.03 - Data and abstraction

Class hierarchies

Abstract class:

abstract class IntSet {
  def incl(x: Int): IntSet
  def contains(x: Int): Boolean
  def union(other: IntSet): IntSet
}

Implementation class:

class Empty extends IntSet {
  def incl(x: Int): IntSet = new NonEmpty(x, new Empty, new Empty)

  def contains(x: Int): Boolean = false

  def union(other: IntSet) = other

  override def toString = "."
}

class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
  def incl(x: Int): IntSet = 
    if (x < elem) new NonEmpty(elem, left incl x, right)
    else if (x > elem) new NonEmpty(elem, left, right incl elem)
    else this

  def contains(x: Int): Boolean = 
    if (x < elem) left contains elem
    else if (x > elem) right contains elem
    else true

  def union(other: IntSet): IntSet = ((left union right) union other) incl elem

  override def toString = "{" + left + elem + right + "}"
}

Overriding:

abstract class Base {
  def foo = 1
  def bar: Int
}
class Sub extends Base {
  override def foo = 2
  def bar = 3
}

Singletons:

object Empty extends IntSet {
  def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)
  def contains(x: Int): Boolean = false
  override def toString = "."
}

Class organization

Packages like in Java.

Imports:

import somepackage.SomeClass
import somepackage._
import somepackage.{SomeClass, SomeOtherClass}

Can import from any packages or Objects. The following are automatically imported:

• All members of package scala
• All members of package java.lang
• All members of the singleton object scala.Predef

Scala is a single inheritance language. Each class can have a single superclass. To emulate multiple inheritance we can use traits.

trait Planar {
  def height: Int
  def width: Int
  def area = height * width
}

class Square extends Shape with Planar with Moveable ...

Traits cannot have data fields (parameters).

Polymorphism

Value parameters:

trait IntList ...

class Cons(val head: Int, val tail: IntList) extends IntList

class Nil extends IntList ...

Note: trait is used here as an interface The value parameters (val head and val tail) automatically declare the two fields. The following:

class Cons(val head: Int, val tail: IntList) extends IntList

is equivalent to:

class Cons(_head: Int, _tail: Int) extends IntList = {
  def head = _head
  def tail = _tail
}

A generalization using type parameters (generics):

trait List[T]

class Cons[T](val head: T, val tail: List[T]) extends List[T]

class Nil[T] extends List[T]

Full implementation:

trait List[T] {
  def isEmpty: Boolean

  def head: T

  def tail: List[T]

  def nth(n: Integer): T = {
    if (isEmpty) throw new IndexOutOfBoundsException
    else if (n == 0) head
    else tail nth(n - 1)
  }
}

class Cons[T](val head: T, val tail: List[T]) extends List[T] {
  def isEmpty: Boolean = false
}

class Nil[T] extends List[T] {
  isEmpty: Boolean = true

  def head: Nothing = throw new NoSuchElementException("Nil.head")

  def tail: Nothing = throw new NoSuchElementException("Nil.tail")
}

Two forms of polymorphism:

• subtyping
• generics