[Haskell-cafe] symbol type?

[Thomas Conway]

On 10/10/07, Michael Vanier <mvanier at cs.caltech.edu> wrote:
> Is there an implementation of a symbol type in Haskell i.e. a string which has a constant-time
> comparison operation?

To borrow Prolog terminology, it sounds like you're looking for an
"atom" data type.

I've not done it, but I've plotted to implement a module according to
the following sketch:

module Data.Atom where

data Atom ....

atom :: String -> Atom -- or ByteString

name :: Atom -> String -- or ByteString

instance Eq Atom where ...

instance Ord Atom where ...

The constructor function would do hash-consing using unsafePerformIO
internally to build a [hash] table of extant Atoms. If ByteString is
used for the internal "name", the hash consing means that you can use
the Ptr for O(1) equality tests. The implementation of compare would
still need to do a normal string comparison, after doing an initial
equality test.

If you do the O(1) equality test before doing a full compare, the
performance will be very good in many situations, since non-equal
comparisons tend to terminate quickly. The exception of course is
strings with long common prefixes (e.g. URLs). For symbol names in a
compiler, this is unlikely to be a significant problem.

cheers,
T.
-- 
Thomas Conway
drtomc at gmail.com

Silence is the perfectest herald of joy:
I were but little happy, if I could say how much.