-- 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 * <tt>O(n)</tt> creation
--   time * <tt>O(1)</tt> equality-comparison * <tt>O(1)</tt> (in practice)
--   ord-comparison * <tt>Ord</tt>-comparison results are independent on
--   evaluation order</li>
--   </ul>
--   
--   This module is thread-safe.
@package simple-atom
@version 0.1.0.1


-- | Symbols without a central symbol table.
--   
--   Symbols provide the following efficient operations:
--   
--   <ul>
--   <li><i>O(1)</i> equality comparison (in practise) - <i>O(1)</i>
--   ordering comparison (in practise) - <i>O(n)</i> creation</li>
--   </ul>
--   
--   This can be implemented by using a global variable mapping strings to
--   symbols and a counter assigning ids to symbols. However, this has two
--   problems:
--   
--   <ol>
--   <li>It has a space leak. No symbols can ever be removed from this
--   table. For example, if we add the symbol <tt>"foo"</tt> the first time
--   it might get assigned id 1, if we then delete it and insert it again
--   it might get assigned id 42. However, there may still be symbols in
--   memory which got assigned id 1. Instead, symbols should be garbage
--   collected like other data. Using weak pointers has bad effects on
--   performance due to garbage collector overhead.</li>
--   <li>It is not reliable to compare symbols created using different
--   symbol tables. They would most likely get assigned different ids.</li>
--   </ol>
--   
--   This implementation of symbols allows *optional* use of a symbol
--   table. If a symbol table is used, this implementation will tend to use
--   less memory and its operations will be a little bit faster at the
--   beginning. For longer runs, it won't make a big difference though,
--   since the representation is self-optimising.
--   
--   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.
--   
--   <ul>
--   <li>Implementation</li>
--   </ul>
--   
--   Each symbol is represented a pointer to the symbol info, which
--   consists of:
--   
--   <ul>
--   <li>a <a>String</a> * a <tt>Hash</tt> * a null-able parent pointer to
--   an equivalent symbol info</li>
--   </ul>
--   
--   Creating the same symbol twice will at first be represented as two
--   different entities.
--   
--   <pre>
--            .----+-------+-----.
--   A -----&gt; | 42 | <a>foo</a> | nil |
--            <tt>----+-------+-----</tt>
--   B --.
--       '--&gt; .----+-------+-----.
--   C -----&gt; | 42 | <a>foo</a> | nil |
--            <tt>----+-------+-----</tt>
--   </pre>
--   
--   (Note that <tt>A</tt>, <tt>B</tt> and <tt>C</tt> are <tt>IORefs</tt>.)
--   
--   When comparing <tt>A</tt> and <tt>B</tt> we use the following
--   properties:
--   
--   <ol>
--   <li>If <tt>A</tt> and <tt>B</tt> are identical then they must be
--   equal.</li>
--   <li>If they point to the same object, they must equal.</li>
--   <li>If they have different hashes, they are different.</li>
--   </ol>
--   
--   Unless there is a hash collision, we can decide equality and ordering
--   for all symbols that have been built with the same hash table.
--   
--   If the two objects have no parent, have the same hash, and the same
--   string, we now make one the first the parent of the other and update
--   the pointer of <tt>B</tt> accordingly. If there are no references to
--   the second object left it can now be garbage collected.
--   
--   If an object already has a parent pointer we follow each object's
--   parents to the roots and compare the roots. This process might again
--   result in updates to <tt>A</tt> or <tt>B</tt> and various parent
--   pointers.
--   
--   In the example above, after <tt>A == B</tt> we have:
--   
--   <pre>
--            .----+-------+-----.
--   A -----&gt; | 42 | <a>foo</a> | nil |
--       .--&gt; <tt>----+-------+-----</tt>
--   B --'                    ^
--            .----+-------+--|--.
--   C -----&gt; | 42 | <a>foo</a> |  *  |
--            <tt>----+-------+-----</tt>
--   </pre>
--   
--   After <tt>C == A</tt> or <tt>C == B</tt> we have.
--   
--   <pre>
--   A -----&gt; .----+-------+-----.
--       .--&gt; | 42 | <a>foo</a> | nil |
--   B --'.-&gt; <tt>----+-------+-----</tt>
--        |                   ^
--        |   .----+-------+--|--.
--   C ---'   | 42 | <a>foo</a> |  *  |
--            <tt>----+-------+-----</tt>
--   </pre>
--   
--   The second object will now be garbage collected.
--   
--   In fact, after the first <tt>A == B</tt>, the remaining updates could
--   use some help from the garbage collector. This could be done by
--   somehow forcibly (and unsafely) replacing the second object by an
--   update frame and then rely on the GC's indirection shortening feature.
--   This is <i>very</i> unsafe, since some code may rely "know" that the
--   object is already evaluated. E.g., C's pointer could be tagged (c.f.
--   "Faster Laziness Using Dynamic Pointer Tagging"). It <i>might</i> work
--   if we can match the physical layout of both structures, but it's
--   equally likely that hell freezes over, so I'll leave that as an
--   exercise for more braver hackers.
--   
--   <ul>
--   <li>TODO</li>
--   <li>generalise to arbitrary hashable objects. need not be restricted
--   to <a>String</a>.</li>
--   <li>make thread-safe. (we only need a lock for the uncommon
--   cases)</li>
--   <li>make sure the pointer update code is correct and has no bad
--   cases</li>
--   <li>implement IntMap variant/wrapper that respects that two different
--   objects may have the same key (however unlikely).</li>
--   </ul>
module Data.Atom.UF

-- | A symbol.
data Symbol

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

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

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