[Haskell-cafe] Efficient object identity (aka symbols as data)
Jacek.Generowicz at cern.ch
Thu May 26 11:41:04 CEST 2011
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
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.
More information about the Haskell-Cafe