[Haskell-cafe] Efficient object identity (aka symbols as data)

[Jacek Generowicz]

On 2011 May 26, at 11:12, Brandon Allbery wrote:

> On Thu, May 26, 2011 at 04:45, Jacek Generowicz <jacek.generowicz at cern.ch 
> > wrote:
> What is the Haskell approach to efficient comparison and lookup of  
> objects by their identity?
>
> ghc uses Data.Unique to generate unique internal identifiers to  
> associate with things.

At first blush it sounds like the sort of thing I'm after. Thanks.

> (Think gensym.  Hm, except last time I did anything serious with  
> Lisp, it was Maclisp... does gensym even still exist, or did CL do  
> something inscrutable with it?)

CL has gensym.

But gensym does seem to be overkill in the case I presented.

I *could*, for example, say

data Person = Fred | Johnny | Sally | Belinda | Kate | Roger | Eric  
[... and so on for a few squillion ...]
data Group = Amazing | Brilliant | Cool | Great | Funky  [ ... and so  
on for a few dozen ...]

preferences :: Map Person (Group, Group, Group)

In this setup (Fred == Johnny) will be very cheap, and (lookup Fred  
preferences) will be less cheap but possible.

I'd use gensym if I need a new symbol right about which I know nothing  
other than I want it to be new and unique (nobody has created it  
before, and nobody will in the future). In the example scenario, I  
know what I want the symbol is to be called, and am prepared to accept  
the responsibility for avoiding duplicates, but I still want to be  
able create it at run time. In the Haskell snippet above, the compiler  
protects me against duplication, but forces me to know the data at  
compile time.

In Lisp terms, I'm looking for make-symbol and intern.

> Beyond that, the existence of functions such as  
> reallyUnsafePointerEquality# makes me think it's a Hard Problem.

:-)