Edison.hs

-- |
--   Module      :  Data.Edison
--   Copyright   :  Copyright (c) 2006 Robert Dockins
--   License     :  MIT; see COPYRIGHT file for terms and conditions
--
--   Maintainer  :  robdockins AT fastmail DOT fm
--   Stability   :  stable
--   Portability :  GHC, Hugs (MPTC and FD)
--
--   Edison is a library of purely functional data structures written by
--   Chris Okasaki.  It is named after Thomas Alva Edison and for the
--   mnemonic value /ED/i/S/on (/E/fficent /D/ata /S/tructures).
--
--   Edison provides several families of abstractions, each with
--   multiple implementations.  The main abstractions provided by Edison are:
--
--   * /Sequences/ such as stacks, queues, and dequeues,
--
--   * /Collections/ such as sets, bags and heaps, and
--
--   * /Associative Collections/ such as finite maps and priority queues
--     where the priority and element are distinct.
--
--
--
--   /Conventions:/
--
--   Each data structure is implemented as a separate module.  These modules
--   should always be imported @qualified@ to prevent a flood of name clashes,
--   and it is recommended to rename the module using the @as@ keyword to reduce
--   the overhead of qualified names and to make substituting one implementation
--   for another as painless as possible.
--
--   Names have been chosen to match standard usage as much as possible.  This
--   means that operations for abstractions frequently share the same name
--   (for example, @empty@, @null@, @size@, etc).  It also means that in many
--   cases names have been reused from the Prelude.  However, the use of
--   @qualified@ imports will prevent name reuse from becoming name clashes.  If
--   for some reason you chose to import an Edison data structure unqualified,
--   you will likely need to import the Prelude @hiding@ the relevant names.
--
--   Edison modules also frequently share type names.  For example, most sequence
--   type constructors are named @Seq@.  This additionally aids substituting
--   implementations by simply importing a different module.
--
--   Argument orders are selected with the following points in mind:
--
--   * /Partial application:/ arguments more likely to be static usually
--     appear before other arguments in order to facilitate partial
--     application.
--
--   * /Collection appears last:/ in all cases where an operation queries a
--     single collection or modifies an existing collection, the collection
--     argument will appear last.  This is something of a de facto standard
--     for Haskell datastructure libraries
--     and lends a degree of consistency to the API.
--
--   * /Most usual order:/ where an operation represents a well-known
--     mathematical function on more than one datastructure, the arguments
--     are chosen to match the most usual argument order for the function.
--
--
--   /Type classes:/
--
--   Each family of abstractions is defined as a set of classes: a main class
--   that every implementation of that abstraction should support and several
--   auxiliary subclasses that an implementation may or may not support. However,
--   not all applications require the power of type classes, so each method
--   is also directly accessible from the implementation module.  Thus you can
--   choose to use overloading or not, as appropriate for your particular
--   application.
--
--   Documentation about the behavior of data structure operations is defined
--   in the modules "Data.Edison.Seq", "Data.Edison.Coll" and
--   "Data.Edison.Assoc".  Implementations are required to respect
--   the descriptions and axioms found in these modules.  In some cases time
--   complexity is also given.  Implementations may differ from these time
--   complexities; if so, the differences will be given in the documentation for
--   the individual implementation module.
--
--
--
--   /Notes on Eq and Ord instances:/
--
--   Many Edison data structures require @Eq@ or @Ord@ contexts to define equivalence
--   and total ordering on elements or keys.  Edison makes the following assumptions
--   about all such required instances:
--
--   * An @Eq@ instance correctly defines an equivalence relation (but not necessarily
--     structural equality); that is, we assume @(==)@ (considered as a
--     relation) is reflexive, symmetric and transitive, but allow that equivalent
--     items may be distinguishable by other means.
--
--   * An @Ord@ instance correctly defines a total order which is consistent with
--     the @Eq@ instance for that type.
--
--   These assumptions correspond to the usual meanings assigned to these classes.  If
--   an Edison data structure is used with an @Eq@ or @Ord@ instance which violates these
--   assumptions, then the behavior of that data structure is undefined.
--
--
--
--   /Notes on Read and Show instances:/
--
--   The usual Haskell convention for @Read@ and @Show@ instances (as championed by the
--   Haskell \"deriving\" mechanism), is that @show@ generates a string which is a
--   valid Haskell expression built up
--   using the data type's data constructors such that, if interpreted as Haskell code, the
--   string would generate an identical data item.  Furthermore, the derived  @Read@
--   instances are able to parse such strings, such that @(read . show) === id@.
--   So, derived instances of @Read@ and @Show@ exhibit
--   the following useful properties:
--
--   * @read@ and @show@ are complementary; that is, @read@ is a useful inverse for @show@
--
--   * @show@ generates a string which is legal Haskell code representing the data item
--
--   For concrete data types, the deriving mechanism is usually quite sufficient.
--   However, for abstract types the derived @Read@ instance may allow users to create data
--   which violates invariants. Furthermore, the strings resulting from @show@ reference hidden
--   data constructors which violates good software engineering principles and also
--   cannot be compiled because the constructors are not available outside the defining module.
--
--   Edison avoids most of these problems and still maintains the above useful properties by
--   doing conversions to and from lists and inserting explicit calls to the list conversion
--   operations.  The corresponding @Read@ instance strips the list conversion call before
--   parsing the list.  In this way, private data constructors are not revealed and @show@ strings
--   are still legal, compilable Haskell code.  Furthermore, the showed strings gain a degree of
--   independence from the underlying datastructure implementation.
--
--   For example, calling @show@ on an empty Banker's queue will result in the following string:
--
-- > Data.Edison.Seq.BankersQueue.fromList []
--
--   Datatypes which are not native Edison data structures (such as StandardSet and StandardMap)
--   may or may not provide @Read@ or @Show@ instances and, if they exist, they may or may
--   not also provide the properties that Edison native @Read@ and @Show@ instances do.
--
--
--   /Notes on time complexities:/
--
--   Some Edison data structures (only the sequences currently) have detailed time complexity
--   information.  Unless otherwise stated, these are amortized time complexities, assuming
--   persistent usage of the datastructure.  Much of this data comes from:
--
--   Martin Holters. /Efficient Data Structures in a Lazy Functional Language/.  Master's Thesis.
--   Chalmers University of Technology, Sweden. 2003.
--
--   /Notes on unsafe functions:/
--
--   There are a number of different notions of what constitutes an unsafe function.
--   In Haskell, a function is generally called \"unsafe\" if it can subvert
--   type safety or referential integrity, such as @unsafePerformIO@ or @unsafeCoerce#@.
--   In Edison, however, we downgrade the meaning of \"unsafe\" somewhat.  An
--   \"unsafe\" Edison function is one which, if misused, can violate the structural
--   invariants of a data structure.  Misusing an Edison \"unsafe\" function should
--   never cause your runtime to crash or break referential integrity, but it may cause
--   later uses of a data structure to behave in undefined ways.  Almost all unsafe functions
--   in Edison are labeled with the @unsafe@ prefix.  An exception to this rule is the
--   @With@ functions in the 'Set' class, which are also unsafe but do not have
--   the prefix.  Unsafe functions will have explicit preconditions listed in their
--   documentation.
--
--
--
--   /Notes on ambiguous functions:/
--
--   Edison also contains some functions which are labeled \"ambiguous\".  These
--   functions cannot violate the structural invariants of a data structure, but, under
--   some conditions, the result of applying an ambiguous function is not well defined.
--   For ambiguous functions, the result of applying the function may depend on otherwise
--   unobservable internal state of the data structure, such as the actual shape of a
--   balanced tree.  For example, the 'AssocX' class contains the @fold@ function, which
--   folds over the elements in the collection in an arbitrary order.  If the combining
--   function passed to @fold@ is not fold-commutative (see below), then the result of
--   the fold will depend on the actual order that elements are presented to the
--   combining function, which is not defined.
--
--   To aid programmers, each API function is labeled /ambiguous/ or /unambiguous/ in its
--   documentation.  If a function is unambiguous only under some circumstances,
--   that will also be explicitly stated.
--
--   An \"unambiguous\" operation is one where all correct implementations of the operation
--   will return \"indistinguishable\" results.  For concrete data types, \"indistinguishable\"
--   means structural equality.  An instance of an abstract data type is considered
--   indistinguishable from another if all possible applications of unambiguous
--   operations to both yield indistinguishable results.  (Note: this definition is
--   impredicative and rather imprecise.  Should it become an issue, I will attempt to
--   develop a better definition.  I hope the intent is sufficiently clear).
--
--   A higher-order unambiguous operation may be rendered ambiguous if passed a \"function\" which
--   does not respect referential integrity (one containing @unsafePerformIO@ for example).
--   Only do something like this if you are 110% sure you know what you are doing, and even then
--   think it over two or three times.
--
--
--
--   /How to choose a fold:/
--
--   /Folds/ are an important class of operations on data structures in a functional
--   language; they perform essentially the same role that iterators perform in
--   imperative languages.  Edison provides a dizzying array of folds which (hopefully)
--   correspond to all the various ways a programmer might want to fold over a data
--   structure.  However, it can be difficult to know which fold to choose for a
--   particular application.  In general, you should choose a fold which provides
--   the /fewest/ guarantees necessary for correctness.  The folds which have fewer
--   guarantees give data structure implementers more leeway to provide efficient
--   implementations.  For example, if you which to fold a commutative, associative
--   function, you should chose @fold@ (which does not guarantee an order) over @foldl@
--   or @foldr@, which specify particular orders.
--
--   Also, if your function is strict in
--   the accumulating argument, you should prefer the strict folds (eg, @fold'@); they will
--   often provide better space behavior.  /Be aware/, however, that the \"strict\" folds
--   are not /necessarily/ more strict than the \"non-strict\" folds; they merely give
--   implementers the option to provide additional strictness if it improves performance.
--
--   For associative collections, only use with @WithKey@ folds if you actually need the
--   value of the key.
--
--
--   /Painfully detailed information about ambiguous folds:/
--
--   All of the folds that are listed ambiguous are ambiguous because they do not or cannot
--   guarantee a stable order with which the folding function will be applied.  However,
--   some functions are order insensitive, and the result will be unambiguous regardless
--   of the fold order chosen.  Here we formalize this property, which we call
--   \"fold commutativity\".
--
--   We say @f :: a -> b -> b@ is /fold-commutative/ iff @f@ is unambiguous and
--
-- >    forall w, z :: b; m, n :: a
-- >
-- >       w = z ==> f m (f n w) = f n (f m z)
-- >
--
--   where @=@ means indistinguishability.
--
--   This property is sufficient (but not necessary) to ensure that, for any
--   collection of elements to
--   fold over, folds over all permutations of those elements will generate
--   indistinguishable results.  In other words, an ambiguous fold applied to a
--   fold-commutative combining function becomes /unambiguous/.
--
--   Some fold combining functions take their arguments in the reverse order.  We
--   straightforwardly extend the notion of fold commutativity to such functions
--   by reversing the arguments.  More formally, we say @g :: b -> a -> b@ is fold
--   commutative iff @flip g :: a -> b -> b@ is fold commutative.
--
--   For folds which take both a key and an element value, we extend the notion of fold
--   commutativity by considering the key and element to be a single, uncurried argument.
--   More formally, we say @g :: k -> a -> b -> b@ is fold commutative iff
--
-- >    \(k,x) z -> g k x z :: (k,a) -> b -> b
--
--   is fold commutative according to the above definition.
--
--   Note that for @g :: a -> a -> a@, if @g@ is unambiguous,
--   commutative, and associative, then @g@ is fold-commutative.
--
--   Proof:
--
-- >    let w = z, then
-- >    g m (g n w) = g m (g n z)     g is unambiguous
-- >                = g (g n z) m     commutative property of g
-- >                = g n (g z m)     associative property of g
-- >                = g n (g m z)     commutative property of g
--
--   Qed.
--
--   Thus, many common numeric combining functions, including @(+)@ and @(*)@ at
--   integral types, are fold commutative and can be safely used with ambiguous
--   folds.
--
--   /Be aware/ however, that @(+)@ and @(*)@ at floating point types are only
--   /approximately/ commutative and associative due to rounding errors; using
--   ambiguous folds with these operations may result in subtle differences in
--   the results.  As always, be aware of the limitations and numeric
--   properties of floating point representations.
--
--
--
--   /About this module:/
--
--   This module re-exports the various data structure abstraction classes, but
--   not their methods. This allows you to write type signatures which have
--   contexts that mention Edison type classes without having to import the
--   appropriate modules @qualified@.  The class methods are not exported to
--   avoid name clashes.  Obviously, to use the methods of these classes, you
--   will have to import the appropriate modules.  This module additionally
--   re-exports the entire "Data.Edison.Prelude" module.
--
--
--
--   /Miscellaneous points:/
--
--   Some implementations export a few extra functions beyond those included
--   in the relevant classes.  These are typically operations that are
--   particularly efficient for that implementation, but are not general enough
--   to warrant inclusion in a class.
--
--   Since qualified infix symbols are fairly ugly, they have been largely avoided.
--   However, the "Data.Edison.Sym" module defines a number of infix operators
--   which alias the prefix operators; this module is intended to be imported
--   unqualified.
--
--   Most of the operations on most of the data structures are strict.  This is
--   inevitable for data structures with non-trivial invariants. Even given
--   that, however, many of the operations are stricter than necessary.  In
--   fact, operations are never deliberately made lazy unless the laziness is
--   required by the algorithm, as can happen with amortized data structures.
--
--   Note, however, that the various sequence implementations are always lazy
--   in their elements.  Similarly, associative collections are always lazy in
--   their elements (but usually strict in their keys).  Non-associative
--   collections are usually strict in their elements.

module Data.Edison (

-- * Sequence class
  Sequence

-- * Collection classes
-- ** Non-observable collections
, CollX
, OrdCollX
, SetX
, OrdSetX
-- ** Observable collections
, Coll
, OrdColl
, Set
, OrdSet

-- * Associative collection classes
-- ** Non-observable associative collections
, AssocX
, OrdAssocX
, FiniteMapX
, OrdFiniteMapX
-- ** Observable associative collections
, Assoc
, OrdAssoc
, FiniteMap
, OrdFiniteMap

, module Data.Edison.Prelude
) where

import Data.Edison.Prelude
import Data.Edison.Seq
import Data.Edison.Coll
import Data.Edison.Assoc