On 02/07/06, Brian Hulley <[EMAIL PROTECTED]> 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, [EMAIL PROTECTED]
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to