[Haskell-cafe] groupBy without Ord?
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
More information about the Haskell-Cafe