Am 03/22/2014 06:40 PM, schrieb Kim-Ee Yeoh:

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

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

If you take a look at the code for groupBy:

groupBy :: (a -> a -> Bool) -> [a] -> [[a]] groupBy _ [] = [] groupBy eq (x:xs) = (x:ys) : groupBy eq zs

Cool! I have a database background and the SQL "group by" does of course not assume any ordering. So I often wonder, where you would use Haskell's groupBy WITHOUT sorting first, but I assume there are situations, where this is useful.

On Sun, Mar 23, 2014 at 1:29 AM, martin wrote:

So I often wonder, where you would use Haskell's groupBy WITHOUT sorting first, but I assume there are situations, where this is useful.

But if you sorted first, then there must be an Ord-er on the elements, yes? In which case you could then apply (sqlGroup = group . sort) as originally desired. I'm sure groupBy is useful standalone (dim memories of some functional pearl) but your hunch is right in that I normally use it after a sorting step. -- Kim-Ee

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

On Sun, Mar 30, 2014 at 04:06:24PM +0200, martin wrote:

Am 03/24/2014 12:34 AM, schrieb John Lato:

...

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).

Wouldn't a modified quicksort give n*log(n) complexity. Something like:

Quicksort is O(n^2) in the worst case.

Am 03/24/2014 12:34 AM, schrieb John Lato:> 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.

Am 03/30/2014 04:12 PM, schrieb Tom Ellis:

Quicksort is O(n^2) in the worst case.

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 next to each other. I have no reason to assume that this aligning is more expensive than true sorting. Unlike my naive quicksort, it has no problem with millions of elements. 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 one is even a bit faster than my modifed sort. So all in all there seems to be no benefit of sorting the list fist and asking for (Ord=>) when Eq is sufficient.

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. But I still have trouble to believe, that sorting (Ord=>) is cheaper than aligning (Eq=>) because sorting does aligning plus some more. Does (Ord=>) make life so much easier, or why do you think this is the case?

Hi, martin wrote:

But I still have trouble to believe, that sorting (Ord=>) is cheaper than aligning (Eq=>) because sorting does aligning plus some more. Does (Ord=>) make life so much easier [...]?

Yes, it does. For example, if you know that x < y and you know that y < z, you immediately also know that x < z without having to call (<) a third time. But if you know that x /= y and you know that y /= z, you don't know anything about whether x /= z or not. To learn this, you have to call (/=) a third time. Many sorting algorithms exploit this by cleverly comparing elements in such an order that no matter how they compare, we get to safe some of the calls to (<). This situation is typical in programming: A seemingly harder problem can be easier to solve than an seemingly easier variant, because partial solutions of the seemingly harder problem contain more information than partial solutions of the seemingly easier variant of the problem. In this case, the partial solutions are the results of x < y and y < z, and if they are both true, they contain enough information to also know x < z without computing anything. So if you cannot solve a problem, sometimes you have to make it harder in order to make it easier. Tillmann

On Sun, Mar 30, 2014 at 9:06 PM, martin wrote:

groupEq (x:xs) = (groupEq a) ++ [x] ++ (groupEq b) where a = filter (==x) xs b = filter (/= x) xs

Why the need to recurse on "a"? It's a list of identical elements! -- Kim-Ee