[Haskell-cafe] Where is Data.Atom ?

ajb at spamcop.net ajb at spamcop.net
Sun Jul 2 20:01:19 EDT 2006

G'day all.

Quoting Brian Hulley <brianh at metamilk.com>:

> 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.

Unique would give you an instance of Ord Atom, it just wouldn't give
you lexicographic ordering.  Whether you need lexicographic ordering
or not largely depends on what you want atoms for.

In X11, for example, atoms basically form a user-extensible enumeration
type.  X11 atoms do support ordering, but the ordering is arbitrary by
design.  The reason is that it is very important that atoms are fixed-
size to make manipulation and incorporation into network protocol
messages easier; that's their whole reason for existing.

Lisp/Prolog atoms, on the other hand, do need lexicographic ordering.

The point is that atoms which use the standard ordering that comes with
Uniques isn't wrong, though it may not quite be what you want.

> 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.

This would, of course, be inappropriate behaviour if you used arbitrary
ordering for your atoms.

Andrew Bromage

More information about the Haskell-Cafe mailing list