simple-atom-0.2: Atom (or symbol) datatype for fast comparision and sorting.




data Symbol Source

A Symbol. This is essentially a String, but with different performance characteristics:

  • O(n) creation time (using insert)
  • O(1) equality comparison.
  • O(1) comparison (in practice). The result of compare is independent of evaluation order.

It is currently implemented as follows.

  • Each symbol contains a unique integer, which allows O(1) comparison.
  • 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.
  • The String representation of the symbol. Use show to return it. At any time, there will be only one symbol of a given name in memory.


intern :: String -> SymbolSource

Turn a String into a Symbol.

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.)