Looking at the code of nubBy
http://www.haskell.org/ghc/docs/latest/html/libraries/base-4.4.0.0/src/Data-List.html#nubBy
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
_______________________________________________
Haskell-prime mailing list
Haskell-prime@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-prime
