[Haskell-cafe] groupBy without Ord?

[Brent Yorgey]

On Sat, Mar 22, 2014 at 05:51:55PM +0100, martin 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?

Well, you can just call groupBy on it. =) But I assume you mean that
you still want to group together all equal elements.  You could do
something like

  groupEq [] = []
  groupEq (a:rest) = (a:as) : groupEq bs
    where (as,bs) = partition (==a) rest

and you could easily generalize it to take a binary predicate, like groupBy, as well.

If you want to get a little fancier and avoid the explicit recursion,
you can use Data.List.Split.chop (from the 'split' package), which
provides a generic way of recursively processing a list:

  chop :: ([a] -> (b,[a])) -> [a] -> [b]

like so:

  import Data.List.Split (chop)
  import Control.Arrow (first)

  groupEq = chop (\(a:rest) -> first (a:) (partition (==a) rest))

-Brent