[Haskell-cafe] Re: (flawed?) benchmark : sort
David Menendez
dave at zednenem.com
Wed Mar 12 22:28:26 EDT 2008
On Wed, Mar 12, 2008 at 7:48 PM, <ajb at spamcop.net> wrote:
> Adrian Hey wrote:
>
> >> This might be a reasonable thing to say about *sortBy*, but not sort
> >> as the ordering of equal elements should not be observable (for any
> >> correct instance of Ord). It should be impossible to implement a
> >> function which can discriminate between [a,a],[a,b],[b,a],[b,b] if
> >> compare a b = EQ.
>
> Nonsense. Consider a Schwartzian transform wrapper:
>
> data OrdWrap k v = OrdWrap k v
>
> instance (Ord k) => Ord (OrdWrap k v) where
> compare (OrdWrap k1 v1) (OrdWrap k2 v2) = OrdWrap k1 k2
>
> It would be incorrect (and not sane) for sort [a,b] to return [a,a] in
> this case, though a case could be made that either [a,b] or [b,a] make
> sense.
Adrian is arguing that compare a b == EQ should imply compare (f a) (f
b) == EQ for all functions f (excluding odd stuff). Thus, the problem
with your example would be in the Ord instance, not the sort function.
--
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>
More information about the Haskell-Cafe
mailing list