On 2008-09-05, Bart Massey
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 -><-