Friday, October 5, 2012

Type Class Polymorphism and Monads

Target audience: Advanced

Overview

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
     c.remove(top)
     top 
   }
}

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

println(thisCollection)


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


Monads

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.


References

Posted by No comments:
Labels: , , ,
Subscribe to: Posts (Atom)