[Haskell-cafe] Re: (flawed?) benchmark : sort
Daniel Fischer
daniel.is.fischer at web.de
Mon Mar 10 16:09:52 EDT 2008
Am Montag, 10. März 2008 20:12 schrieb Neil Mitchell:
> Hi
>
> > "The Ord class is used for totally ordered datatypes."
> >
> > This *requires* that it be absolutely impossible in valid code to
> > distinguish equivalent (in the EQ sense, not the == sense) things via
> > the functions of Ord. The intended interpretation of these functions is
> > clear and can be taken as normative:
> >
> > forall f . (compare x y == EQ and (f x or f y is defined))
> > ==> f x == f y)
>
> Are you sure? I would have read this as the ordering must be
> reflexive, antisymetric and transitive - the standard restrictions on
> any ordering. See http://en.wikipedia.org/wiki/Total_ordering
>
But antisymmetry means that (x <= y) && (y <= x) ==> x = y, where '=' means
identity. Now what does (should) 'identity' mean?
Depends on the type, I dare say. For e.g. Int, it should mean 'identical bit
pattern', shouldn't it? For IntSet it should mean 'x and y contain exactly
the same elements', the internal tree-structure being irrelevant. But that
means IntSet shouldn't export functions that allow to distinguish (other than
by performance) between x and y.
In short, I would consider code where for some x, y and a function f we have
(x <= y) && (y <= x) [or, equivalently, compare x y == EQ] but f x /= f y
broken indeed.
So for
data Foo = Foo Int (Int -> Int),
an Ord instance via compare (Foo a _) (Foo b _) = compare a b
is okay if Foo is an abstract datatype and outside the defining module it's
guaranteed that
compare (Foo a f) (Foo b g) == EQ implies (forall n. f n == g n), but not if
the data-constructor Foo is exported.
> Thanks
>
> Neil
More information about the Haskell-Cafe
mailing list