Sunday, June 11, 2017

Scala Immutability & Covariance

Target audience: Beginner
Estimated reading time: 10'

This posts illustrates the concept of immutable and covariant containers/collections in Scala in the case of the stack data structure.
This post uses Scala 2.11.6

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]= 
   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]] = => 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

def popAll[U >: T]: List[U] = pop(this,List[U]())
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).

Scala By Example - M. Odersky - June 2014


  1. Deep learning Domain is an AI function that mimics the workings of the human brain in processing data for use in detecting objects, recognizing speech, translating languages, and making decisions. IEEE Deep learning domain Deep Learning Projects for Final Year
    mimics the workings of the human brain in processing data for use in detecting objects, recognizing speech, translating languages, and making decisions.

    Smaller than expected IEEE Final Year project centers ground for all fragments of CSE & IT engineers hoping to assemble. Final Year Projects for CSE It gives you tips and rules that is progressively critical to consider while choosing any final year project point.

    Spring Framework has already made serious inroads as an integrated technology stack for building user-facing applications. Spring Framework Corporate TRaining the authors explore the idea of using Java in Big Data platforms.
    Specifically, Spring Framework provides various tasks are geared around preparing data for further analysis and visualization. Spring Training in Chennai

    The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training

  2. When half in} roulette on-line with the Martingale strategy, wager sizes can enhance rapidly, quickly exhausting your budget and the desk limits. Yes, you can to|you 토토사이트 probably can} play on line casino roulette on-line with actual money within the United Kingdom. At our really helpful roulette on-line casinos, you can to|you probably can} play extensive variety|all kinds} of on-line roulette variations. Most operators provide classic variations of European, French, and American Roulette. You also can discover some revolutionary variations of the classics. Make sure the on line casino you register at has a licence from a good regulatory agency earlier than creating an account and half in} roulette on-line for actual money.