I agree, I view == as some kind of equivalence relation in Haskell, and not a congruence relation (which would force x==y =&gt; f x == f y).<br>Of course, the Haskell type system isn&#39;t strong enough to enforce anything more than it being a function returning a boolean.<br>
<br>&nbsp; -- Lennart<br><br><div class="gmail_quote">On Wed, Mar 12, 2008 at 12:55 AM, Aaron Denney &lt;<a href="mailto:wnoise@ofb.net">wnoise@ofb.net</a>&gt; wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d">On 2008-03-11, Adrian Hey &lt;<a href="mailto:ahey@iee.org">ahey@iee.org</a>&gt; wrote:<br>
&gt; Neil Mitchell wrote:<br>
&gt;&gt; Hi<br>
&gt;&gt;<br>
&gt;&gt;&gt; &nbsp;(sort [a,b]) in the case we have: (compare a b = EQ)<br>
&gt;&gt;&gt;<br>
&gt;&gt;&gt; &nbsp;Which of the following 4 possible results are correct/incorrect?<br>
&gt;&gt;&gt; &nbsp;1- [a,a]<br>
&gt;&gt;&gt; &nbsp;2- [a,b]<br>
&gt;&gt;&gt; &nbsp;3- [b,a]<br>
&gt;&gt;&gt; &nbsp;4- [b,b]<br>
&gt;&gt;<br>
&gt;&gt; Fortunately the Haskell sort is meant to be stable,<br>
&gt;<br>
&gt; I would have said it is meant to be *correct* first and *efficient*<br>
&gt; second. You&#39;re ruling out a whole bunch of possibly more efficient<br>
&gt; and correct sorts on the grounds that they may give observably different<br>
&gt; results for a tiny minority of (IMO broken) Eq/Ord instances.<br>
<br>
</div>It&#39;s exactly your opinion that these are broken that we&#39;re arguing<br>
about. &nbsp;My view is that they are just equivalence and ordering<br>
relations, not complete equality relations. &nbsp;Using sortBy, or wrapping<br>
in a newtype with a different ordering instance and then using sort<br>
should be equivalent.<br>
<div class="Ih2E3d"><br>
&gt; Wrt to *sortBy* (vs. *sort*), I would be inclined to agree with you.<br>
&gt; I sure hope someone has proven that the (apparently) different sortBy<br>
&gt; implementations provided by ghc,nhc and h98 library report are precisely<br>
&gt; equivalent for all (type legal) function arguments.<br>
</div><div class="Ih2E3d">&gt;&gt; and sorting is<br>
&gt;&gt; meant to be a permutation, so we happily have the situation where this<br>
&gt;&gt; has a correct answer: 2.<br>
&gt;<br>
&gt;&gt; Anything else is incorrect.<br>
&gt;<br>
&gt; Isn&#39;t 3 also a permutation? Why is it incorrect?<br>
<br>
</div>Stability -- &nbsp;see &quot;Fortunately the Haskell sort is meant to be stable,&quot; above.<br>
<div class="Ih2E3d"><br>
&gt;&gt; Adrian: I think its fairly clear we disagree about these things.<br>
&gt;&gt; However, we both understand the others point of view, so I guess its<br>
&gt;&gt; just a question of opinion - and I doubt either of us will change. As<br>
&gt;&gt; such I think any further discussion may just lead to sleep deprivation<br>
&gt;&gt; [1]. I think I&#39;m coming from a more discrete maths/theoretical<br>
&gt;&gt; background while you are coming from a more practical/pragmatist<br>
&gt;&gt; background.<br>
&gt;<br>
&gt; If the &quot;discrete maths/theoretical&quot; POV necessatates to the kind of<br>
&gt; biasing madness of Data.Map/Set (for example) then it *sucks* bigtime<br>
&gt; IMO :-)<br>
<br>
<br>
</div><div class="Ih2E3d">&gt; Having tried this approach myself too (with the clone) I can confirm<br>
&gt; that *this way lies madness*, so in future I will not be making<br>
&gt; any effort to define or respect &quot;sane&quot;, unambiguous and stable behaviour<br>
&gt; for &quot;insane&quot; Eq/Ord instances for any lib I produce or hack on. Instead<br>
&gt; I will be aiming for correctness and optimal efficiency on the<br>
&gt; assumption that Eq and Ord instances are sensible.<br>
<br>
</div>Good. &nbsp;But sensible only means that the Eq and Ord instances agree, not that<br>
x == y =&gt; f x == f y.<br>
<font color="#888888"><br>
--<br>
Aaron Denney<br>
-&gt;&lt;-<br>
</font><div><div></div><div class="Wj3C7c"><br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>