Ok, my turn now. Let's think about algorithm that takes equivalence relation EQ, ordering relation ORD on abstraction classes generated by this equivalence ( -> equivalence classes ) and divides given input elements XS into appropriate classes and then prints them out according to given ordering ORD. If we pose the restriction (let's call it (*)), that input XS should have at most one element from every abstraction class, we get sorting in a way that you desire. Hovewer, if we don't pose that restriction the algorithm still makes perfect sense and is given by standard library sortBy. <br>
<br>I see no reason for restriction (*).<br><br><br><br>For efficiency reasons there could be additional class StrictEq. If the type is in that class then we can assume (*) and use more space-efficient algorithm.<br><br>Now, the problem with<br>
<br>treeSort = concatMap (reverse . snd) . Map.toAscList<br>
. Map.fromListWith (++) . map (\x -> (x,[x]))<br>
<br>is that i can't tell any compact way of implementing treeSortBy in nice manner. This is because Data.Map does not allow us to provide our own comparison test instead of compare.<br><br><br><div class="gmail_quote">
On Mon, Mar 10, 2008 at 6<span class="__mozilla-findbar-search" style="padding: 0pt; background-color: yellow; color: black; display: inline; font-size: inherit;">:</span>10 PM, Adrian Hey <<a href="mailto:ahey@iee.org">ahey@iee.org</a>> wrote<span class="__mozilla-findbar-search" style="padding: 0pt; background-color: yellow; color: black; display: inline; font-size: inherit;">:</span><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">Neil Mitchell wrote<span class="__mozilla-findbar-search" style="padding: 0pt; background-color: yellow; color: black; display: inline; font-size: inherit;">:</span><br>
> Hi<br>
><br>
>> We're talking about *semantic correctness*, not efficiency. If you<br>
>> want to fine tune your code like this you shouldn't be relying<br>
>> on overloaded general purpose function implementations. E.G. the<br>
>> COrdering type used by AVL lib is one way to do this. This lets<br>
>> a combining comparison chose which of two "equal" values is used<br>
>> (and other things).<br>
><br>
> I would have thought<span class="__mozilla-findbar-search" style="padding: 0pt; background-color: yellow; color: black; display: inline; font-size: inherit;">:</span><br>
><br>
> sort x == sortBy compare x<br>
><br>
> was a reasonable property to have.<br>
<br>
</div>Certainly, but this is part of (but not the complete) specification<br>
for sortBy, not sort. But given sane Ord/Eq instances and sortBy<br>
implementation, then this is indeed also one of many possible<br>
correct implementatations of sort.<br>
<div class="Ih2E3d"><br>
> But you are proposing that sort<br>
> should make assumptions on the compare function,<br>
<br>
</div>Not just sort, but any function with an Ord constraint is entited<br>
to assume sane behavior wrt to compare. Without this the Ord class<br>
just becomes quite useless, other than saving a few keystrokes for<br>
folk who be bothered to pass any old compare function as explicit arg.<br>
Surely type classes are supposed to be more than that?<br>
<div class="Ih2E3d"><br>
> which you can't even state in Haskell,<br>
<br>
</div>There are plenty of formal statements about things that can't be<br>
written in Haskell. That doesn't mean they aren't true or should not<br>
be respected or relied upon. It just means Haskell is an imperfect<br>
language for expressing such things.<br>
<br>
> but sortBy should not.<br>
<br>
sortBy should not "assume" anything about the function of type<br>
x -> x -> Ordering. Rather, what sortBy actually does with that<br>
function should be specified.<br>
<div class="Ih2E3d"><br>
> I also know of a data type<span class="__mozilla-findbar-search" style="padding: 0pt; background-color: yellow; color: black; display: inline; font-size: inherit;">:</span><br>
><br>
> data Set xs = Set [xs]<br>
><br>
> where the Set constructor is all nicely hidden. If I define Set "ab"<br>
> to be equal to Set "ba", should the compiler burst into flames?<br>
<br>
??<br>
<br>
If we<br>
> _require_ all Eq definitions to follow our very narrowly defined<br>
> notion of equality, then the question comes up why we permit people to<br>
> write Eq at all - why doesn't the compiler just do it for us, if there<br>
> is only one right answer.<br>
<br>
</div>You provided one example yourself..<br>
<div class="Ih2E3d"><br>
data Foo = Foo Int (Int -> Int)<br>
<br>
</div>It's perfectly possible for Foo to be an abstract type exported from<br>
a module that preserves the invariant that the same function is always<br>
associated with a given Int (value).<br>
<br>
If this is the case there's no reason why Foo should not be an instance<br>
of Ord or Eq.<br>
<br>
If this isn't the case then Foo should certainly not be an instance or<br>
either class IMO.<br>
<br>
If this was intended to be the case but in fact isn't the case, then<br>
that's a bug.<br>
<br>
Regards<br>
--<br>
<font color="#888888">Adrian Hey<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<span class="__mozilla-findbar-search" style="padding: 0pt; background-color: yellow; color: black; display: inline; font-size: inherit;">:</span>//www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>