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

[Christopher Done]

On 26 May 2011 10:45, Jacek Generowicz <jacek.generowicz at cern.ch> 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. So:

    persons <- fmap (zipWith addId [1..] . map parsePerson)
(hGetContents handle)
     where addId id person = person { personId = id }

> 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

You can also implement ordering if required:

instance Ord Person where
   Person{personId=id1} `compare` Person{personId=id2} = id1 `compare` id2

Then you can write person1 == person2 and person1 > person2, etc.
without "looking inside" the object, and all the library functions you
have available like the list functions that work on Eq instances and
Ord instances will work for your data type automatically.

There're also some packages on Hackage for generating unique ids.