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 <[EMAIL PROTECTED]> wrote: > On 2008-03-11, Adrian Hey <[EMAIL PROTECTED]> 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@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe