Python-"is"-like equality operator for Haskell/GHC

12
votes

Is there a GHC-specific "unsafe" extension to ask whether two Haskell references point to the same location?

I'm aware this can break referential transparency if not used properly. But there should be little harm (unless I'm missing something), if it is used very careful, as a means for optimizations by short-cutting recursive (or expensive) data traversal, e.g. for implementing an optimized Eq instance, e.g.:

instance Eq ComplexTree where
   a == b  = (a `unsafeSameRef` b) || (a `deepCompare` b)

providing deepCompare is guaranteed to be true if unsafeSameRef decides true (but not necessarily the other way around).

EDIT/PS: Thanks to the answer pointing to System.Mem.StableName, I was able to also find the paper Stretching the storage manager: weak pointers and stable names in Haskell which happens to have addressed this very problem already over 10 years ago...

4
haskellreferenceghc
I've often wanted exactly this feature, for exactly this purpose: a faster equality check. – Neil Brown
@FUZxxl: if he asks that (and the question indicates quite clearly that he knows what he's talking about), then obviously he needs that. Blaming OP in performing premature optimization without knowing his problem is a bit... premature. – Roman Cheplyaka
@Roman Cheplyaka: Sorry. I don't wanted the comment to be rude, so I've deleted it. – fuz
+1 For perfectly asked question. However, I would trust the compiler to automatically do this optimization for me. Does it not? – Tarrasch
@Tarrasch: no, there are lots of reasons not to do that. Particularly, equality is not quite reflexive, as Lennart Augustsson pointed out in his response. – Roman Cheplyaka

4 Answers

13
votes

GHC's System.Mem.StableName solves exactly this problem.

9
votes

There's a pitfall to be aware of:

Pointer equality can change strictness. I.e., you might get pointer equality saying True when in fact the real equality test would have looped because of, e.g., a circular structure. So pointer equality ruins the semantics (but you knew that).

2
votes

I think StablePointers might be of help here http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/Foreign-StablePtr.html Perhaps this is the kind of solution you are looking for:

import Foreign.StablePtr (newStablePtr, freeStablePtr)
import System.IO.Unsafe (unsafePerformIO)

unsafeSameRef :: a -> a -> Bool
unsafeSameRef x y = unsafePerformIO $ do
    a <- newStablePtr x
    b <- newStablePtr y
    let z = a == b
    freeStablePtr a
    freeStablePtr b
    return z;
2
votes

There's unpackClosure# in GHC.Prim, with the following type:

unpackClosure# :: a -> (# Addr#,Array# b,ByteArray# #)

Using that you could whip up something like:

{-# LANGUAGE MagicHash, UnboxedTuples #-} 
import GHC.Prim

eq a b = case unpackClosure# a of 
    (# a1,a2,a3 #) -> case unpackClosure# b of 
        (# b1,b2,b3 #) -> eqAddr# a1 b1

And in the same package, there's the interestingly named reallyUnsafePtrEquality# of type

reallyUnsafePtrEquality#  :: a -> a -> Int#

But I'm not sure what the return value of that one is - going by the name it will lead to much gnashing of teeth.