While working on a fun math/programming exercise I discovered a peculiar behavior in "nub". While it worked the vast majority of the time, there were a few cases where it failed to purge all duplicates as defined by (==). Replacing the use of "nub" with "nubBy (==)" correctly purged all cases.
I would have isolated the bug better for you, but like I say nub works by far the majority of the time. This must be a peculiar clash with my custom data structures and strange definition of (==).
Cheers.
Trac metadata
Trac field
Value
Version
6.8.2
Type
Bug
TypeOfFailure
OtherFailure
Priority
normal
Resolution
Unresolved
Component
Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture
Unknown
Edited
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Child items
0
No child items are currently assigned. Use child items to break down this issue into smaller parts.
Linked items
0
Link issues together to show that they're related or that one is blocking others.
Learn more.
There may be other bugs as well, that is just the first instance I found. nubBy (==) will break as well, you just have not seen it yet.
All instances of Eq must be transitive, reflexive, symmetric, and antisymmetric. Haskell can't automatically check this for you -- so it is left up the developer to do, either by formal proof, or by unit testing.
Well there still seems to be a problem, considering the what the library docs say about nubBy..
"The 'nubBy' function behaves just like 'nub', except it uses a user-supplied equality predicate instead of the overloaded '==' function."
.and nub was indeed originally defined as,..
nub=nubBy compare
.as is the local nub in the example.
So right or wrong, shouldn't we see the same result in each case? Here's the source of the problem I think:
elem_by :: (a -> a -> Bool) -> a -> [a] -> Boolelem_by _ _ [] = Falseelem_by eq y (x:xs) = x `eq` y || elem_by eq y xs
vs.
elem _ [] = Falseelem x (y:ys) = x==y || elem x ys
Also, where does the H98 report say all instances of Eq must be transitive, reflexive, symmetric, and antisymmetric? It just says "The Eq class provides equality (==)..", whatever that might mean :-)
Jeremy is correct: I forgot a case in my definition of (==) that makes it not completely symmetric for second layer commutative equivalence (oops).
The relevant demonstration for the example case that failed in the linked codepaste is:
*Main> let a = Branch (Branch (Leaf (Just 9)) Add (Leaf (Just 9))) Add (Leaf (Just 2)) *Main> let b = Branch (Leaf (Just 9)) Add (Branch (Leaf (Just 9)) Add (Leaf (Just 2))) *Main> a == b True *Main> b == a False *Main> List.nubBy (==) [a,b] [((9+9)+2)] *Main> List.nub [a,b] [((9+9)+2),(9+(9+2))]
I guess the lack of symmetry in (==) causes the difference in behavior, which makes more sense to me now.
However, Adrian is also correct, the difference in behavior between "nub" and "nubBy (==)" is what startled me. I would have found the bug in my code eventually (especially after unit testing).
Well there still seems to be a problem, considering the what the library docs say about nubBy..
hrm, interesting. I am guessing that even with 'valid' Eq instances that could be important due to laziness and bottom?
Also, where does the H98 report say all instances of Eq must be transitive, reflexive, symmetric, and antisymmetric? It just says "The Eq class provides equality (==)..", whatever that might mean :-)
Well, it does not say it explicitly, but I suspect H98's usage of Eq implicitly demands those laws be followed. Hopefully in Haskell' the laws will not only be stated, but there will be some QuickCheck-style properties you can use to test your own instances ;)