Skip to content

Instantly share code, notes, and snippets.

@bkyrlach
Created September 13, 2012 21:44
Show Gist options
  • Save bkyrlach/3717913 to your computer and use it in GitHub Desktop.
Save bkyrlach/3717913 to your computer and use it in GitHub Desktop.
Nemerel tree converted to 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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment