[Haskell-cafe] groupBy without Ord?

[John Lato]

On Mar 31, 2014 5:28 AM, "martin" <martin.drautzburg at web.de> 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.

None of your attempts have addressed the major criticism, I.e. your
algorithm has higher complexity than Ord-based solutions. That doesn't mean
your algorithm won't work well for your use case, but it does mean that it
will work less well for some (many?) use cases.

Have you tried "groupEq [1..1000000::Int]" ?  Is the performance of that
acceptable? Does that impact your use case?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140331/43deb2be/attachment.html>