[Haskell-cafe] groupBy without Ord?

[Arjen]

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 <martin.drautzburg at web.de
> <mailto:martin.drautzburg at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>