Re: [Haskell-cafe] groupBy without Ord?

Hi, Have you considered using a "dictionary" of key-value pairs to group the elements? HashTable requires only Eq and a hash function but no Ord. First insert all element into the hashtable and them iterate over the keys in the hashtable where you can find all elements per group. You could tests whether the (somewhat constant) overhead of the hashtable is significant in your use cases. On second thought, this might introduce an overloading dependency on the Hash class/function. Maybe you know something about the key type such that this dependency can be resolved elsewhere? kind regards, Arjen. On 03/24/2014 12:34 AM, John Lato wrote:

I would keep in mind that, given the constraints

- you want to group together all equal elements from the entire list - the only operation you can perform on elements is comparison for equality

your function will have quadratic complexity (at least I can't see any way around it). If there's any way of sorting the elements, even if the order is entirely arbitrary, you should consider it.

John L.

On Sat, Mar 22, 2014 at 9:51 AM, martin mailto:martin.drautzburg@web.de> wrote:

Hello all,

when I groupBy a list in order to cluster elements which satisfy some sort of equality, I usually have to sort the list first, which requires Ord. However groupBy itself does not require Ord, but just Eq.

How can I groupBy a List whose elements are only instances of Eq but not of Ord?

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe