Hello Duncan, Monday, July 3, 2006, 12:50:14 AM, you wrote:

...

...

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

and also equal lengths.

The nice thing about the ByteString representation is that we can use the length to short-cut inequality and use equality of the pointers to short-cut equality:

see first line of quote :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Brian Hulley wrote:

So perhaps my original spec is impossible to implement, though it is an open question whether some very clever encoding (with corresponding implementation of <) could be found which would lead to a better average performance (whatever that means).

An alternative design for an atom module could be:

create :: MonadIO m => String -> m Atom toString :: Atom -> String

instance Eq Atom -- O(1) instance Ord Atom -- O(1) but depends on creation order

but here the < would not be lexicographic, so although it would be useful for implementing symbol tables, environments etc it's not ideal for GUI use (eg when displaying a tree of modules where everything should be listed alphabetically).

Eureka! There *is* a way to get O(1) lexicographic comparisons of Atoms :-) although at the expense of O(n + k) but possibly amortized O(n + ?) creation time where n is the length of the string and k is the number of Atoms in existence at any given time. The previous reason for needing to be clairvoyant in the choice of Unique (or Integer or Int) to represent an Atom was to allow expressions such as atom "a" < atom "b" because when the code has determined the representation for the first atom the creation of the second atom mustn't be allowed to change it. However with monadic creation, such expressions can't be written, and therefore it would be possible to represent atoms as follows: newtype Atom = Atom (IORef Int) -- or IORef Integer and when new atoms are created, we could simply update the Int's referenced by other atoms to ensure that the relative ordering is still lexicographic. If we assume that it's very unlikely we'd need more than 2^31 atoms to exist at any given time (if this assumption is wrong we could use Integer instead of Int) and that usually we'd have a lot less, the Int's could be allocated with gaps between them so that we'd only occasionally need to adjust the Int's of the atoms to the left or right when a new atom is inserted in the table, and in all cases it's extremely unlikely that we'd need to adjust the representation of all the other Atoms (hence amortized O(n) hopefully). The comparison would then be: compare (Atom l) (Atom r) = unsafePerformIO $ do li <- readIORef l ri <- readIORef r return (compare li ri) which is safe as long as creation of atoms is not allowed inside unsafePerformIO (it would be nice if there was a way to tell the typechecker that a specific action is not allowed in unsafe IO) Still there would be some tricky details to work out eg how to ensure that the average number of Integer's that need to be updated on creation of each new atom is as small as possible, so I'll leave this as an exercise for the reader!!! :-) Essentially it depends on how well the following can be implemented: data OrderingToken = ??? instance Eq OrderingToken instance Ord OrderingToken create :: MonadIO m => m OrderingToken -- x < y |- createBetween x y == z where x < z and z < y createBetween :: MonadIO m => OrderingToken -> OrderingToken -> m (OrderingToken) It would be interesting to investigate what the theoretical tradeoffs would be between the complexities of the above functions (assuming we want (<) to be O(1)) and whether or not they require to be monadic. Anyway apologies for rambling on, 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

G'day all. Quoting Brian Hulley :

So perhaps my original spec is impossible to implement, though it is an open question whether some very clever encoding (with corresponding implementation of <) could be found which would lead to a better average performance (whatever that means).

For what it's worth: - It's not such a dumb idea to separate equality testing from less-than testing. A (Unique,ByteString) pair makes the former fast and the latter pretty fast when it's needed. - Arithmetic coding preserves lexicographic ordering. If you have a good statistical model for what sort of strings might be used as atoms, it may be possible to construct a representation of atoms which fit in machine 32- or 64-bit word most of the time. (This is similar to the way that GHC represents Integers; use a machine word when it fits.) - Hash table implementations rely on using a cheap test first (comparing hash codes), going to a full comparison only if the cheap test doesn't rule out what you're looking for.

As an aside, if the monad was removed then the result of atom "a" < atom "b" (atom :: String -> Atom) could not be determined by analysis of the program. It would depend on the evaluation order chosen by the compiler, but in a sense this doesn't matter because whatever the result is, it would be the same at any future time during the same run of the program so the use of Atoms as keys would still be safe. But is this still "functional"?

Questions of this nature produce much disagreement. Once upon a time, program arguments and environment variables were passed to a Haskell program using a similar mechanism. I think we got rid of this because it's not "functional" if you consider programs that fork. Cheers, Andrew Bromage

Iain Alexander wrote:

Another suggestion:

Put your strings in an ordered binary tree (other data structures might also work here).

Make your Atom an encoding of the structure of the tree (resp. other structure). This is logically a sequence of bits, 0 for left (less than), 1 for right (greater than) - if you terminate this variable-length sequence with 1, I think it all works out OK. You then encode this sequence of bits in a Word32 (or some other convenient item), with implicit trailing zeros.

root ~> 1[000...] root.left ~> 01[000...] root.right ~> 11[000...] ...

There are clearly some questions such as how unbalanced is the tree likely to get (since you can't conveniently rebalance it), and what to do if your Atom "overflows", but this might give you something to work with.

Thanks for the suggestion. However I think that just using a binary tree would be equivalent to just using the representation of the original string as a sequence of bits (except for "early out" eg representing 0b00001111 as just 1111 etc), and any other systematic encoding of strings that preserved all the info necessary for lexicographic ordering (that still works when new atoms are created later) would also end up using at least the same number of bit comparisons on average (since a new information preserving representation is just a permutation of the original at the bit level - if some strings are represented with fewer bits others would need more bits so it would all balance out). The only way I can see of getting truly O(1) lexicographic comparisons (by this I mean O(log P) where P is the maximum number of atoms that can exist simultaneously at any point during program execution) would be to have a "floating" representation (accessed via an IORef) where the concrete values of existing atoms are changed as necessary behind the scenes as new atoms are created, but as Chris pointed out this would require a locking operation if the atoms were used in a multi-threaded program, so all in all, it may well be much faster to just use ByteStrings especially if the Atoms are just to be used to represent fairly short strings such as module names or natural language words etc. Still I think this would be an interesting project - Prolog style Atoms with O(1) lexicographic ordering and O(n + f k) creation time where k is the size of the existing population and f is some function which minimizes the amortized time... Regards, 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