Looking at the old tickets http://hackage.haskell.org/trac/ghc/ticket/2528 http://hackage.haskell.org/trac/ghc/ticket/3280 the USE_REPORT_PRELUDE version of nub is also different from the implementation, but both variants fulfill "nub = nubBy (==)" (the prelude version by definition). So when we change the nubBy implmentation we also need to change the nub implementation (which is more difficult, because it uses "elem"). Cheers Christian Am 20.09.2011 12:59, schrieb Christian Maeder:
Looking at the code of nubBy http://www.haskell.org/ghc/docs/latest/html/libraries/base-4.4.0.0/src/Data-...
nubBy :: (a -> a -> Bool) -> [a] -> [a] #ifdef USE_REPORT_PRELUDE nubBy eq [] = [] nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs) #else nubBy eq l = nubBy' l [] where nubBy' [] _ = [] nubBy' (y:ys) xs | elem_by eq y xs = nubBy' ys xs | otherwise = y : nubBy' ys (y:xs)
-- Not exported: -- Note that we keep the call to `eq` with arguments in the -- same order as in the reference implementation -- 'xs' is the list of things we've seen so far, -- 'y' is the potential new element elem_by :: (a -> a -> Bool) -> a -> [a] -> Bool elem_by _ _ [] = False elem_by eq y (x:xs) = y `eq` x || elem_by eq y xs #endif
I see that the USE_REPORT_PRELUDE version corresponds to your proposal, but the actual implementation (based on elem_by) behaves differently despite the "same order" comment!
Therefore I support your proposal to change "y `eq` x" in elem_by (and possibly improve the documentation).
Cheers Christian
Am 08.09.2011 02:07, schrieb Cale Gibbard:
I just tried this in ghci-7.0.3:
ghci> nubBy (>=) [1,2,3,4] [1]
Think about what this is doing: it is excluding 2 from the list because 2>= 1, rather than including it because 1>= 2 fails.
I think an important convention when it comes to higher order functions on lists is that to the extent which is possible, the function parameters take elements from the list (or things computed from those) in the order in which they occur in the original list.
If we reimplement it in the obvious way: ghci> let nubBy f [] = []; nubBy f (x:xs) = x : filter (not . f x) (nubBy f xs) ghci> nubBy (>=) [1,2,3,4] [1,2,3,4]
I'm aware that the Report (strangely!) explicitly leaves the behaviour of nubBy unspecified for functions which are not equivalence relations, but the behaviour given by the Report implementation (the opposite of the current behaviour in GHC) is useful and desirable nonetheless.
I'm sure I've written about this before. I'm not entirely sure what happened to the previous thread of discussion about this, but it just came up again for me, and I decided that I was sufficiently irritated by it to post again.
Another thing perhaps worth pointing out is that the parameters to mapAccumR have always been backwards (compare it with foldr). Few enough people use this function that I'm fairly sure we could just change it without harm.
- Cale