Skip to content

Instantly share code, notes, and snippets.

@jaked
Created February 12, 2014 19:50
Show Gist options
  • Save jaked/8963171 to your computer and use it in GitHub Desktop.
Save jaked/8963171 to your computer and use it in GitHub Desktop.
trait Comparable {
type T
def compare(a: T, b: T): Int
}
trait IInterval {
type T
type Endpoint
def create(low: Endpoint, high: Endpoint): T
def isEmpty(t: T): Boolean
def contains(t: T, e: Endpoint): Boolean
def intersect(t1: T, t2: T): T
}
def makeInterval(endpoint: Comparable): IInterval = new IInterval {
type Endpoint = endpoint.T
sealed trait IntervalT
case class Interval(a: Endpoint, b: Endpoint) extends IntervalT
case object Empty extends IntervalT
type T = IntervalT
def create(low: Endpoint, high: Endpoint) =
if (endpoint.compare(low, high) > 0) Empty
else Interval(low, high)
def isEmpty(t: T) =
t match {
case Empty => true
case _ => false
}
def contains(t: T, x: endpoint.T) =
t match {
case Empty => false
case Interval(l, h) =>
endpoint.compare(x, l) >= 0 && endpoint.compare(x, h) <= 0
}
def intersect(t1: T, t2: T) = {
def min(x: Endpoint, y: Endpoint) = if (endpoint.compare(x, y) <= 0) x else y
def max(x: Endpoint, y: Endpoint) = if (endpoint.compare(x, y) >= 0) x else y
(t1, t2) match {
case (Empty, _) => Empty
case (_, Empty) => Empty
case (Interval(l1, h1), Interval(l2, h2)) =>
create(max(l1, l2), min(h1, h2))
}
}
}
object IntComparable extends Comparable {
type T = Int
def compare(a: T, b: T) = b - a
}
// now in repl
scala> val interval = makeInterval(IntComparable)
interval: IInterval = $anon$1@12fd41e0
scala> interval.create(3, 4)
<console>:17: error: type mismatch;
found : Int(3)
required: interval.Endpoint
interval.create(3, 4)
^
// We can fix it with
//
// def makeInterval(endpoint: Comparable): IInterval { type Endpoint = endpoint.T } = new IInterval {
//
// which should be the same as the sharing constraint
//
// This is a 2.10 feature but you can enable it in 2.9 with -Ydependent-method-types. Now:
scala> val interval = makeInterval(IntComparable)
interval: IInterval{type Endpoint = IntComparable.T} = $anon$1@dc33904
scala> interval.create(3, 4)
res2: interval.T = Interval(3,4)
// Notice that the type of interval is different from before; the sharing constraint is visisble
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment