Data.List.groupBy with non-transitive equality predicate

[Ross Paterson]

On Wed, Aug 29, 2007 at 10:02:53PM +0200, Henning Thielemann wrote:
>  I assumed that 'groupBy' would compare adjacent elements, but it seems to
> compare the leading element of each block with subsequent elements. Since
> the documentation doesn't tell which elements are actually compared it
> seems to assume that the comparison is commutative and transitive. Maybe
> this point should be made clearer.
>  Additionally I think that comparing neighbouring elements is a useful
> behaviour and I suggest an according variant of 'groupBy' for Data.List.
> Opinions?

This has come up a few times now.

The Haskell 98 Report says that the argument function is assumed to
define an equivalence.  For such arguments, the definition given in
the Report (comparing with the leading element) is equivalent to a
definition comparing adjacent elements, like:

        groupBy rel []          =  []
        groupBy rel (x:xs)      =  (x:ys) : groupBy rel zs
          where (ys,zs) = groupByAux x xs
                groupByAux x0 (x:xs) | rel x0 x = (x:ys, zs)
                  where (ys,zs) = groupByAux x xs
                groupByAux y xs = ([], xs)

But the latter definition is also useful for other relations, e.g.
groupBy (<=) would produce the list of "runs".  So I'd suggest that
changing the reference definition of groupBy, and removing the restriction,
would be an improvement, but still compatible with Haskell 98.  The same
goes for nubBy.