[Issue 13595] Extend std.algorithm.groupBy to support non-equivalence relations

via Digitalmars-d-bugs digitalmars-d-bugs at puremagic.com
Tue Nov 4 11:18:48 PST 2014


https://issues.dlang.org/show_bug.cgi?id=13595

hsteoh at quickfur.ath.cx changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |pull

--- Comment #3 from hsteoh at quickfur.ath.cx ---
https://github.com/D-Programming-Language/phobos/pull/2654

Note that the Haskell example is actually wrong, because the Haskell groupBy
function also assumes that the predicate is an equivalence relation. It just so
happens that Haskell's groupBy only assumes transitivity, whereas the original
implementation of std.algorithm.groupBy also assumes reflexivity, which causes
an infinite loop when that assumption fails to hold.

In the above referenced PR, groupBy now defaults to assuming a non-equivalence
relation, meaning that the predicate is evaluated for every pair of adjacent
elements, so the OP's predicate (x,y) => (x*y)%3 == 0 will produce the grouping
[[1], [2,3,4], [5,6,7], [8,9]], because both 2*3 and 3*4 are divisible by 3, as
are 5*6 and 6*7. (Notice that Haskell's groupBy evaluates the predicate against
the first element of the subrange, thus it checks 2*3 and 2*4 instead of 2*3
and 3*4 for the second subrange.)

--


More information about the Digitalmars-d-bugs mailing list