[Haskell-cafe] groupBy without Ord?

[martin]

Am 03/24/2014 12:34 AM, schrieb John Lato:> I would keep in mind that, given the constraints
> 
> - you want to group together all equal elements from the entire list 
> - the only operation you can perform on elements is comparison for equality
> 
> your function will have quadratic complexity (at least I can't see any way around it).  If there's any way of
> sorting the elements, even if the order is entirely arbitrary, you should consider it.


Am 03/30/2014 04:12 PM, schrieb Tom Ellis:

> 
> Quicksort is O(n^2) in the worst case.
> 

I just took the sort function from Data.List and replaced all occurences of cmp x == GT by (==) and all others by (/=).
I didn't even bother to understand the algorithm.  What I got is a reordered list where all equal elements are aligned
next to each other. I have no reason to assume that this aligning is more expensive than true sorting. Unlike my naive
quicksort, it has no problem with millions of elements.

But of course it makes little sense to implement an aligning function and then use the native groupBy, when you can
easily roll your own fast groupEq as Brent Yorgey pointed out:

  groupEq :: Eq a => [a] -> [[a]]
  groupEq [] = []
  groupEq (a:rest) = (a:as) : groupEq bs
    where (as,bs) = partition (==a) rest

This one is even a bit faster than my modifed sort. So all in all there seems to be no benefit of sorting the list fist
and asking for (Ord=>) when Eq is sufficient.