[Haskell-cafe] Re: (flawed?) benchmark : sort

[Lennart Augustsson]

I agree, I view == as some kind of equivalence relation in Haskell, and not
a congruence relation (which would force x==y => f x == f y).
Of course, the Haskell type system isn't strong enough to enforce anything
more than it being a function returning a boolean.

  -- Lennart

On Wed, Mar 12, 2008 at 12:55 AM, Aaron Denney <wnoise at ofb.net> wrote:

> On 2008-03-11, Adrian Hey <ahey at iee.org> wrote:
> > Neil Mitchell wrote:
> >> Hi
> >>
> >>>  (sort [a,b]) in the case we have: (compare a b = EQ)
> >>>
> >>>  Which of the following 4 possible results are correct/incorrect?
> >>>  1- [a,a]
> >>>  2- [a,b]
> >>>  3- [b,a]
> >>>  4- [b,b]
> >>
> >> Fortunately the Haskell sort is meant to be stable,
> >
> > I would have said it is meant to be *correct* first and *efficient*
> > second. You're ruling out a whole bunch of possibly more efficient
> > and correct sorts on the grounds that they may give observably different
> > results for a tiny minority of (IMO broken) Eq/Ord instances.
>
> It's exactly your opinion that these are broken that we're arguing
> about.  My view is that they are just equivalence and ordering
> relations, not complete equality relations.  Using sortBy, or wrapping
> in a newtype with a different ordering instance and then using sort
> should be equivalent.
>
> > Wrt to *sortBy* (vs. *sort*), I would be inclined to agree with you.
> > I sure hope someone has proven that the (apparently) different sortBy
> > implementations provided by ghc,nhc and h98 library report are precisely
> > equivalent for all (type legal) function arguments.
> >> and sorting is
> >> meant to be a permutation, so we happily have the situation where this
> >> has a correct answer: 2.
> >
> >> Anything else is incorrect.
> >
> > Isn't 3 also a permutation? Why is it incorrect?
>
> Stability --  see "Fortunately the Haskell sort is meant to be stable,"
> above.
>
> >> Adrian: I think its fairly clear we disagree about these things.
> >> However, we both understand the others point of view, so I guess its
> >> just a question of opinion - and I doubt either of us will change. As
> >> such I think any further discussion may just lead to sleep deprivation
> >> [1]. I think I'm coming from a more discrete maths/theoretical
> >> background while you are coming from a more practical/pragmatist
> >> background.
> >
> > If the "discrete maths/theoretical" POV necessatates to the kind of
> > biasing madness of Data.Map/Set (for example) then it *sucks* bigtime
> > IMO :-)
>
>
> > Having tried this approach myself too (with the clone) I can confirm
> > that *this way lies madness*, so in future I will not be making
> > any effort to define or respect "sane", unambiguous and stable behaviour
> > for "insane" Eq/Ord instances for any lib I produce or hack on. Instead
> > I will be aiming for correctness and optimal efficiency on the
> > assumption that Eq and Ord instances are sensible.
>
> Good.  But sensible only means that the Eq and Ord instances agree, not
> that
> x == y => f x == f y.
>
> --
> Aaron Denney
> -><-
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080312/fdb0ce95/attachment.htm