Generalize groupBy in a useful way?
wnoise at ofb.net
Fri Sep 5 21:43:01 EDT 2008
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],] from the standard library
> 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
> 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...
More information about the Libraries