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
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.
#ifdef USE_REPORT_PRELUDE
elem x = any (== x)
notElem x = all (/= x)
#else
elem _ [] = False
elem x (y:ys) = x==y || elem x ys
notElem _ [] = True
notElem x (y:ys)= x /= y && notElem x ys
#endif
So the proposal should be to swap the arguments in "x==y" and "x /= y"
(above) which would also fix the nub implementation!
C.
Am 20.09.2011 13:46, schrieb Christian Maeder:
> 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-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
More information about the Haskell-prime
mailing list