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