This posts illustrates the concept of immutable and covariant containers/collections in Scala in the case of the

*stack*data structure.**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

This implementation has a major inconvenient: It cannot accept elements of type other than T because

**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, covariance and tail recursion**

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

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:

**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))

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

It is time to test drive this immutable stack.

**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).

**References**

Scala By Example - M. Odersky - June 2014

## No comments:

## Post a Comment