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

[Krzysztof Skrzętnicki]

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.


I see no reason for restriction (*).



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.

Now, the problem with

treeSort = concatMap (reverse . snd) . Map.toAscList
             . Map.fromListWith (++) . map (\x -> (x,[x]))

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.


On Mon, Mar 10, 2008 at 6:10 PM, Adrian Hey <ahey at iee.org> wrote:

> Neil Mitchell wrote:
> > Hi
> >
> >>  We're talking about *semantic correctness*, not efficiency. If you
> >>  want to fine tune your code like this you shouldn't be relying
> >>  on overloaded general purpose function implementations. E.G. the
> >>  COrdering type used by AVL lib is one way to do this. This lets
> >>  a combining comparison chose which of two "equal" values is used
> >>  (and other things).
> >
> > I would have thought:
> >
> > sort x == sortBy compare x
> >
> > was a reasonable property to have.
>
> Certainly, but this is part of (but not the complete) specification
> for sortBy, not sort. But given sane Ord/Eq instances and sortBy
> implementation, then this is indeed also one of many possible
> correct implementatations of sort.
>
> > But you are proposing that sort
> > should make assumptions on the compare function,
>
> Not just sort, but any function with an Ord constraint is entited
> to assume sane behavior wrt to compare. Without this the Ord class
> just becomes quite useless, other than saving a few keystrokes for
> folk who be bothered to pass any old compare function as explicit arg.
> Surely type classes are supposed to be more than that?
>
> > which you can't even state in Haskell,
>
> There are plenty of formal statements about things that can't be
> written in Haskell. That doesn't mean they aren't true or should not
> be respected or relied upon. It just means Haskell is an imperfect
> language for expressing such things.
>
> > but sortBy should not.
>
> sortBy should not "assume" anything about the function of type
> x -> x -> Ordering. Rather, what sortBy actually does with that
> function should be specified.
>
> > I also know of a data type:
> >
> > data Set xs = Set [xs]
> >
> > where the Set constructor is all nicely hidden. If I define Set "ab"
> > to be equal to Set "ba", should the compiler burst into flames?
>
> ??
>
>  If we
> > _require_ all Eq definitions to follow our very narrowly defined
> > notion of equality, then the question comes up why we permit people to
> > write Eq at all - why doesn't the compiler just do it for us, if there
> > is only one right answer.
>
> You provided one example yourself..
>
> data Foo = Foo Int (Int -> Int)
>
> It's perfectly possible for Foo to be an abstract type exported from
> a module that preserves the invariant that the same function is always
> associated with a given Int (value).
>
> If this is the case there's no reason why Foo should not be an instance
> of Ord or Eq.
>
> If this isn't the case then Foo should certainly not be an instance or
> either class IMO.
>
> If this was intended to be the case but in fact isn't the case, then
> that's a bug.
>
> Regards
> --
> Adrian Hey
>
> _______________________________________________
> 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/20080310/19ad4433/attachment.htm