nubBy seems broken in recent GHCs
Cale Gibbard
cgibbard at gmail.com
Sat Jun 6 01:21:45 EDT 2009
According to the Report:
nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy eq [] = []
nubBy eq (x:xs) = x : nubBy eq (filter (\y -> not (eq x y)) xs)
Hence, we should have that
nubBy (<) (1:2:[])
= 1 : nubBy (<) (filter (\y -> not (1 < y)) (2:[]))
= 1 : nubBy (<) []
= 1 : []
However in ghc-6.10.3:
Prelude Data.List> nubBy (<) [1,2]
[1,2]
The order of the parameters to the function which is passed to nubBy
is *important* since the function might not be an equivalence
relation. nubBy is more generally useful for sieving even when the
relation is not symmetric. groupBy, for a similar reason, has
applications for grouping beyond those provided by equivalence
relations, and I think we should be able to rely on its behaviour.
Moreover, I contend that the Report's order is more sensible, since
the parameters to the relation stay in the left-to-right order in
which they occurred in the list. It would be good if this could get
fixed for 6.10.4.
- Cale
PS: There is actually another implementation of groupBy which would
*also* be useful to have, but which is exactly the same for
equivalence relations as groupBy, and it compares adjacent elements
rather than the first element of a group with successive ones.
(groupByAdjacent or something would be a reasonable name.)
An implementation of it can be found here:
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5595
More information about the Libraries
mailing list