Please apply the comparison function given to nubBy to elements of the list in the order in which they occur in the list.
Christian.Maeder at dfki.de
Tue Sep 20 14:19:25 CEST 2011
Apologies for responding to myself, but the difference between the
REPORT_PRELUDE and the ghc implementation also applies to elem and notElem.
elem x = any (== x)
notElem x = all (/= x)
elem _  = False
elem x (y:ys) = x==y || elem x ys
notElem _  = True
notElem x (y:ys)= x /= y && notElem x ys
So the proposal should be to swap the arguments in "x==y" and "x /= y"
(above) which would also fix the nub implementation!
Am 20.09.2011 13:46, schrieb Christian Maeder:
> Looking at the old tickets
> 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
>> 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)
>> nubBy eq l = nubBy' l 
>> 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
>> 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]
>>> 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]
>>> 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
>>> 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
More information about the Haskell-prime