[GHC] #7913: Argument order not preserved by nubBy
#7913: Argument order not preserved by nubBy -------------------------+-------------------------------------------------- Reporter: paullik | Owner: Type: bug | Status: new Priority: normal | Component: Prelude Version: 7.6.3 | Keywords: nubBy Os: Linux | Architecture: Unknown/Multiple Failure: None/Unknown | Blockedby: Blocking: | Related: -------------------------+-------------------------------------------------- Hello. I recently wanted to know how the element 4 in [2,4] is ruled out by: {{{ nubBy (\x y -> x `mod` y == 0) [2,4] }}} and discussing this on #haskell we discovered that the documentation or the code is buggy. The [http://hackage.haskell.org/packages/archive/base/latest/doc/html/src /Data-List.html#nubBy numBy source] states that ''we keep the call to `eq` with arguments in the same order as in the reference implementation'', which, comparing the following two lines, is not true: {{{ nubBy eq (x:xs) = x : nubBy eq (filter (\ y -> not (eq x y)) xs) elem_by eq y (x:xs) = y `eq` x || elem_by eq y xs }}} Also this is easily proved by defining: {{{ nubBy' eq [] = [] nubBy' eq (x:xs) = x : nubBy' eq (filter (\ y -> not (eq x y)) xs) }}} Then running: {{{ nubBy (\x y -> x `mod` y == 0) [2,4] }}} which yields [2] because of '''eq y x''' and {{{ nubBy' (\x y -> x `mod` y == 0) [2,4] }}} which yields [2,4] because of '''eq x y'''. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7913 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7913: Argument order not preserved by nubBy ---------------------------------+------------------------------------------ Reporter: paullik | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Prelude | Version: 7.6.3 Keywords: nubBy | Os: Linux Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown | Testcase: Blockedby: | Blocking: Related: | ---------------------------------+------------------------------------------ Changes (by simonpj): * difficulty: => Unknown Comment: OK, here is the implementation of `nubBy`, both reference model and actual: {{{ 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 }}} In `nubBy'` the `xs` is the list of all earlier elements that have been accepted into the result list. Indeed when we compare a later item `y` with these, the `y` parameter should be second, as it is in the reference implementation. So if I'm right the fix should be to swap the order of arguments to `eq` in the definition of `elem_by`. And document all this more clearly in the defn of `nubBy`. And if we were paranoid we might do the same thing for `nub`, really, just in case `(==)` isn't symmetrical. Does everyone agree? Easy to do. Would someone like to make a patch? Simon -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7913#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7913: Argument order not preserved by nubBy ---------------------------+------------------------------------------------ Reporter: paullik | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Prelude | Version: 7.6.3 Resolution: duplicate | Keywords: nubBy Os: Linux | Architecture: Unknown/Multiple Failure: None/Unknown | Difficulty: Unknown Testcase: | Blockedby: Blocking: | Related: ---------------------------+------------------------------------------------ Changes (by igloo): * status: new => closed * resolution: => duplicate Comment: This is a duplicate of #2528, which also has some explanation of why things are the way they are now. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7913#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7913: Argument order not preserved by nubBy ---------------------------+------------------------------------------------ Reporter: paullik | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Prelude | Version: 7.6.3 Resolution: | Keywords: nubBy Os: Linux | Architecture: Unknown/Multiple Failure: None/Unknown | Difficulty: Unknown Testcase: | Blockedby: Blocking: | Related: ---------------------------+------------------------------------------------ Changes (by simonpj): * status: closed => new * resolution: duplicate => Comment: I see; I'd missed that. We can do one of two things * Simple: change documentation of the "reference" implementation to reverse order of args to `eq`. But (a) reference impl differs from Report; (b) the back to front code is a bit unintuitive. * Still easy: change the order of args in both `elem_by` ''and'' in `nub`, so that the impl matches the reference impl. This is what #2528 should have done in the first place. Disadvantage: it's a change. * Simplest: do nothing Library folk, what do you want? Simon -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7913#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC