On Sun, Mar 30, 2014 at 10:50:54PM +0200, martin wrote:
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
Data.List.sort is a merge sort and the merge phase of this will not carry over to a correct 'groupBy'. Please check your implementation again!
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 is O(n^2). Tom