[Haskell-cafe] Where is Data.Atom ?

[Brian Hulley]

Hi -
I seem to remember from some discussion long ago that there is a Data.Atom 
module somewhere (hopefully with a BSD licence), but a search on Hoogle 
turned up no results so maybe I'm mistaken.
What I'm looking for is an Atom type and the following operations:

      fromString :: String -> Atom
      toString :: Atom -> String

      instance Eq Atom
      instance Ord Atom -- this is where things get difficult!

It is particularly important that the ordering comparison is extremely fast, 
preferably independent of the length of the original String, and that it 
preserves the lexicographic ordering between the original Strings.

I can see that an "unsafe" global ref to a Trie of Char with Unique as the 
"value" of a node would allow me to implement fromString, toString, and 
instance Eq Atom, but I've got no idea how to implement instance Ord Atom so 
that the order is independent of the order in which Atoms are created and 
exactly the same as the lexicographic ordering of the String without being 
O(n) where n is the min of the lengths of the Atoms being compared.

I'm also hoping that Atoms which are no longer in use would manage to 
magically vanish by themselves. In a Trie implementation, this would mean 
maintaining an invariant that leaf nodes are always held by a weak link and 
internal nodes by a strong link.

Any ideas (or pointers to a nice downloadable module that already does all 
this :-) )?

Thanks,
Brian.

-- 
Logic empowers us and Love gives us purpose.
Yet still phantoms restless for eras long past,
congealed in the present in unthought forms,
strive mightily unseen to destroy us.

http://www.metamilk.com