An unusual definition of total ordering

One of the things that will show up in the imminently forthcoming Scala 2.7.1 release candidate, is the addition of traits for representing equivalence relations, partial orderings, and total orderings. Previously, the trait

`Ordered`
was used for representing totally ordered things:

```trait Ordered[A] {
def compare(that: A): Int
def <  (that: A): Boolean = (this compare that) <  0
def >  (that: A): Boolean = (this compare that) >  0
def <= (that: A): Boolean = (this compare that) <= 0
def >= (that: A): Boolean = (this compare that) >= 0
def compareTo(that: A): Int = compare(that)
}```

However, the

`Ordered`
trait does not provide a representation of a total ordering. Therefore, the new trait `Ordering`:

``` trait Ordering[T] extends PartialOrdering[T] {
def compare(x: T, y: T): Int
override def lteq(x: T, y: T): Boolean = compare(x, y) <= 0
override def gteq(x: T, y: T): Boolean = compare(x, y) >= 0
override def lt(x: T, y: T): Boolean = compare(x, y) < 0
override def gt(x: T, y: T): Boolean = compare(x, y) > 0
override def equiv(x: T, y: T): Boolean = compare(x, y) == 0
}
```

The tricky part however, was writing description of the properties required of something that implements the

`Ordering`
trait. When one normally thinks of a total ordering one thinks of a relation that is

• anti-symmetric,
• transitive,
• and total.

The problem is that

`Ordering`
is not defined in terms of a binary relation, but a binary function producing integers (
`compare`
). If the first argument is less than the second the function returns a negative integer, if they are equal in the ordering the function returns zero, and if the second argument is less than the first the function returns a positive integer. Therefore, it is not straightforward to express these same properties. The best I could come up with was

• `compare(x, x) == 0`
, for any
`x`
of type
`T`
.
• `compare(x, y) == z`
and
`compare(y, x) == w`
then
`Math.signum(z) == -Math.signum(w)`
, for any
`x`
and
`y`
of type
`T`
and
`z`
and
`w`
of type
`Int`
.
• if
`compare(x, y) == z`
and
`lteq(y, w) == v`
and
`Math.signum(z) >= 0`
and
`Math.signum(v) >= 0`
then
`compare(x, w) == u`
and
`Math.signum(z + v) == Math.signum(u)`
,
for any
`x`
,
`y`
, and
`w`
of type
`T`
and
`z`
,
`v`
, and
`u`
of type
`Int`
.

Where

`Math.signum`
returns
`-1`
if its input is negative,
`0`
if its input is
`0`
, and
`1`
if its input is positive.

The first property is clearly reflexivity. I call the third property transitivity. I am not sure what to call the second property. I do not think a notion of totality is required because it is assumed you will always get an integer back from

`compare`
rather than it throwing an exception or going into an infinite loop.

It would probably be a good exercise to prove that given these properties on

`compare`
hold if and only if
`lteq`
(defined above in terms of
`compare`
) has all the normal properties of a total ordering.