[Haskell-cafe] nubBy seems broken in recent GHCs

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Sat Jun 6 12:39:50 EDT 2009


Cale Gibbard wrote:
> 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]

Interesting. This was changed in response to

    http://hackage.haskell.org/trac/ghc/ticket/2528

| Tue Sep  2 11:29:50 CEST 2008  Simon Marlow <marlowsd at gmail.com>
|   * #2528: reverse the order of args to (==) in nubBy to match nub
|   This only makes a difference when the (==) definition is not
|   reflexive, but strictly speaking it does violate the report definition
|   of nubBy, so we should fix it.

It turns out that 'elem' differs from the report version and should
have its comparison reversed. Of course that would only ever matter
for broken Eq instances.

However, the report also states that the nubBy function may assume that
the given predicate defines an equivalence relation.

    http://haskell.org/onlinereport/list.html#sect17.6

So I'm not sure there's anything to be fixed here - although backing
out the above patch probably won't hurt anybody.

Bertram


More information about the Haskell-Cafe mailing list