[Haskell-cafe] groupBy without Ord?

martin martin.drautzburg at web.de
Sun Mar 30 14:06:24 UTC 2014

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). 

Wouldn't a modified quicksort give n*log(n) complexity. Something like:

groupEq [] = []
groupEq (x:xs) = (groupEq a) ++ [x] ++ (groupEq b)
            a = filter (==x) xs
            b = filter (/= x) xs

This is indeed much slower than the built-in sort, but it slower too whern I replace "==" with ">", resulting in a
texbook quicksort.

More information about the Haskell-Cafe mailing list