> As I understood, the question was if GHC would first compare pointers,
and only call the Eq instance if the pointers are not equal.

Yes, spot on!

> 1. An Eq instance that doesn't obey the reflective property (not recommended):

And this is what I mean with "defined in some funny way". One could consider this optimization(?) only to kick in when GHC generates the instance definition by means of the deriving mechanism. That should be safe(?).

> I think the reason it isn't done is that it's not always an optimization

Could you explain when it's not?


Clarification:

Consider the following:

    let xs = [1..1000] in xs == xs

xs would surely be equal but generally finding out if two lists are equal amounts to comparing each element. If the compiler was first to check if the objects referenced where the same, it should safely be able to yield True without further evaluation. (In this particular example the compiler may make other optimizations but it gives the general idea.)

Ofcourse `let x = undefined in x == x` might be considered bad to optimize to True but maybe this could be checked somehow...





2014-08-20 10:35 GMT+02:00 Michael Snoyman <michael@snoyman.com>:



On Wed, Aug 20, 2014 at 11:28 AM, Johan Tibell <johan.tibell@gmail.com> wrote:
On Wed, Aug 20, 2014 at 10:23 AM, Erik Hesselink <hesselink@gmail.com> wrote:
As I understood, the question was if GHC would first compare pointers,
and only call the Eq instance if the pointers are not equal. I guess
this would be safe, but I don't think GHC does such a thing.

I think the reason it isn't done is that it's not always an optimization. We do it manually in e.g. bytestring.
 


There are two cases I can think of where it would also change the semantics of the code:

1. An Eq instance that doesn't obey the reflective property (not recommended):

data BadEq = BadEq
instance Eq BadEq where
    BadEq == BadEq = False

2. Eq instances intended to avoid timing attacks, by always comparing the entire data structure.

newtype SlowEq a = SlowEq [a]
instance Eq a => Eq (SlowEq a) where
    SlowEq x == SlowEq y = slowAnd $ length x == length y : zipWith (==) x y

slowAnd =
    loop True
  where
    loop !x [] = x
    loop !x (!y:ys) = loop (x && y) ys

(Note: not actually tested.) It's difficult for me to imagine a case though where a timing attack could result on two data structures sharing the same pointer; usually we'd be talking about comparing two ByteStrings or Texts that come from very different sources.

Michael

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe