Yes, that's a good point. I think nub should be defined as nubBy (==), not as nubBy (not . (/=)). I'll make it consistently so. Simon | -----Original Message----- | From: Janis Voigtlaender [mailto:voigt@orchid.inf.tu-dresden.de] | Sent: 04 January 2002 11:07 | To: haskell@haskell.org | Subject: Report Issues | | | Simon Peyton-Jones wrote: | > | > Folks, | > | > You have all been eating too much Xmas pudding. Only one | > Haskell98 Report issue has arisen since my release of 21 Dec. | | OK, here comes a rather trivial issue regarding the libraries: | | Section 7.6 of the Library Report gives the following example | definition of nub: | | nub :: (Eq a) => [a] -> [a] | nub [] = [] | nub (x:xs) = x : nub (filter (\y -> x /= y) xs) | | But then, in Section 7.9, the following actual implementation | is given: | | nub :: Eq a => [a] -> [a] | nub = nubBy (==) | | nubBy :: (a -> a -> Bool) -> [a] -> [a] | nubBy eq [] = [] | nubBy eq (x:xs) = x : nubBy eq (filter (\y -> not | (eq x y)) xs) | | The two definitions are only equivalent, if for all x and y | holds that | (x /= y) | and | (not (x == y)) | are equivalent. | While this is true for all basic types, and is also true for | user defined instances of Eq, if the programmer specifies | only one of the two functions (==) or (/=) and leaves the | other one at the default method, nobody can prevent me from | writing an instance declaration where I define (==) and (/=) | without adhering to the duality. This might be stupid to do, | but still it contradicts the report, right? | | Janis. | | | -- | Janis Voigtlaender | http://wwwtcs.inf.tu-dresden.de/~voigt/ | mailto:voigt@tcs.inf.tu-dresden.de | | _______________________________________________ | Haskell mailing list | Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell |
What, by the way, is the rationale behind including /= in the Eq class in the first place? Since /= is intended to be semantically equivalent to \x y -> not (x == y), the only plausible reason for making it overloaded is optimization. But an optimized implementation of /= can at most be two "not":s faster than just using not and ==, so the performance benefits seem quite minimal here. This is nothing compared to, say, Monad.>>, where an optimized implementation can be quite a lot faster than the default one that uses >>=. So as far as I see, the overloadability of /= is just a source of subtle errors, when the implementation doesn't follow the expected (but non-language-enforceable) semantics. Lauri Alanko la@iki.fi
I don't know if this is an "appropriate" use of overloading both == and /=, but I've done something like the following:
data T a = T a | U (a -> Int)
instance Eq a => Eq (T a) where (T a) == (T a') = a == a' (U _) == (U _ ) = False (T a) /= (T a') = a /= a' (U _) /= (U _ ) = False
This probably isn't "good", but it suited my purposes. I agree in general, though, I don't think /= should be in the class, even though I've capitalized on it. - Hal -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On Fri, 4 Jan 2002, Lauri Alanko wrote:
What, by the way, is the rationale behind including /= in the Eq class in the first place?
Since /= is intended to be semantically equivalent to \x y -> not (x == y), the only plausible reason for making it overloaded is optimization. But an optimized implementation of /= can at most be two "not":s faster than just using not and ==, so the performance benefits seem quite minimal here. This is nothing compared to, say, Monad.>>, where an optimized implementation can be quite a lot faster than the default one that uses >>=.
So as far as I see, the overloadability of /= is just a source of subtle errors, when the implementation doesn't follow the expected (but non-language-enforceable) semantics.
Lauri Alanko la@iki.fi
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
participants (3)
-
Hal Daume III -
Lauri Alanko -
Simon Peyton-Jones