[Haskell-cafe] Where is Data.Atom ?

[David House]

On 02/07/06, Brian Hulley <brianh at metamilk.com> wrote:
> 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.

Isn't compare on strings O(n) anyway? I suppose it would actually be
O(d), where d is the index of the first difference, but that's O(n)
worst-case. Even equality (a special case of compare) on strings
(well, [Char], to be more precise) involves traversing the list and so
is O(n) worst-case, no?

-- 
-David House, dmhouse at gmail.com