Friday, October 5, 2012

Type Class Polymorphism and Monads

Target audience: Advanced
Estimated reading time: 45'


Most of software developers associate the concept of polymorphism to dynamic binding & class inheritance available in the most common object oriented programming languages such as C++ and Java. As part of its functional programming "DNA", Scala provides developers with  alternative polymorphism approaches (beside the ubiquitous method override).

Note: For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omitted 

Object-Oriented Polymorphism

Java or C++ programmers are familiar with this implementation of polymorphism as described in the example below. A trait the key behavior of a collection by declaring two method += to add a new item into the collection and -= to retrieve the first item from the collection.

trait Collection[T <: Double] {                           
   def += (t:T) : Boolean
   def -= : T 

The class, OrderedCollection implements ordered collection of type inherited from Double by defining the two abstract methods += & -=. This class specializes the behavior of the trait by ordering the elements in the collection.

class OrderedCollection[T <: Double] extends Collection[T] {
   import scala.collection.mutable.TreeSet
   var c = TreeSet.empty(Ordering.fromLessThan[T]((x:Double, y:Double) => (x < y)))
   override def += (t:T) : Boolean = c.add(t)
   override def -= : T = { 
     val top = c.head

The following code snippet illustrate a simple use case for the ordered collection. Note the declaration of the type of the collection instance, thisCollection is not required and added for the sake of clarity.

val thisCollection: Collection[Double] = new OrderedCollection[Double]
thisCollection += 9.556
thisCollection += 45.7
thisCollection += 4.9

Type Class Polymorphism 
Scala supports Type class polymorphism, also referred as Ah-hoc polymorphism in technical articles. Scala also supports Ah-Doc polymorphism which the ability to create and apply generic polymorphic operators or functions to arguments of different types. Ad hoc polymorphism lets you add features to a type on demand.
Let's define a Wrapper type (trait) which basic purpose is to wrap an element into a collection M[_] of this element. The Wrapper type class declares the operators apply and get that is to be implemented by wrapper associated to a predetermined collection.
- apply creates a collection M[T] of element of type T.
- get retrieves the first and only element of the collection.

Note: The type of the element in the collection is not a parameter type for the Wrapper: T is the type parameter for the collection and type M[_] is the parameter type for the wrapper. The Wrapper trait is defined as:

trait Container[M[_]] {
  def apply[T](t: T): M[T]
  def get[T](c: M[T]): T

We can create a type class ArrayBuffer to "wrap" any object by overriding the apply and get operators. The implicit conversion from ArrayBuffer to Wrapper is obviously independent from the type T of the contained element (validation of method argument is omitted).

implicit val arrayBuffer = new Container[ArrayBuffer] {
  override def apply[T](t: T) : ArrayBuffer[T] =  ArrayBuffer[T](t)
  override def get[T](ab: ArrayBuffer[T]) : T = ab.head 

def compose[M[_]: Container, X, Y](c1: M[X], c2: M[Y]) = {
   val c = implicitly[Container[M]]
   c(ab.get(c1), ab.get(c2))

One of the most known application of type class polymorphism is the monadic representation of collection. The concept and theoretical foundation of monads is discussed in the previous post. Monads define the minimum set of operations for a functional category of objects. Scala standard library includes quite a few of categories and their associated monadic representation: List[T], Option[T], ..
Let's extend our simple Wrapper to define a Monad for collection containing a single element. The monad must define a constructor, apply, a functor, map that converts a single element collection into a another single element collection by transforming its only element and a flatMap that generate a new single element collection from the element of an existing collection.

trait _Monad[M[_]] {
  def apply[T](t: T): M[T]
  def map[T, U](m: M[_])(f: T => U): M[U]
  def flatMap[T, U](m: M[_])(f: T => M[U]): M[U]

As with the trait wrapper we can create a implicit conversion from any single element ArrayBuffer into its associated monad to monadic operators can be used transparently by the client code.

implicit val mArrayBuffer = new _Monad[ArrayBuffer] {
  override def apply[T](t:T): ArrayBuffer[T] =  ArrayBuffer[T](t)
  override def map[T, U](m: ArrayBuffer[T])(f: T => U): ArrayBuffer[U] = ArrayBuffer[U](f(m.head))
  override def flatMap[T, U](m: ArrayBuffer[T])(f: T => ArrayBuffer[U]): ArrayBuffer[U] = f(m.head) 

Monads will be discussed in length in a future post.

* An Overview of the Scala Programming Language - 2nd Edition M. Odersky, P. Altherr, V. Cremet, I. Dragos, G. Dubochet, B. Emir, S. McDirmid, S. Micheloud, N. Mihaylov, M. Schinz, E. Stenman, L. Spoon, M. Zenger
* Programming in Scala - 2nd Edition M. Odersky, L. Spoon, B. Venners - Artima 2011
* Fabulous adventures in coding - Monads, part one E. Lippert's - 2013


  1. I can only express a word of thanks! Nothing else. Because your topic is nice, you can add knowledge. Thank you very much for sharing this information.

    Avriq India
    pest control
    cctv camera

  2. 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

  3. It was really helpful for me. Every tip is useful and innovating to understand easily. I feel happy and thanks for sharing this kind of valuable concept. amazon web services aws training in chennai. amazon web services aws training in chennai

    microsoft azure training in chennai

    workday training in chennai

    android-training-in chennai

    ios training in chennai