Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Adventures in Type Theory: Parametric Polymorphism(Generics) vs Adhoc Polymophism(Type Classes) (Java,Scala,C#,F#,Nemerle,Haskell)
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
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);
}
}
}
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
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 +"]";
}
}
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);
}
}
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
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)
}
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
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)
}
@VladD2

Why toString() does not present in all examples?

@ckirkendall
Owner

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.