[Haskell-cafe] Re: Where is Data.Atom?
ia at stryx.demon.co.uk
Mon Jul 3 20:33:23 EDT 2006
Put your strings in an ordered binary tree (other data structures might also
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.
Iain Alexander ia at stryx.demon.co.uk
More information about the Haskell-Cafe