[Haskell-cafe] groupBy without Ord?

martin martin.drautzburg at web.de
Mon Mar 31 09:27:47 UTC 2014

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?

More information about the Haskell-Cafe mailing list