Adventures in Type Theory: Parametric Polymorphism(Generics) vs Adhoc Polymophism(Type Classes) (Java,Scala,C#,F#,Nemerle,Haskell)

A-Objective.txt

The Objective

This language experiment was designed to show how parametric polymorphism and type classes are
implemented in different languages. The implementation languages where chosen out of personal
preference. I am well aware it's not complete and would love for you to help me with that.  If
you don't see your favorite language please add it as a comment.  I am also not an expert in all
of these languages but did try to make them as idiomatic as possible. If you believe there is a
better solution please leave a comment with the implementation.

The Code

The goal of the code is to create an abstract binary tree of type 'a and to create an insert function
based on a comparison function.  Last we demonstrate the use with type int.

Personal Takeaways:
  * ML based languages provide very terse and readable code, when compared to C based syntax.
  * The mixing of ML and C based syntax in Nemerle is interesting but not sure it helps
    readability.
  * Type Classes provide a better user experience due to the removal of wrapper elements.
  * In Scala using Implicits as Type Classes should be preferred over Generics.
  * Haskell and F# to have the easiest to read code. (this says a lot coming from a 14 year
    java veteran)
  * A better example of Type Classes should involve higher kinds. You can see an example in scala
    of this here: https://gist.github.com/2948611
      

Note: Parametric implementations start with PP and Type Class implementations start with TC.

If you are software nerd you can follow our adventures.
Twitter: @crkirkendall
         @benkyrlach

PP-CSharp-TreeMagic.cs

using System;

namespace TreeMagic{

    interface Comparable<T> {
        int compareTo(T a);
    }

    class ComparableInteger : Comparable<ComparableInteger> {
           public int val;

           public  ComparableInteger(int a){
               val=a;
           }

           public int compareTo(ComparableInteger a){
              if(val>a.val){
                  return -1;
              }else if(val==a.val){
                  return 0;
              }else{
                  return 1;
              }
           }

        override public String ToString(){
            return ""+val;
        }
    }

    class Tree<T> where T : Comparable<T> {
        public Tree<T> left;
        public T elem;
        public Tree<T> right;

        public Tree(Tree<T> l, T e, Tree<T> r){
            this.left=l;
            this.elem=e;
            this.right=r;
        }

        override public String ToString(){
            String l = left == null ? "Tip" : left.ToString();
            String r = right == null ? "Tip" : right.ToString();
            return "[" + l + ":" + elem.ToString() + ":" + r +"]";
        }
    }

    static class TreeOperations
    {
        public static Tree<T> insert<T>(Tree<T> t, T e) where T : Comparable<T>
        {
            if (t == null)
                return new Tree<T>(null, e, null);
            switch (t.elem.compareTo(e))
            {
                case -1: return new Tree<T>(insert(t.left, e), t.elem, t.right);
                case 1: return new Tree<T>(t.left, t.elem, insert(t.right, e));
                default: return new Tree<T>(t.left, t.elem, t.right);
            }
        }
    }

    class Program{
        static void Main(string[] args){
            ComparableInteger a = new ComparableInteger(123);
            Tree<ComparableInteger> b=new Tree<ComparableInteger>(null,a,null);
            Tree<ComparableInteger> c = TreeOperations.insert(b, new ComparableInteger(100));
            Console.WriteLine(c);
        }
    }
}

PP-FSharp-TreeMagic.fs

open System 

type IComparable<'a> =
  abstract CompareTo : 'a -> int

type ComparableInt(v : int) =
  member this.Val = v
  override this.ToString() = string(v)
  interface IComparable<ComparableInt> with
    member this.CompareTo(a) = 
      if v > a.Val then 1
      elif v = a.Val then 0
      else -1

type Tree<'a when 'a :> IComparable<'a>> =
  | Node of Tree<'a> * 'a * Tree<'a>
  | Tip
  override this.ToString() = 
    match this with
      | Node(l,c,r) -> sprintf "[%s,%s,%s]" (l.ToString()) (c.ToString()) (r.ToString())
      | Tip -> "Tip"
  
module TreeOperations =
  let rec insert(t : Tree<'a>, e : 'a when 'a :> IComparable<'a>) =
    match t with
      | Node(l, c, r) ->
        match e.CompareTo(c) with 
         | -1 -> Node(insert(l, e), c, r)
         | 1 -> Node(l, c, insert(r, e))
         | 0 -> Node(l, e, r)
      | Tip -> Node(Tip, e, Tip)
        
[<EntryPoint>]
let main(args : string[]) =        
  let tmp = Node(Tip, ComparableInt(3), Tip)
  let tmp2 = TreeOperations.insert(tmp, ComparableInt(4))        
  Console.WriteLine(tmp2)
  0

PP-Java-TreeMagic.java

public class TreeMagic {
        public static void main(String[] args){
            ComparableInteger a = new ComparableInteger(123);
            Tree<ComparableInteger> b=new Tree<ComparableInteger>(null,a,null);
            Tree<ComparableInteger> c = Tree.insert(b, new ComparableInteger(100));
            System.out.println(c);
        }
}

interface Comparable<T> {
    public int compareTo(T a);
}

class ComparableInteger implements Comparable<ComparableInteger> {
       public int val;

       public  ComparableInteger(int a){
           val=a;
       }

       public int compareTo(ComparableInteger a){
          if(val>a.val){
              return -1;
          }else if(val==a.val){
              return 0;
          }else{
              return 1;
          }
       }

    public String toString(){
        return ""+val;
    }
}

class Tree<T extends Comparable<T>> {
    public final Tree<T> left;
    private final T elem;
    private final Tree<T> right;

    public Tree(Tree<T> l, T e, Tree<T> r){
        this.left=l;
        this.elem=e;
        this.right=r;
    }

    public static <T extends Comparable<T>> Tree<T> insert(Tree<T> t, T e){
        if(t==null)
            return new Tree<T>(null,e,null);
        switch (t.elem.compareTo(e)){
            case -1: return new Tree<T>(Tree.insert(t.left, e), t.elem, t.right);
            case 1: return new Tree<T>(t.left, t.elem, Tree.insert(t.right, e));
            default: return new Tree<T>(t.left,t.elem,t.right);
        }
    }

    public String toString(){
        return "[" + left + ":" + elem + ":" + right +"]";
    }
}

PP-Nemerle-TreeMagic.n

interface IComparable [A] {
  CompareTo (elem : A) : int;
}

[Record]
class ComparableInteger : IComparable[ComparableInteger] {
       public val : int;

       public CompareTo(a : ComparableInteger) : int{
          if(val>a.val) 1
          else if(val==a.val) 0
          else -1
       }
       
       public override ToString() : string {  
          val.ToString() 
       }
}
 
variant Tree[A] where A : IComparable[A] {
  | Node {
      left : Tree[A];
      elem : A;
      right : Tree[A];
    }
  | Tip
  
  public override ToString() : string {
    match (this) {
      | Node(l, e, r) => ($ "[$l:$e:$r]") 
      | Tip => "Tip"
    }
  }
}

module TreeOperations {
  public Insert[A] (t : Tree[A], e : A) : Tree[A] where A : IComparable[A] {
    match (t) {
      | Tree.Node(l, c, r) =>
        match (e.CompareTo(c)) {
         | -1 => Tree.Node(Insert(l, e), c, r)
         | 1 => Tree.Node(l, c, Insert(r, e))
         | 0 => Tree.Node(l, e, r)
        }
      | Tip =>
        Tree.Node(Tree.Tip(), e, Tree.Tip())
    }
  }
}

class TreeMagic {
   static Main () : void {
     def a = ComparableInteger(123);
     def b = Tree.Node(Tree.Tip(),a,Tree.Tip());
     def c = TreeOperations.Insert(b, ComparableInteger(100));
     System.Console.WriteLine (c);
   }
 }

PP-Ocaml.ml

type 'a tree = Tip | Node of 'a tree * 'a * 'a tree

module type COMPARABLE =
    sig
      type t
      val compare: t -> t -> int
    end
  
module IntComparable =
    struct
      type t = int
      let compare x y = 
        if x < y then -1
        else if x > y then 1
        else 0
    end
    
module TreeOperations =
    functor(Elt : COMPARABLE) ->
      struct
        let rec insert t e =
          match t with
             Tip -> Node(Tip, e, Tip)
           | Node (l, c, r) -> 
                 match (Elt.compare e c) with
                   -1 -> Node((insert l e), c, r)
                  | 1 -> Node(l, c, (insert r e))
                  | 0 -> Node(l, e, r)
      end
    
           
module IntTreeOp = TreeOperations(IntComparable)

let tmp1 = IntTreeOp.insert Tip 3

let tmp2 = IntTreeOp.insert tmp1 4

PP-Scala-TreeMagic.scala

package problems

trait Comparable[T] {
  def compareTo(t: T): Int
}

case class ComparableInt(val a: Int) extends Comparable[ComparableInt] {
  override def compareTo(b: ComparableInt): Int = {
    if(a < b.a) {
      -1
    } else if (a > b.a) {
      1
    } else {
      0
    }
  }
}

abstract class Tree[A <: Comparable[A]]

case class Node[A <: Comparable[A]](l: Tree[A], c: A, r: Tree[A]) extends Tree[A] 
case class Tip[A <: Comparable[A]] extends Tree[A]

object Tree {
  def insert[A <: Comparable[A]](t: Tree[A], e: A): Tree[A] = {
    t match {
      case Node(l, c, r) => {
        e.compareTo(c) match {
          case -1 => Node(Tree.insert(l, e), c, r)
          case 1 => Node(l, c, insert(r, e))
          case 0 => Node(l, e, r)
        }          
      }
      case Tip() => Node(Tip(), e, Tip())
    }
  }
}

object TreeMagic extends App {
  val a = ComparableInt(123) 
  val b = Node(Tip(), a, Tip())
  val c = Tree.insert(b, ComparableInt(100))
  
  println(c)
}

TC-Haskell-TreeMagic.hs

class Comparable a where
  compareTo :: a -> a -> Int

intCompare :: Int -> Int -> Int
intCompare x y 
  | x < y  = -1
  | x > y  =  1
  | x == y =  0
  
instance Comparable Int where 
  compareTo x y  =  intCompare x y

data Tree a = Tip | Node (Tree a) a (Tree a)
  deriving Show

insert :: (Comparable a) => Tree a -> a -> Tree a
insert t e = 
  case t of
    Node l c r -> 
       case compareTo c e of
         -1 -> Node (insert l e) c r
          1 -> Node l c (insert r e)
          0 -> Node l e r
    Tip -> Node Tip e Tip             

main :: IO ()
main = do
      let tmp = Node Tip (3::Int) Tip
          tmp2 = insert tmp 4
      print tmp2

TC-Scala-TreeMagic.scala

trait Comparable[T] {
  def compare(a: T, b: T): Int
}
object Comparable {
  implicit object IntComparable extends Comparable[Int] {
    override def compare(a: Int, b: Int): Int = {
     if(a < b) {
    	 -1
     } else if (a > b) {
    	 1
     } else {
    	 0
     }
    }
  }
}

abstract class Tree[A: Comparable]

case class Node[A: Comparable](l: Tree[A], c: A, r: Tree[A]) extends Tree[A] 
case class Tip[A: Comparable] extends Tree[A]

object Tree {
  def insert[A : Comparable](t: Tree[A], e: A) : Tree[A] = {
    t match {
      case Node(l, c, r) => {
        implicitly[Comparable[A]].compare(e,c) match {
          case -1 => Node(Tree.insert(l, e), c, r)
          case 1 => Node(l, c, insert(r, e))
          case 0 => Node(l, e, r)
        }          
      }
      case Tip() => Node(Tip(), e, Tip())
    }
  }
}

object TreeMagic extends App {
  val a = 123 
  val b = Node(Tip(), a, Tip())
  val c = Tree.insert(b, 100)
  
  println(c)
}

Why toString() does not present in all examples?

@vlad2 - Haskell and Scala have default to strings that present readable versions of the tree. The "derive show" is what is required for this in Haskell.