[Haskell-cafe] groupBy without Ord?

[Tom Ellis]

On Mon, Mar 31, 2014 at 11:27:47AM +0200, martin wrote:
> Am 03/30/2014 11:15 PM, schrieb Tom Ellis:
> >>  groupEq :: Eq a => [a] -> [[a]]
> >>  groupEq [] = []
> >>  groupEq (a:rest) = (a:as) : groupEq bs
> >>    where (as,bs) = partition (==a) rest
> > 
> > This is O(n^2).
> 
> I understood, that you suggested to go ahead and sort the list, instead of just aligning equal elements next to each
> other. So far all my attempts to prove you wrong failed.
> 
> But I still have trouble to believe, that sorting (Ord=>) is cheaper than aligning (Eq=>) because sorting does aligning
> plus some more. Does (Ord=>) make life so much easier, or why do you think this is the case?

An Ord instance is a total order on your datatype and gives you extra
properties to work.  Seemingly these properties help a lot!

However, I'm not sure I'd say sorting does "aligning plus some more". 
Depending on what you want to do, sorting might be seen as "aligning minus
some".  When sorting, the whole collection comes out in sorted order not
just in grouped blocks.  That is, the range of a sorting function is
strictly smaller (exponentially smaller I guess) than the range of a
grouping function.  Thus sorting loses a lot of information.

Tom