Generalize groupBy in a useful way?

Aaron Denney wnoise at
Fri Sep 5 21:43:01 EDT 2008

On 2008-09-05, Bart Massey <bart at> wrote:
> I experienced some interesting behavior with groupBy
> tonight, and thought I'd run it by folks as a proposal for
> the Haskell libraries.
> Consider the predicate
>     incp e1 e2 = e1 + 1 == e2
> Naively, one might expect
>     groupBy incp [2,3,4,5,6] == [[2,3,4,5,6]]
> but one actually gets [[2,3],[4,5],[6]] from the standard library
> implementation.
> The Haskell98 Report makes it clear that
>    "When the 'By' function replaces an Eq context by a
>     binary predicate, the predicate is assumed to define an
>     equivalence."
> Thus, the observed behavior is technically correct, or at
> least technically not incorrect.  The incp predicate does
> not follow the equivalence laws (it is neither symmetric nor
> reflexive), so groupBy is probably permitted to return most
> any result of the correct type.  What is actually happening
> is that the groupBy implementation is using span with a
> predicate (incp a) where a is the first element in the list.

If the comparison can be expensive on the first element, this
allows the possibility of caching some of that computation by
constructing a function that does the comparison.

I admit this is unlikely...

Aaron Denney

More information about the Libraries mailing list