Generalize groupBy in a useful way?

[Aaron Denney]

On 2008-09-05, Bart Massey <bart at cs.pdx.edu> 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
-><-