Target audience: Beginner
Estimated reading time: 4'
This posts illustrates the concept of immutable and covariant containers/collections in Scala in the case of the stack data structure.
Table of contents
Note: This article uses Scala 2.11.6
Overview
There is a relation between immutability and covariance which may not be apparent to a novice Scala programmer. Let's consider the case of a mutable and immutable implementation of a stack. The mutable stack is a container of elements with method to push element into (pop the last element from) the stack.
class MutableStack[T] {
private[this] val _stack = new ListBuffer[T]
final def pop: Option[T]=
if(_stack.isEmpty)
None
else
Some(_stack.remove(_stack.size-1))
def push(t: T): Unit = _stack.append(t)
}
The internal container is defined as a ListBuffer instance. The elements are appended to the list buffer (push) and the method pop pops the last elements pushed onto the stack.
This implementation has a major inconvenient: It cannot accept elements of type other than T because ListBuffer is a invariant collection. Let's consider then a immutable stack
Immutability and covariance
An covariant immutable stack cannot access its elements unless its elements are contained by itself. This feat is accomplish by breaking down the stack recursively as the last element pushed into the stack and the previous state of the stack.
class ImmutableStack[+T](
val t: T,
val stack: Option[ImmutableStack[T]]) {
def this(t: T) = this(t, Some(new EmptyImmutableStack(t)))
...
}
In this recursive approach the immutable stack is initialized with a single element of type T and the option of the existing immutable stack. The stack can be defined as reusable with covariance because elements are managed by the stack itself stack.
The next step is to define the initial state of the stack. We could have chosen a singleton empty stack with no elements. Instead, we define the first state of the immutable stack as:
class EmptyImmutableStack[+T](t: T) extends ImmutableStack[T](t, None)
Next let's define the pop and push operators for ImmutableStack. The pop method return the previous state of the immutable stack that is next to last element pushed into the stack. The push method is contra-variant as its push an element of super type of T. The existing state this stack is added as the previous (2nd argument) state.
final def pop: Option[ImmutableStack[T]] =
stack.map(sk => new ImmutableStack[T](sk.t, sk.stack))
def push[U >: T](u: U): ImmutableStack[U] = new ImmutableStack[U](u, Some(this))
Tail recursion
The next step is to traverse the entire stack and return a list of all its element. This is accomplished through a tail recursion on the state of the stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def popAll[U >: T]: List[U] = pop(this,List[U]())
@scala.annotation.tailrec
private def pop[U >: T](
_stck: ImmutableStack[U],
xs: List[U]
): List[U] = _stck match {
case st: EmptyImmutableStack[T] => xs.reverse
case st: ImmutableStack[T] => {
val newStack = _stck.stack.getOrElse(
new EmptyImmutableStack[T](_stck.t)
)
pop(newStack, _stck.t :: xs)
}
}
|
The recursion call pop (line 4) updates the list xs (line 6) and exists when the ImmutableStack is empty of type EmptyImmutableStack (line 9). The list has to be reversed to index the list elements from the last to the first (line 9). As long as the stack is not empty (or type ImmutableStack) the method recurses (line 14).
It is time to test drive this immutable stack.
val intStack = new ImmutableStack[Int](4)
val newStack = intStack.push(56).push(14).push(77)
println(newStack.popAll.mkString(", "))
The values in the stack are: 77, 14, 56, 4.
This examples illustrates the concept of immutable, covariant stack by using the instance of the stack has its state (current list of elements it contains).
This examples illustrates the concept of immutable, covariant stack by using the instance of the stack has its state (current list of elements it contains).
