[Haskell-cafe] groupBy without Ord?
tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk
Sun Mar 30 21:15:56 UTC 2014
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).
More information about the Haskell-Cafe