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 EDiSon (Efficent Data Structures).

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.