-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Atom (or symbol) datatype for fast comparision and sorting.
--   
--   This module provides an abstract datatype for atoms, such that:
--   
--   <ul>
--   <li>Each atom string is only in memory once</li>
--   <li><tt>O(n)</tt> creation time</li>
--   <li><tt>O(1)</tt> equality-comparison</li>
--   <li><tt>O(1)</tt> (in practice) ord-comparison</li>
--   <li><tt>Ord</tt>-comparison results are independent on evaluation
--   order</li>
--   </ul>
--   
--   This module is thread-safe.
@package simple-atom
@version 0.2


-- | Symbols without a central symbol table.
--   
--   Symbols provide the following efficient operations:
--   
--   <ul>
--   <li><i>O(1)</i> equality comparison (in practise)</li>
--   <li><i>O(1)</i> ordering comparison (in practise)</li>
--   <li><i>O(n)</i> creation where <i>N</i> is the size of the symbol
--   descriptor.</li>
--   </ul>
--   
--   Many implementations often have the additional property that each
--   symbol descriptor only exists once in memory. This implementation
--   slightly relaxes this property:
--   
--   <ul>
--   <li>A symbol descriptor is guaranteed to exists only once in memory if
--   it has been created using the same symbol table. Furthermore, if two
--   symbols created from different symbol tables are compared and their
--   descriptors turn out to be equal, the symbols will share the
--   descriptor after the comparison.</li>
--   </ul>
--   
--   This allows the following additional properties not present in
--   conventional implementations:
--   
--   <ul>
--   <li>No space leak. The symbol table can be discarded at any time.</li>
--   <li>Symbols created using different symbol tables can be compared
--   reliably.</li>
--   <li>No global lock. (TODO: Well we might need one in the case of
--   hash-collisions, but a lock-free implementation might be
--   possible.)</li>
--   </ul>
--   
--   Inspired by Richard O<tt>Keefe</tt>s message to Erlang's eeps mailing
--   list <a>http://www.erlang.org/cgi-bin/ezmlm-cgi/5/057</a>, which in
--   turn was inspired by the Logix implementation of Flat Concurrent
--   Prolog.
module Data.Atom.UF

-- | A symbol.
--   
--   Note that the ordering on <tt>a</tt> is <i>not</i> preserved on
--   <tt>Symbol a</tt>. Symbols are ordered by their hashes, and only if
--   the hashes are equal will the ordering on <tt>a</tt> be used. We have:
--   
--   <pre>
--     x == y ==&gt; intern x == intern y
--   
--   let sx = intern x
--         sy = intern y
--     in
--       (sx &lt; sy) == ((symbolHash sy &lt; symbolHash sx) ||
--                     symbolHash sy == symbolHash sx &amp;&amp; x &lt; y)
--   </pre>
data Symbol a

-- | Create a new local symbol. For best performance use <a>internInto</a>
--   together with a symbol table / map.
intern :: (a -> Word64) -> a -> Symbol a

-- | Insert a symbol into an existing table.
internInto :: SymTab s => (a -> Word64) -> s a -> a -> (s a, Symbol a)
class SymTab s
lookupSymbol :: SymTab s => s a -> a -> Maybe (Symbol a)
insertSymbol :: SymTab s => a -> (Symbol a) -> s a -> s a

-- | Returns the hash of the symbol.
symbolHash :: Symbol a -> Word64
instance Show a => Show (Symbol a)
instance Ord a => Ord (Symbol a)
instance Ord a => Eq (Symbol a)

module Data.Atom.Simple

-- | A <a>Symbol</a>. This is essentially a <a>String</a>, but with
--   different performance characteristics:
--   
--   <ul>
--   <li><tt>O(n)</tt> creation time (using <tt>insert</tt>)</li>
--   <li><tt>O(1)</tt> equality comparison.</li>
--   <li><tt>O(1)</tt> comparison (in practice). The result of
--   <a>compare</a> is independent of evaluation order.</li>
--   </ul>
--   
--   It is currently implemented as follows.
--   
--   <ul>
--   <li>Each symbol contains a unique integer, which allows <tt>O(1)</tt>
--   comparison.</li>
--   <li>Each symbol contains an infinite chain of hashes, these are used
--   for comparison. In practice, it is very rare that more than the first
--   of those hashes is ever evaluated. The first hash is cached, so that
--   most comparisons will not need any indirections.</li>
--   <li>The <a>String</a> representation of the symbol. Use <a>show</a> to
--   return it. At any time, there will be only one symbol of a given name
--   in memory.</li>
--   </ul>
data Symbol

-- | Turn a <a>String</a> into a <a>Symbol</a>.
--   
--   Note, however, that this function contains a space leak. It has
--   internal state (the symbol table) but is referentially transparent.
--   Unfortunately, there is no way to delete items from the symbol table.
--   
--   (This function is, of course, thread-safe.)
intern :: String -> Symbol
instance Ord Symbol
instance Eq Symbol
instance Show Symbol