public
Last active — forked from bkyrlach/TreeMagic.scala

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

  • Download Gist
A-Objective.txt
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
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
C#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
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
F#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
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
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
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
Nemerle
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
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
OCaml
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
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
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
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
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
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
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
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.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.