Newer
Older
Here's an outline of a class hierarchy that represents lists of integers.
We pick the low-level class representation instead of enums or case classes to
make the underlying representation clearer.
trait IntList ...
class Node(val head: Int, val tail: IntList) extends IntList ...
class Empty() extends IntList ...
- an empty list `Empty()`, or
- a list `Node(x, xs)` consisting of a `head` element `x`
and a `tail` list `xs`.
Note the abbreviation `(val head: Int, val tail: IntList)` in the definition of `Cons`.
This defines at the same time parameters and fields of a class.
class Node(_head: Int, _tail: IntList) extends IntList
val head = _head
val tail = _tail
where `_head` and `_tail` are otherwise unused names.
Type Parameters
===============
It seems too narrow to define only lists with `Int` elements.
We'd need another class hierarchy for `Double` lists, and so on, one for each possible element type.
We can generalize the definition using a type parameter:
trait List[T]
class Node[T](val head: T, val tail: List[T]) extends List[T]
class Empty[T]() extends List[T]
Type parameters are written in square brackets, e.g. `[T]`.
Complete Definition of List
===========================
trait List[T] {
def isEmpty: Boolean
def head: T
def tail: List[T]
}
class Node[T](val head: T, val tail: List[T]) extends List[T] {
def isEmpty = false
}
class Empty[T]() extends List[T] {
def isEmpty = true
def head = throw NoSuchElementException("Nil.head")
def tail = throw NoSuchElementException("Nil.tail")
Like classes, functions can have type parameters.
For instance, here is a function that creates a list consisting of a single element.
def singleton[T](elem: T) = Node[T](elem, Empty[T]())
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
In fact, the Scala compiler can usually deduce the correct type
parameters from the value arguments of a function call.
So, in most cases, type parameters can be left out. You could also write:
singleton(1)
singleton(true)
Types and Evaluation
====================
Type parameters do not affect evaluation in Scala.
We can assume that all type parameters and type arguments are removed
before evaluating the program.
This is also called \red{type erasure}.
Languages that use type erasure include Java, Scala, Haskell, ML, OCaml.
Some other languages keep the type parameters around at run time, these include C#, F#.
Yet other languages expand the program into specialized copies per type argument, these include C++ or Rust.
Polymorphism
============
Polymorphism means that a function type comes "in many forms".
In programming it means that
- the function can be applied to arguments of many types, or
- the type can have instances of many types.
->
We have seen two principal forms of polymorphism:
- subtyping: instances of a subclass can be passed to a base class
- generics: instances of a function or class are created by type parameterization.
Write a function `nth` that takes an integer `n` and a list and
selects the `n`'th element of the list.
If index is outside the range from `0` up the the length of the list minus one, a `IndexOutOfBoundsException` should be thrown.