diff options
author | Geoffrey Washburn <geoffrey.washburn@epfl.ch> | 2008-04-03 14:16:41 +0000 |
---|---|---|
committer | Geoffrey Washburn <geoffrey.washburn@epfl.ch> | 2008-04-03 14:16:41 +0000 |
commit | 4ec9c8abe1b2bb8aff74edaf954453070bef89fd (patch) | |
tree | c9c312d0d1aecb927d332500552e7547a6ed8802 /src/library | |
parent | fcb2ea2ebd5b190dbdb962a7cee3588a1d2c2aa4 (diff) | |
download | scala-4ec9c8abe1b2bb8aff74edaf954453070bef89fd.tar.gz scala-4ec9c8abe1b2bb8aff74edaf954453070bef89fd.tar.bz2 scala-4ec9c8abe1b2bb8aff74edaf954453070bef89fd.zip |
First complete draft of the equivalence, partia...
First complete draft of the equivalence, partial ordering, and total
ordering traits. Documentation for the total ordering is a little
"novel".
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/Equiv.scala | 27 | ||||
-rw-r--r-- | src/library/scala/Ordering.scala | 72 | ||||
-rw-r--r-- | src/library/scala/PartialOrdering.scala | 62 |
3 files changed, 148 insertions, 13 deletions
diff --git a/src/library/scala/Equiv.scala b/src/library/scala/Equiv.scala index bcbaf26c8b..07e7793d58 100644 --- a/src/library/scala/Equiv.scala +++ b/src/library/scala/Equiv.scala @@ -10,15 +10,32 @@ package scala -/** A trait for representing equivalence relations. - * @author Geoffrey Washburn - * @version 0.9, 2008-03-19 +/** A trait for representing equivalence relations. It is important to + * distinguish between a type that can be compared for equality or + * equivalence and a representation of equivalence on some type. This + * trait is for representing the latter. + * + * An <a href="http://en.wikipedia.org/wiki/Equivalence_relation">equivalence + * relation</a> is a binary relation on a type. This relation is exposed as + * the <code>equiv</code> method of the <code>Equiv</code> trait. This + * relation must be: + * <ul> + * <li>reflexive: <code>equiv(x, x) == true</code>, for any <code>x</code> of + * type <code>T</code>.</li> + * <li>symmetric: <code>equiv(x, y) == equiv(y, x)</code>, for any <code>x</code> + * and <code>y</code> of type <code>T</code>.</li> + * <li>transitive: if <code>equiv(x, y) == true</code> and <code>equiv(y, z) == true</code> + * then <code>equiv(x, z) == true</code>, for any <code>x</code>, <code>y</code>, + * and <code>z</code> of type <code>T</code>.</li> + * </ul> + * + * @author Geoffrey Washburn + * @version 1.0, 2008-04-03 */ trait Equiv[T] { /** Returns <code>true</code> iff <code>x</code> is equivalent to - * <code>y</code>. The implementation should be equivalence - * relation: reflexive, transitive, symmetric. + * <code>y</code>. */ def equiv(x: T, y: T): Boolean } diff --git a/src/library/scala/Ordering.scala b/src/library/scala/Ordering.scala index 9ae63fd641..358cfb5bdf 100644 --- a/src/library/scala/Ordering.scala +++ b/src/library/scala/Ordering.scala @@ -10,15 +10,71 @@ package scala -/** A trait for representing total orderings. - * @author Geoffrey Washburn - * @version 0.9, 2008-03-19 +/** A trait for representing total orderings. It is important to + * distinguish between a type that has a total order and a represnetation + * of total ordering on some type. This trait is for representing the + * latter. + * + * A <a href="http://en.wikipedia.org/wiki/Total_order">total ordering</a> + * is a binary relation on a type <code>T</code> that is also a partial + * ordering on values of type <code>T</code>. This relation is exposed as + * the <code>compare</code> method of the <code>Ordering</code> trait. + * This relation must be: + * <ul> + * <li>reflexive: <code>compare(x, x) == 0</code>, for any <code>x</code> of + * type <code>T</code>.</li> + * <li>(need a name): <code>compare(x, y) == z</code> and <code>compare(y, x) == w</code> + * then <code>Math.signum(z) == -Math.signum(w)</code>, for any <code>x</code> and <code>y</code> of + * type <code>T</code> and <code>z</code> and <code>w</code> of type <code>Int</code>.</li> + * <li>upward transitive: if <code>compare(x, y) == z</code> and <code>lteq(y, w) == v</code> + * and <code>Math.signum(z) >= 0</code> and <code>Math.signum(v) >= 0</code> then + * <code>compare(x, w) == u</code> and <code>Math.signum(z + v) == Math.signum(u)</code>, + * for any <code>x</code>, <code>y</code>, + * and <code>w</code> of type <code>T</code> and <code>z</code>, <code>v</code>, and <code>u</code> + * of type <code>Int</code>.</li> + * <li>downward transitive: if <code>compare(x, y) == z</code> and <code>lteq(y, w) == v</code> + * and <code>Math.signum(z) <= 0</code> and <code>Math.signum(v) <= 0</code> then + * <code>compare(x, w) == u</code> and <code>Math.signum(z + v) == Math.signum(u)</code>, + * for any <code>x</code>, <code>y</code>, + * and <code>w</code> of type <code>T</code> and <code>z</code>, <code>v</code>, and <code>u</code> + * of type <code>Int</code>.</li> + * </ul> + * + * @author Geoffrey Washburn + * @version 0.9, 2008-04-03 */ -trait Ordering[T] extends Equiv[T] { +trait Ordering[T] extends PartialOrdering[T] { + /** Returns a negative integer iff <code>x</code> comes before + * <code>y</code> in the ordering, returns 0 iff <code>x</code> + * is the same in the ordering as <code>y</code>, and returns a + * positive number iff <code>x</code> comes after + * <code>y</code> in the ordering. + */ def compare(x: T, y: T): Int - def gteq(x: T, y: T): Boolean = compare(x, y) >= 0 - def lteq(x: T, y: T): Boolean = compare(x, y) <= 0 - def lt(x: T, y: T): Boolean = compare(x, y) < 0 - def gt(x: T, y: T): Boolean = compare(x, y) > 0 + + /** Returns <code>true</code> iff <code>x</code> comes before + * <code>y</code> in the ordering. + */ + override def lteq(x: T, y: T): Boolean = compare(x, y) <= 0 + + /** Returns <code>true</code> iff <code>y</code> comes before + * <code>x</code> in the ordering. + */ + override def gteq(x: T, y: T): Boolean = compare(x, y) >= 0 + + /** Returns <code>true</code> iff <code>x</code> comes before + * <code>y</code> in the ordering and is not the same as <code>y</code>. + */ + override def lt(x: T, y: T): Boolean = compare(x, y) < 0 + + /** Returns <code>true</code> iff <code>y</code> comes before + * <code>x</code> in the ordering and is not the same as <code>x</code>. + */ + override def gt(x: T, y: T): Boolean = compare(x, y) > 0 + + /** Returns <code>true</code> iff <code>x</code> is equivalent to + * <code>y</code> in the ordering. + */ + override def equiv(x: T, y: T): Boolean = compare(x, y) == 0 } diff --git a/src/library/scala/PartialOrdering.scala b/src/library/scala/PartialOrdering.scala new file mode 100644 index 0000000000..0945121724 --- /dev/null +++ b/src/library/scala/PartialOrdering.scala @@ -0,0 +1,62 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id$ + +package scala + +/** A trait for representing partial orderings. It is important to + * distinguish between a type that has a partial order and a represnetation + * of partial ordering on some type. This trait is for representing the latter. + * + * A <a href="http://en.wikipedia.org/wiki/Partial_order">partial ordering</a> + * is a binary relation on a type <code>T</code> that is also an equivalence + * relation on values of type <code>T</code>. This relation is exposed as + * the <code>lteq</code> method of the <code>PartialOrdering</code> trait. + * This relation must be: + * <ul> + * <li>an equivalence relation: if <code>equiv(x, y)</code> then <code>lteq(x, y)</code>, + * for any <code>x</code> and <code>y</code> of type <code>T</code>.</li> + * <li>anti-symmetric: <code>lteq(x, y) == true</code> and <code>lteq(y, x) == true</code> + * then <code>equiv(x, y)</code>, for any <code>x</code> and <code>y</code> of + * type <code>T</code>.</li> + * <li>transitive: if <code>lteq(x, y) == true</code> and <code>lteq(y, z) == true</code> + * then <code>lteq(x, z) == true</code>, for any <code>x</code>, <code>y</code>, + * and <code>z</code> of type <code>T</code>.</li> + * </ul> + * + * @author Geoffrey Washburn + * @version 1.0, 2008-04-0-3 + */ + +trait PartialOrdering[T] extends Equiv[T] { + /** Returns <code>true</code> iff <code>x</code> comes before + * <code>y</code> in the ordering. + */ + def lteq(x: T, y: T): Boolean + + /** Returns <code>true</code> iff <code>y</code> comes before + * <code>x</code> in the ordering. + */ + def gteq(x: T, y: T): Boolean = lteq(y, x) + + /** Returns <code>true</code> iff <code>x</code> comes before + * <code>y</code> in the ordering and is not the same as <code>y</code>. + */ + def lt(x: T, y: T): Boolean = lteq(x, y) && !equiv(x, y) + + /** Returns <code>true</code> iff <code>y</code> comes before + * <code>x</code> in the ordering and is not the same as <code>x</code>. + */ + def gt(x: T, y: T): Boolean = gteq(x, y) && !equiv(x, y) + + /** Returns <code>true</code> iff <code>x</code> is equivalent to + * <code>y</code> in the ordering. + */ + def equiv(x: T, y: T): Boolean = lteq(x,y) && lteq(y,x) +} |