I think that nubBy
requires the binary boolean operation to be an equivalence relation.
This is roughly in the same spirit of sortBy
requiring a preorder relation (reflexive & transitive). If this requirement is invalidated, then quicksort and mergesort become non equivalent algorithms. The intent of the Haskell report is instead to allow an implementation to use any of them (or another correct sorting algorithm).
Similarly, if the nubBy
comparison is allowed being a non-equivalence, the implementation is unnecessarily constrained to use exactly the reference Prelude
algorithm, preventing the use of a more efficient alternative.
To be honest, the exact requirements on the operators passed to the "...By" are not always obvious. For instance the documentation of sortBy seems to guarantee correctness only for total orderings, albeit I expect the actual implementation will also work for a larger class of orderings, provided the result is interpreted up-to the equivalence induced by the ordering.
The documentation for nubBy simply states that the first argument is a "user-supplied equality predicate". So, it is only guaranteed for equality, and not for arbitrary equivalences.
However, my feeling is that if its implementation works for equality, it has to work also for equivalences (provided the result is read up-to, of course). This might indeed be provable by exploiting the "free theorem" associated to the nubBy
type. My lack of expertise with parametricity betrays me here :)