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

On Thu, May 26, 2011 at 04:45, Jacek Generowicz

...

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.

:-)

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

...

On Thu, May 26, 2011 at 05:41, Jacek Generowicz

...

wrote: On 2011 May 26, at 11:12, Brandon Allbery wrote: (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?)

But gensym does seem to be overkill in the case I presented. (...) In Lisp terms, I'm looking for make-symbol and intern.

I think I just landed on "inscrutable";

Nah, it's probably just me confusing you.

(gensym) used to do pretty much that, it rolled symbols starting from 'a0000 for the first one generated in a given interpreter.

It still does essentially that. (Just don't be fooled by the "name" a0000: you can't access that symbol through that name. Aaaah, maybe in Maclisp it really did intern them under that name, but that would surprise me). '(gensym)' in CL is a bit like 'object()' in Python or 'new MyEmptyClass' in C++: the key point being that if you don't bind the thing being created right now, you'll never be able to get your hands on it again. Coming back on topic: Yes, I could use gensym for my purposes (though CL provides a variety of similar yet subtly different tools, which is why gensym feels a bit weird in this context).

On 2011 May 26, at 11:16, Christopher Done wrote:

On 26 May 2011 10:45, Jacek Generowicz wrote:

...

What is the Haskell approach to efficient comparison and lookup of objects by their identity?

Often you just provide your own and implement Eq.

...

I should be able to run the program on data that becomes available at run time.

Typically you define an id generator and zip anything coming from the input stream up with that generator.

Makes sense.

...

Whatever algorithm I choose to use for the optimization, will have to do lots of comparisons of Groups and Persons where their *identity* is all that matters: you don't need to look inside the objects.

To achieve this abstraction the usual way is just implementing Eq:

instance Eq Person where Person{personId=id1} == Person{personId=id2} = id1 == id2

Any comments on the relative efficiency of the above as compared to A == B in the context of data Foo = A | B | C | D | ... lots more ... ? (I imagine that a Sufficiently Smart Compiler could reduce (==) :: Person Person to just integer comparison.) Thank you.

2011/5/26 Jacek Generowicz :

On 2011 May 26, at 11:16, Christopher Done wrote:

...

On 26 May 2011 10:45, Jacek Generowicz wrote:

...

What is the Haskell approach to efficient comparison and lookup of objects by their identity?

Often you just provide your own and implement Eq.

...

I should be able to run the program on data that becomes available at run time.

Typically you define an id generator and zip anything coming from the input stream up with that generator.

Makes sense.

...

...

Whatever algorithm I choose to use for the optimization, will have to do lots of comparisons of Groups and Persons where their *identity* is all that matters: you don't need to look inside the objects.

To achieve this abstraction the usual way is just implementing Eq:

instance Eq Person where  Person{personId=id1} == Person{personId=id2} = id1 == id2

Any comments on the relative efficiency of the above as compared to

A == B in the context of

data Foo = A | B | C | D | ... lots more ...

?

(I imagine that a Sufficiently Smart Compiler could reduce (==) :: Person Person to just integer comparison.)

I'm pretty sure GHC will do that for you. An approach similar to the one by Chris Done is to use a bi-directional map between Persons and Ints along the lines of data IdMap a = IdMap (IntMap a) (Map a Int) You can then associate a unique Int with each of your Persons and use this during your comparison. For associating Ints to the Persons, a simple fold or a State monad computation suffice. For the lookups on the further properties of Persons, an additional argument or the Reader monad will do. If you use a State monad and a single operation that associates an Int to a Person, then you additionally get the guarantee (inside a monadic computation) that no two Persons will be associated with the same Int. Efficiency-wise, you'll have O(log(n)) association, O(min(n,W)) access time, and O(1) comparison time with a very low constant factor. See the IntMap documentation for the O(min(n,W)) explanation. Additionally, the code is pure with all the nice properties that come with it. By the way this problem is very similar to the one of observable sharing. See this thread: http://www.haskell.org/pipermail/haskell-cafe/2008-February/039639.html best regards, Simon

On Thu, May 26, 2011 at 14:56, Andrew Coppin wrote:

My understanding is that if you have a constructor with no fields, it gets allocated as a compile-time constant. In other words, "C" is just a pointer to a static data structure somewhere in the program binary, and (==) effectively becomes pointer equity.

When used as a general function, at least; my understanding is that it's usually reduced to an integer tag (and that this is relied on to do fast conversions internally)

Why doesn't Haskell have built in syntactic sugar for atoms? -- Anupam

I think because of deriving Enum.