/usr/share/doc/haskell-edison-api-doc/html/Data-Edison.html is in libghc-edison-api-doc 1.2.1-17.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Data.Edison</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Data-Edison.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-Edison.html">Source</a></li><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">EdisonAPI-1.2.1: A library of efficient, purely-functional data structures (API)</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Portability</th><td>GHC, Hugs (MPTC and FD)</td></tr><tr><th>Stability</th><td>stable</td></tr><tr><th>Maintainer</th><td>robdockins AT fastmail DOT fm</td></tr><tr><th>Safe Haskell</th><td>Safe-Infered</td></tr></table><p class="caption">Data.Edison</p></div><div id="table-of-contents"><p class="caption">Contents</p><ul><li><a href="#g:1">Sequence class
</a></li><li><a href="#g:2">Collection classes
</a><ul><li><a href="#g:3">Non-observable collections
</a></li><li><a href="#g:4">Observable collections
</a></li></ul></li><li><a href="#g:5">Associative collection classes
</a><ul><li><a href="#g:6">Non-observable associative collections
</a></li><li><a href="#g:7">Observable associative collections
</a></li></ul></li></ul></div><div id="description"><p class="caption">Description</p><div class="doc"><p>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 <em>ED</em>i<em>S</em>on (<em>E</em>fficent <em>D</em>ata <em>S</em>tructures).
</p><p>Edison provides several families of abstractions, each with
multiple implementations. The main abstractions provided by Edison are:
</p><ul><li> <em>Sequences</em> such as stacks, queues, and dequeues,
</li><li> <em>Collections</em> such as sets, bags and heaps, and
</li><li> <em>Associative Collections</em> such as finite maps and priority queues
where the priority and element are distinct.
</li></ul><p><em>Conventions:</em>
</p><p>Each data structure is implemented as a separate module. These modules
should always be imported <code>qualified</code> to prevent a flood of name clashes,
and it is recommended to rename the module using the <code>as</code> keyword to reduce
the overhead of qualified names and to make substituting one implementation
for another as painless as possible.
</p><p>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, <code>empty</code>, <code>null</code>, <code>size</code>, etc). It also means that in many
cases names have been reused from the Prelude. However, the use of
<code>qualified</code> 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 <code>hiding</code> the relevant names.
</p><p>Edison modules also frequently share type names. For example, most sequence
type constructors are named <code>Seq</code>. This additionally aids substituting
implementations by simply importing a different module.
</p><p>Argument orders are selected with the following points in mind:
</p><ul><li> <em>Partial application:</em> arguments more likely to be static usually
appear before other arguments in order to facilitate partial
application.
</li><li> <em>Collection appears last:</em> 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.
</li><li> <em>Most usual order:</em> 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.
</li></ul><p><em>Type classes:</em>
</p><p>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.
</p><p>Documentation about the behavior of data structure operations is defined
in the modules <a href="Data-Edison-Seq.html">Data.Edison.Seq</a>, <a href="Data-Edison-Coll.html">Data.Edison.Coll</a> and
<a href="Data-Edison-Assoc.html">Data.Edison.Assoc</a>. 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.
</p><p><em>Notes on Eq and Ord instances:</em>
</p><p>Many Edison data structures require <code>Eq</code> or <code>Ord</code> contexts to define equivalence
and total ordering on elements or keys. Edison makes the following assumptions
about all such required instances:
</p><ul><li> An <code>Eq</code> instance correctly defines an equivalence relation (but not necessarily
structural equality); that is, we assume <code>(==)</code> (considered as a
relation) is reflexive, symmetric and transitive, but allow that equivalent
items may be distinguishable by other means.
</li><li> An <code>Ord</code> instance correctly defines a total order which is consistent with
the <code>Eq</code> instance for that type.
</li></ul><p>These assumptions correspond to the usual meanings assigned to these classes. If
an Edison data structure is used with an <code>Eq</code> or <code>Ord</code> instance which violates these
assumptions, then the behavior of that data structure is undefined.
</p><p><em>Notes on Read and Show instances:</em>
</p><p>The usual Haskell convention for <code>Read</code> and <code>Show</code> instances (as championed by the
Haskell "deriving" mechanism), is that <code>show</code> 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 <code>Read</code>
instances are able to parse such strings, such that <code>(read . show) === id</code>.
So, derived instances of <code>Read</code> and <code>Show</code> exhibit
the following useful properties:
</p><ul><li> <code>read</code> and <code>show</code> are complementary; that is, <code>read</code> is a useful inverse for <code>show</code>
</li><li> <code>show</code> generates a string which is legal Haskell code representing the data item
</li></ul><p>For concrete data types, the deriving mechanism is usually quite sufficient.
However, for abstract types the derived <code>Read</code> instance may allow users to create data
which violates invariants. Furthermore, the strings resulting from <code>show</code> 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.
</p><p>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 <code>Read</code> instance strips the list conversion call before
parsing the list. In this way, private data constructors are not revealed and <code>show</code> strings
are still legal, compilable Haskell code. Furthermore, the showed strings gain a degree of
independence from the underlying datastructure implementation.
</p><p>For example, calling <code>show</code> on an empty Banker's queue will result in the following string:
</p><pre> Data.Edison.Seq.BankersQueue.fromList []
</pre><p>Datatypes which are not native Edison data structures (such as StandardSet and StandardMap)
may or may not provide <code>Read</code> or <code>Show</code> instances and, if they exist, they may or may
not also provide the properties that Edison native <code>Read</code> and <code>Show</code> instances do.
</p><p><em>Notes on time complexities:</em>
</p><p>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:
</p><p>Martin Holters. <em>Efficent Data Structures in a Lazy Functional Language</em>. Master's Thesis.
Chalmers University of Technology, Sweden. 2003.
</p><p><em>Notes on unsafe functions:</em>
</p><p>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 <code>unsafePerformIO</code> or <code>unsafeCoerce#</code>.
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 <code>unsafe</code> prefix. An exception to this rule is the
<code>With</code> functions in the <code><a href="Data-Edison.html#t:Set">Set</a></code> class, which are also unsafe but do not have
the prefix. Unsafe functions will have explicit preconditions listed in their
documentation.
</p><p><em>Notes on ambiguous functions:</em>
</p><p>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 <code><a href="Data-Edison.html#t:AssocX">AssocX</a></code> class contains the <code>fold</code> function, which
folds over the elements in the collection in an arbitrary order. If the combining
function passed to <code>fold</code> 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.
</p><p>To aid programmers, each API function is labeled <em>ambiguous</em> or <em>unambiguous</em> in its
documentation. If a function is unambiguous only under some circumstances,
that will also be explicitly stated.
</p><p>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).
</p><p>A higher-order unambiguous operation may be rendered ambiguous if passed a "function" which
does not respect referential integrity (one containing <code>unsafePerformIO</code> 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.
</p><p><em>How to choose a fold:</em>
</p><p><em>Folds</em> 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 <em>fewest</em> 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 <code>fold</code> (which does not guarantee an order) over <code>foldl</code>
or <code>foldr</code>, which specify particular orders.
</p><p>Also, if your function is strict in
the accumulating argument, you should prefer the strict folds (eg, <code>fold'</code>); they will
often provide better space behavior. <em>Be aware</em>, however, that the "strict" folds
are not <em>necessarily</em> more strict than the "non-strict" folds; they merely give
implementers the option to provide additional strictness if it improves performance.
</p><p>For associative collections, only use with <code>WithKey</code> folds if you actually need the
value of the key.
</p><p><em>Painfully detailed information about ambiguous folds:</em>
</p><p>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".
</p><p>We say <code>f :: a -> b -> b</code> is <em>fold-commutative</em> iff <code>f</code> is unambiguous and
</p><pre> forall w, z :: b; m, n :: a
w = z ==> f m (f n w) = f n (f m z)
</pre><p>where <code>=</code> means indistinguishability.
</p><p>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 <em>unambiguous</em>.
</p><p>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 <code>g :: b -> a -> b</code> is fold
commutative iff <code>flip g :: a -> b -> b</code> is fold commutative.
</p><p>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 <code>g :: k -> a -> b -> b</code> is fold commutative iff
</p><pre> \(k,x) z -> g k x z :: (k,a) -> b -> b
</pre><p>is fold commutative according to the above definition.
</p><p>Note that for <code>g :: a -> a -> a</code>, if <code>g</code> is unambiguous,
commutative, and associative, then <code>g</code> is fold-commutative.
</p><p>Proof:
</p><pre> 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
</pre><p>Qed.
</p><p>Thus, many common numeric combining functions, including <code>(+)</code> and <code>(*)</code> at
integral types, are fold commutative and can be safely used with ambiguous
folds.
</p><p><em>Be aware</em> however, that <code>(+)</code> and <code>(*)</code> at floating point types are only
<em>approximately</em> 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.
</p><p><em>About this module:</em>
</p><p>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 <code>qualified</code>. 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 <a href="Data-Edison-Prelude.html">Data.Edison.Prelude</a> module.
</p><p><em>Miscellaneous points:</em>
</p><p>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.
</p><p>Since qualified infix symbols are fairly ugly, they have been largely avoided.
However, the <a href="Data-Edison-Sym.html">Data.Edison.Sym</a> module defines a number of infix operators
which alias the prefix operators; this module is intended to be imported
unqualified.
</p><p>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.
</p><p>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.
</p></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><span class="keyword">class</span> (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Control-Monad.html#t:Functor">Functor</a> s, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Control-Monad.html#t:MonadPlus">MonadPlus</a> s) => <a href="#t:Sequence">Sequence</a> s </li><li class="src short"><span class="keyword">class</span> (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Eq.html#t:Eq">Eq</a> a, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Monoid.html#t:Monoid">Monoid</a> c) => <a href="#t:CollX">CollX</a> c a | c -> a</li><li class="src short"><span class="keyword">class</span> (<a href="Data-Edison.html#t:CollX">CollX</a> c a, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> a) => <a href="#t:OrdCollX">OrdCollX</a> c a | c -> a</li><li class="src short"><span class="keyword">class</span> <a href="Data-Edison.html#t:CollX">CollX</a> c a => <a href="#t:SetX">SetX</a> c a | c -> a</li><li class="src short"><span class="keyword">class</span> (<a href="Data-Edison.html#t:OrdCollX">OrdCollX</a> c a, <a href="Data-Edison.html#t:SetX">SetX</a> c a) => <a href="#t:OrdSetX">OrdSetX</a> c a | c -> a</li><li class="src short"><span class="keyword">class</span> <a href="Data-Edison.html#t:CollX">CollX</a> c a => <a href="#t:Coll">Coll</a> c a | c -> a</li><li class="src short"><span class="keyword">class</span> (<a href="Data-Edison.html#t:Coll">Coll</a> c a, <a href="Data-Edison.html#t:OrdCollX">OrdCollX</a> c a) => <a href="#t:OrdColl">OrdColl</a> c a | c -> a</li><li class="src short"><span class="keyword">class</span> (<a href="Data-Edison.html#t:Coll">Coll</a> c a, <a href="Data-Edison.html#t:SetX">SetX</a> c a) => <a href="#t:Set">Set</a> c a | c -> a</li><li class="src short"><span class="keyword">class</span> (<a href="Data-Edison.html#t:OrdColl">OrdColl</a> c a, <a href="Data-Edison.html#t:Set">Set</a> c a) => <a href="#t:OrdSet">OrdSet</a> c a | c -> a</li><li class="src short"><span class="keyword">class</span> (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Eq.html#t:Eq">Eq</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Control-Monad.html#t:Functor">Functor</a> m) => <a href="#t:AssocX">AssocX</a> m k | m -> k</li><li class="src short"><span class="keyword">class</span> (<a href="Data-Edison.html#t:AssocX">AssocX</a> m k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> k) => <a href="#t:OrdAssocX">OrdAssocX</a> m k | m -> k</li><li class="src short"><span class="keyword">class</span> <a href="Data-Edison.html#t:AssocX">AssocX</a> m k => <a href="#t:FiniteMapX">FiniteMapX</a> m k | m -> k</li><li class="src short"><span class="keyword">class</span> (<a href="Data-Edison.html#t:OrdAssocX">OrdAssocX</a> m k, <a href="Data-Edison.html#t:FiniteMapX">FiniteMapX</a> m k) => <a href="#t:OrdFiniteMapX">OrdFiniteMapX</a> m k | m -> k</li><li class="src short"><span class="keyword">class</span> <a href="Data-Edison.html#t:AssocX">AssocX</a> m k => <a href="#t:Assoc">Assoc</a> m k | m -> k</li><li class="src short"><span class="keyword">class</span> (<a href="Data-Edison.html#t:Assoc">Assoc</a> m k, <a href="Data-Edison.html#t:OrdAssocX">OrdAssocX</a> m k) => <a href="#t:OrdAssoc">OrdAssoc</a> m k | m -> k</li><li class="src short"><span class="keyword">class</span> (<a href="Data-Edison.html#t:Assoc">Assoc</a> m k, <a href="Data-Edison.html#t:FiniteMapX">FiniteMapX</a> m k) => <a href="#t:FiniteMap">FiniteMap</a> m k | m -> k</li><li class="src short"><span class="keyword">class</span> (<a href="Data-Edison.html#t:OrdAssoc">OrdAssoc</a> m k, <a href="Data-Edison.html#t:FiniteMap">FiniteMap</a> m k) => <a href="#t:OrdFiniteMap">OrdFiniteMap</a> m k | m -> k</li><li class="src short">module <a href="Data-Edison-Prelude.html">Data.Edison.Prelude</a></li></ul></div><div id="interface"><h1 id="g:1">Sequence class
</h1><div class="top"><p class="src"><span class="keyword">class</span> (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Control-Monad.html#t:Functor">Functor</a> s, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Control-Monad.html#t:MonadPlus">MonadPlus</a> s) => <a name="t:Sequence" class="def">Sequence</a> s <a href="src/Data-Edison-Seq.html#Sequence" class="link">Source</a></p><div class="doc"><p>The <code><a href="Data-Edison.html#t:Sequence">Sequence</a></code> class defines an interface for datatypes which
implement sequences. A description for each function is
given below.
</p></div><div class="subs instances"><p id="control.i:Sequence" class="caption collapser" onclick="toggleSection('i:Sequence')">Instances</p><div id="section.i:Sequence" class="show"><table><tr><td class="src"><a href="Data-Edison.html#t:Sequence">Sequence</a> []</td><td class="doc empty"> </td></tr></table></div></div></div><h1 id="g:2">Collection classes
</h1><h2 id="g:3">Non-observable collections
</h2><div class="top"><p class="src"><span class="keyword">class</span> (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Eq.html#t:Eq">Eq</a> a, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Monoid.html#t:Monoid">Monoid</a> c) => <a name="t:CollX" class="def">CollX</a> c a | c -> a<a href="src/Data-Edison-Coll.html#CollX" class="link">Source</a></p><div class="doc"><p>This is the root class of the collection hierarchy. However, it
is perfectly adequate for many applications that use sets or bags.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> (<a href="Data-Edison.html#t:CollX">CollX</a> c a, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> a) => <a name="t:OrdCollX" class="def">OrdCollX</a> c a | c -> a<a href="src/Data-Edison-Coll.html#OrdCollX" class="link">Source</a></p><div class="doc"><p>Collections for which the elements have an ordering relation.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> <a href="Data-Edison.html#t:CollX">CollX</a> c a => <a name="t:SetX" class="def">SetX</a> c a | c -> a<a href="src/Data-Edison-Coll.html#SetX" class="link">Source</a></p><div class="doc"><p>A collection where the set property is maintained; that is, a set
contains at most one element of the equivalence class formed by the
<code><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Eq.html#t:Eq">Eq</a></code> instance on the elements.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> (<a href="Data-Edison.html#t:OrdCollX">OrdCollX</a> c a, <a href="Data-Edison.html#t:SetX">SetX</a> c a) => <a name="t:OrdSetX" class="def">OrdSetX</a> c a | c -> a<a href="src/Data-Edison-Coll.html#OrdSetX" class="link">Source</a></p><div class="doc"><p>Sets where the elements also have an ordering relation.
This class contains no methods; it is only an abbreviation for
the context <code>(OrdCollX c a,SetX c a)</code>.
</p></div></div><h2 id="g:4">Observable collections
</h2><div class="top"><p class="src"><span class="keyword">class</span> <a href="Data-Edison.html#t:CollX">CollX</a> c a => <a name="t:Coll" class="def">Coll</a> c a | c -> a<a href="src/Data-Edison-Coll.html#Coll" class="link">Source</a></p><div class="doc"><p>Collections with observable elements. See the module documentation for
comments on observability.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> (<a href="Data-Edison.html#t:Coll">Coll</a> c a, <a href="Data-Edison.html#t:OrdCollX">OrdCollX</a> c a) => <a name="t:OrdColl" class="def">OrdColl</a> c a | c -> a<a href="src/Data-Edison-Coll.html#OrdColl" class="link">Source</a></p><div class="doc"><p>Collections with observable elements where the elements additionally
have an ordering relation. See the module documentation for comments
on observability.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> (<a href="Data-Edison.html#t:Coll">Coll</a> c a, <a href="Data-Edison.html#t:SetX">SetX</a> c a) => <a name="t:Set" class="def">Set</a> c a | c -> a<a href="src/Data-Edison-Coll.html#Set" class="link">Source</a></p><div class="doc"><p>Collections with observable elements where the set property is maintained;
that is, a set contains at most one element of the equivalence class
formed by the <code><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Eq.html#t:Eq">Eq</a></code> instance on the elements.
</p><p><em>WARNING: Each of the following \"With\" functions is unsafe.</em>
The passed in combining functions are used to choose which element is kept
in the case of duplicates. They are required to satisfy the precondition
that, given two equal elements, they return a third element equal to the
other two. Usually, the combining function just returns its first or
second argument, but it can combine elements in non-trivial ways.
</p><p>The combining function should usually be associative. Where the function
involves a sequence of elements, the elements will be combined from
left-to-right, but with an unspecified associativity.
</p><p>For example, if <code>x == y == z</code>,
then <code>fromSeqWith (+) [x,y,z]</code> equals either
<code>single (x + (y + z))</code>
or
<code>single ((x + y) + z)</code>
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> (<a href="Data-Edison.html#t:OrdColl">OrdColl</a> c a, <a href="Data-Edison.html#t:Set">Set</a> c a) => <a name="t:OrdSet" class="def">OrdSet</a> c a | c -> a<a href="src/Data-Edison-Coll.html#OrdSet" class="link">Source</a></p><div class="doc"><p>Collections with observable elements where the set property is maintained
and where additionally, there is an ordering relation on the elements.
This class introduces no new methods, and is simply an abbreviation
for the context:
</p><pre>(OrdColl c a,Set c a)</pre></div></div><h1 id="g:5">Associative collection classes
</h1><h2 id="g:6">Non-observable associative collections
</h2><div class="top"><p class="src"><span class="keyword">class</span> (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Eq.html#t:Eq">Eq</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Control-Monad.html#t:Functor">Functor</a> m) => <a name="t:AssocX" class="def">AssocX</a> m k | m -> k<a href="src/Data-Edison-Assoc.html#AssocX" class="link">Source</a></p><div class="doc"><p>The root class of the associative collection hierarchy.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> (<a href="Data-Edison.html#t:AssocX">AssocX</a> m k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.5.0.0/Data-Ord.html#t:Ord">Ord</a> k) => <a name="t:OrdAssocX" class="def">OrdAssocX</a> m k | m -> k<a href="src/Data-Edison-Assoc.html#OrdAssocX" class="link">Source</a></p><div class="doc"><p>An associative collection where the keys additionally have an ordering
relation.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> <a href="Data-Edison.html#t:AssocX">AssocX</a> m k => <a name="t:FiniteMapX" class="def">FiniteMapX</a> m k | m -> k<a href="src/Data-Edison-Assoc.html#FiniteMapX" class="link">Source</a></p><div class="doc"><p>An associative collection where the keys form a set; that is, each key
appears in the associative collection at most once.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> (<a href="Data-Edison.html#t:OrdAssocX">OrdAssocX</a> m k, <a href="Data-Edison.html#t:FiniteMapX">FiniteMapX</a> m k) => <a name="t:OrdFiniteMapX" class="def">OrdFiniteMapX</a> m k | m -> k<a href="src/Data-Edison-Assoc.html#OrdFiniteMapX" class="link">Source</a></p><div class="doc"><p>Finite maps where the keys additionally have an ordering relation.
This class introduces no new methods.
</p></div></div><h2 id="g:7">Observable associative collections
</h2><div class="top"><p class="src"><span class="keyword">class</span> <a href="Data-Edison.html#t:AssocX">AssocX</a> m k => <a name="t:Assoc" class="def">Assoc</a> m k | m -> k<a href="src/Data-Edison-Assoc.html#Assoc" class="link">Source</a></p><div class="doc"><p>Associative collections where the keys are observable.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> (<a href="Data-Edison.html#t:Assoc">Assoc</a> m k, <a href="Data-Edison.html#t:OrdAssocX">OrdAssocX</a> m k) => <a name="t:OrdAssoc" class="def">OrdAssoc</a> m k | m -> k<a href="src/Data-Edison-Assoc.html#OrdAssoc" class="link">Source</a></p><div class="doc"><p>An associative collection with observable keys where the keys additionally
have an ordering relation.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> (<a href="Data-Edison.html#t:Assoc">Assoc</a> m k, <a href="Data-Edison.html#t:FiniteMapX">FiniteMapX</a> m k) => <a name="t:FiniteMap" class="def">FiniteMap</a> m k | m -> k<a href="src/Data-Edison-Assoc.html#FiniteMap" class="link">Source</a></p><div class="doc"><p>Finite maps with observable keys.
</p></div></div><div class="top"><p class="src"><span class="keyword">class</span> (<a href="Data-Edison.html#t:OrdAssoc">OrdAssoc</a> m k, <a href="Data-Edison.html#t:FiniteMap">FiniteMap</a> m k) => <a name="t:OrdFiniteMap" class="def">OrdFiniteMap</a> m k | m -> k<a href="src/Data-Edison-Assoc.html#OrdFiniteMap" class="link">Source</a></p><div class="doc"><p>Finite maps with observable keys where the keys additionally
have an ordering relation. This class introduces no new methods.
</p></div></div><div class="top"><p class="src">module <a href="Data-Edison-Prelude.html">Data.Edison.Prelude</a></p></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.10.0</p></div></body></html>
|