[Haskell-cafe] groupBy without Ord?

[Tom Ellis]

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