Proposal: make nubBy obey the 98 report semantics

Thomas Miedema thomasmiedema at gmail.com
Tue Sep 23 21:45:00 UTC 2014


The implementation of nubBy in Data.List is as follows, where
USE_REPORT_PRELUDE refers to [1]:

   #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

That comment is actually not correct [2], and the report version and the
base
version don't have the same semantics when used on asymmetric relations:

   MyReportPrelude> nubBy (<) [1]
   [1]

   Data.List> nubBy (<) [1,2]
   [1,2]

## Proposal
Make nubBy and nub obey the report semantics by swapping the arguments to
`eq` in elem_by, and defining nub as nubBy (==). This is the 'still easy'
variant from [3].

## Motivation
The Report's order is more sensible, since the parameters to the relation
stay
in the left-to-right order in which they occurred in the list. See [4,5] for
user bug reports.

Discussion period: 2 weeks
Code review: https://phabricator.haskell.org/D238

[1] https://www.haskell.org/onlinereport/list.html#sect17.6
[2] https://ghc.haskell.org/trac/ghc/ticket/2528
[3] https://ghc.haskell.org/trac/ghc/ticket/7913#comment:3
[4] https://ghc.haskell.org/trac/ghc/ticket/3280
[5] https://ghc.haskell.org/trac/ghc/ticket/7913
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140923/021a2698/attachment.html>


More information about the Libraries mailing list