DATA STRUCTURES GALORE version 3.2
--------------------------------------------------------------------------------
_DATA STRUCTURES GALORE version 3.2_
Written by: Carl Eastlund, Jens Axel S�gaard, and Stevie Strickland
Documentation by: Carl Eastlund
Documentation updated: June 7, 2006
--------------------------------------------------------------------------------
------------------------------------------------------------
_Galore Chapter 0: Introduction_
------------------------------------------------------------
This library implements commonly used immutable data structures. Currently
Galore provides:
_Sets_ (collections of distinct elements)
_Bags_ (a.k.a. multi-sets, collections of elements)
_Tables_ (finite mappings from distinct keys to arbitrary values)
(Other data structures provided by previous versions of Galore will be added in
time. The previous versions of Galore will continue to be available in PLaneT.)
These data structures are immutable, meaning that no operation alters its
input. Instead, each operation produces a new data structure, often sharing
some of its structure with its input. This means that old values remain valid
until they are garbage collected and that these structures are safe for
multi-threaded programs.
Each data structure can have multiple implementations. The primary module for
each data structure provides one or more constructors for each implementation,
and operations which work for any of the implementations. Different
implementations may operate on different kinds of data, provide different
invariants, or have different time/space efficiency tradeoffs.
The operations for each data structure are provided by names describing only
their purpose (and not their kind of data structure). To prevent clashes with
each other and with existing Scheme operations, it is recommended to import
these modules with a prefix:
(require (prefix set: (planet "set.ss" ("soegaard" "galore.plt" 3)))
(prefix bag: (planet "bag.ss" ("soegaard" "galore.plt" 3)))
(prefix table: (planet "table.ss" ("soegaard" "galore.plt" 3))))
Data structures are implemented in the MzScheme class system (see documentation
for class.ss). Each kind of data structure is an interface, each implementation
is a class, and each operation is a method. Users can write their own
implementation of Galore data structures by writing classes that implement the
given interfaces. So long as new implementations adhere to the interfaces and
expected invariants, the functions provided by Galore will work with them and
they will be interoperable with all other Galore data structures.
----------------------------------------
Previous Version
----------------------------------------
Galore version 2 supports the following datastructures:
_sets_, _bags_, _heaps_
_finite maps_, _priority queues_
_stacks_, _queues_, _deques_
For any datastructures or operations not yet provided by Galore version 3, use
the previous version:
(require (planet "FILE.scm" ("soegaard" "galore.plt" 2)))
See the documentation for version 2 at:
<http://ja.soegaard.net/planet/html/soegaard/galore.plt/2/0/doc.txt>
----------------------------------------
Notation
----------------------------------------
Specifications for Galore functions are written in the following form:
(function-name [arg1 arg2 ...]) : (PolymorphicType TypeArg)
arg1 : Type1
arg2 : Type2
The first line begins with a template for applying the function. The template
names the function and its arguments. Square brackets enclose optional
arguments (actual applications may provide zero, some, or none of these).
Ellipses follow repeatable arguments to variable-arity functions, which may be
provided zero or more times.
The template is followed by the function's result type. Subsequent lines list
the type of each argument. Polymorphic types are applied like functions; for
instance, a list of symbols would be (Listof Symbol).
------------------------------------------------------------
_Galore Chapter 1: Sets_
------------------------------------------------------------
A (Set Elem) is a collection of distinct elements, each of type Elem.
Galore provides the following operations for creating and manipulating sets.
----------------------------------------
SET CONSTRUCTORS
----------------------------------------
A set implementation must have a way to distinguish its elements (how to tell
whether one element is the same as another). Some implementations need to know
more about their elements, and use this to provide better invariants.
Each implementation provides two constructors. The first accepts set elements
as additional arguments. The second accepts set elements as a list.
For the following specifications, assume:
elem : Elem
elems : (Listof Elem)
--------------------
Unordered sets require an equality predicate for their elements. Most single
element operations will complete in linear time. Unordered sets have two
constructors:
> (make-unordered elem=? elem ...) : (Set Elem)
> (list->unordered elem=? elems) : (Set Elem)
elem=? : Elem Elem -> Boolean
These operations construct a set containing the given elements as distinguished
by elem=?.
--------------------
Ordered sets require a total ordering for their elements. These orderings are
represented as comparisons in the SRFI 67 style. A comparison produces 0 if its
arguments are equal, 1 if the first argument is greater, and -1 if its second
argument is greater. Most single element operations will complete in
logarithmic time. Ordered sets have two constructors:
> (make-ordered elem-compare elem ...) : (Set Elem)
> (list->ordered elem-compare elems) : (Set Elem)
elem-compare : Elem Elem -> -1 or 0 or 1
These operations construct a set containing the given elements as distinguished
by elem-compare. Operations which traverse the set will traverse the elements
in increasing order.
--------------------
Hashed sets group their elements by hash code; the hash function must respect
the given equality predicate (equal values must have the same hash code).
Operations will take time logarithmic in the number of distinct hash codes and
linear in the number of elements in a single hash code. Hashed sets have two
constructors:
> (make-hashed elem-hash elem=? elem ...) : (Set Elem)
> (list->hashed elem-hash elem=? elems) : (Set Elem)
elem-hash : Elem -> Integer
elem=? : Elem Elem -> Boolean
These operations construct a set containing the given elements as distinguished
by elem=?.
--------------------
Galore also provides six shortcut constructors for sets whose elements are
distinguished by the standard Scheme comparisons eq?, eqv?, and equal?.
> (make-eq elem ...) : (Set Elem)
> (list->eq elems) : (Set Elem)
These operations construct a hashed set containing the given elements as
distinguished by eq?.
> (make-eqv elem ...) : (Set Elem)
> (list->eqv elems) : (Set Elem)
These operations construct an unordered set containing the given elements as
distinguished by eqv?.
> (make-equal elem ...) : (Set Elem)
> (list->equal elems) : (Set Elem)
These operations construct a hashed set containing the given elements as
distinguished by equal?.
----------------------------------------
SET PREDICATES
----------------------------------------
These operations determine whether values are sets.
> (set? v) : Boolean
Reports whether v is a set.
> set/c : FlatContract
> non-empty-set/c : FlatContract
These contracts accept sets. The non-empty-set/c contract requires sets to
contain at least one element.
> (set-of/c elem/c) : FlatContract
> (non-empty-set-of/c elem/c) : FlatContract
elem/c : FlatContract (or predicate)
These produce a contract that accepts sets of type (Set Elem), where elem/c
accepts elements of type Elem. The result of non-empty-set-of/c requires sets
to contain at least one element.
----------------------------------------
SET ACCESSORS
----------------------------------------
These operations extract information from a set.
For the following specifications, assume:
elem : Elem
set : (Set Elem)
> (elements set) : (Listof Elem)
Produces a list of all of set's elements. The elements are in increasing order
for ordered sets.
> (empty? set) : Boolean
Reports whether set contains no elements.
> (size set) : NaturalNumber
Produces the number of elements in set.
> (member? elem set) : Boolean
Reports whether set contains elem.
> (lookup elem set [failure-thunk success-function]) : T
failure-thunk : -> T
success-function : Elem -> T
Finds an element in set that is equal to elem.
If such an element e is found, lookup produces (success-function e).
If no such element is found, lookup produces (failure-thunk).
The default success-function returns e.
The default failure-thunk returns #f.
> (select set) : Elem
Produces an element from the non-empty set. It is unspecified which
element is produced.
----------------------------------------
SET UPDATERS
----------------------------------------
These operations construct updated forms of their input set. The result is
always of the same implementation as the input.
For the following specifications, assume:
elem : Elem
set : (Set Elem)
> (insert elem set) : (Set Elem)
Produces a set containing elem and all elements of set.
> (remove elem set) : (Set Elem)
Produces a set containing all elements of set except elem.
> (clear set) : (Set Elem)
Produces an empty set.
----------------------------------------
SET TRAVERSALS
----------------------------------------
These operations work on each element of a set. Each traversal works on
elements in the same order they are produced by the elements operation.
For the following specifications, assume:
set : (Set Elem)
predicate : Elem -> Boolean
> (fold combine init set) : T
combine : Elem T -> T
init : T
Builds a result from set's elements. If (elements set) is (list e1 e2 ... en),
the result is (combine en ... (combine e2 (combine e1 init))...).
> (map transform set) : (Set Elem)
transform : Elem -> Elem
Produces a new set containing the transformed image of each element of set.
> (for-each action set) : Void
action : Elem -> Void
Calls action for each element of set.
> (filter predicate set) : (Set Elem)
Produces a set containing the elements of set that satisfy predicate. The
result is of the same implementation as set.
> (all? predicate set) : Boolean
> (andmap predicate set) : Boolean
Reports whether all elements of set satify predicate. These operations are
synonymous.
> (any? predicate set) : Boolean
> (ormap predicate set) : Boolean
Reports whether any element of set satisfies predicate. These operations are
synonymous.
----------------------------------------
SET COMBINATIONS
----------------------------------------
These operations represent set-theoretic operations combining multiple sets. In
all cases, the result is of the same implementation as the first set argument.
Multiple sets may only be combined if their notions of distinct elements are the
same. If two sets with different equality are combined the result will be
unpredictable and may yield an error. Here are some concrete examples:
- (make-unordered = 1 2 3) and (make-ordered number-compare 4 5 6) may be
combined, because = and number-compare represent the same equality relation.
Both will distinguish numbers based on numerical equivalence.
- (make-equal "A" "B" "C") and (make-eq "A" "B" "C") may not be combined,
because equal? and eq? do not represent the same equality relation.
Specifically, it is ambiguous whether both "A"s represent equivalent elements.
For the following specifications, assume:
set1 : (Set Elem)
set2 : (Set Elem)
combine : Elem Elem -> Elem
> (union set1 set2 [combine]) : (Set Elem)
Produces a set containing all elements present in either set1 or set2. If set1
and set2 contain equivalent elements e1 and e2 respectively, union adds (combine
e1 e2) to the result in their place. The default combine returns e1.
> (intersection set1 set2 [combine]) : (Set Elem)
Produces a set containing all elements present in both set1 and set2.
For each pair of equivalent elements e1 and e2 found in set1 and set2
respectively, intersection adds (combine e1 e2) to the result. The default
combine returns e1.
> (difference set1 set2) : (Set Elem)
Produces a set containing all elements of set1 not found in set2.
----------------------------------------
SET RELATIONS
----------------------------------------
These operations compare multiple sets. As in set combinations (above),
multiple sets may only be meaningfully compared if their notions of distinct
elements are the same.
For the following specifications, assume:
set1 : (Set Elem)
set2 : (Set Elem)
> (subset? set1 set2) : Boolean
Reports whether all elements in set1 are present in set2.
> (equal? set1 set2) : Boolean
Reports whether both sets contain the same elements.
----------------------------------------
SETS AND EAGER COMPREHENSIONS
----------------------------------------
Support for srfi-42 eager comprehensions are provided by comprehensions.ss.
Requiring (planet "comprehensions.ss" ("soegaard" "galore.plt" 3)) will
provide the comprehension set-ec and the generator :set.
> (set-ec <empty-expr> <qualifier>* <expression>)
The comprehension set-ec evaluates the expression <empty-expr> whose
result must be an empty set. Then the values obtained by evaluating
<expression> once for each binding are inserted into the set. If
there are no qualifiers the result is a singleton set whose element
is the result of evaluating <expression>.
> (:set <var> <arg>)
The generator :set runs through the elements in a set. First <arg>
is evaluated then the variable <var> is bound to each element
of the set in turn. The effect of assigning a value to <var> is
undefined.
Example
- - - -
> (require (prefix set: (planet "set.ss" ("soegaard" "galore.plt" 3))
(planet "comprehensions.ss" ("soegaard" "galore.plt" 3))
(lib "42.ss" "srfi")
(lib "67.ss" "srfi"))
> (define a-set
(set-ec (set:make-ordered integer-compare)
(:range i -5 5)
(* i i)))
> (set:elements a-set)
(0 1 4 9 16 25)
> (list-ec (:set x a-set)
x)
(0 1 4 9 16 25)
> (list-ec (: x a-set)
x)
(0 1 4 9 16 25)
------------------------------------------------------------
_Galore Chapter 2: Tables_
------------------------------------------------------------
A (Table Key Value) is a finite mapping from distinct keys of type Key to
distinct values of type Value. A single key/value pair in a table is called a
binding.
Galore provides the following operations for creating and manipulating tables.
----------------------------------------
TABLE CONSTRUCTORS
----------------------------------------
A table implementation must be able to distinguish its keys just like a set
implementation must distinguish its elements. Like sets, tables have different
implementations that require different information about their keys.
Each implementation provides four constructors. The first accepts bindings as
additional arguments, alternating keys and values. The second accepts bindings
as an s-expression: a list of two-element lists, each a key followed by a
value. The third accepts bindings as an association list of key/value pairs.
The last accepts bindings as a list of keys and a separate list of their
respective values.
For the following specifications, assume:
key : Key
value : Value
keys : (Listof Key)
values : (Listof Value)
sexp : (Listof (list Key Value))
alist : (Listof (cons Key Value))
--------------------
Unordered tables require an equality predicate for their keys. Most
single-binding operations will complete in linear time. Unordered sets have
four constructors:
> (make-unordered key=? key value ...) : (Table Key Value)
> (sexp->unordered key=? sexp) : (Table Key Value)
> (alist->unordered key=? alist) : (Table Key Value)
> (lists->unordered key=? keys values) : (Table Key Value)
key=? : (Key Key -> Boolean)
These operations construct a table containing the given bindings with keys
distinguished by key=?.
--------------------
Ordered tables require a total ordering for their keys. These orderings are
represented as comparisons in the SRFI 67 style (see description for ordered
sets, above). Most single-binding operations will complete in logarithmic time.
Ordered tables have four constructors:
> (make-ordered key-compare key value ...) : (Table Key Value)
> (sexp->ordered key-compare sexp) : (Table Key Value)
> (alist->ordered key-compare alist) : (Table Key Value)
> (lists->ordered key-compare keys values) : (Table Key Value)
key-compare : Key Key -> -1 or 0 or 1
These operations construct a table containing the given bindings with keys
distinguished by key-compare. Operations which traverse the table will traverse
the bindings in increasing order of their keys.
--------------------
Hashed tables group their keys by hash code; the hash function must respect the
given equality predicate (equal keys must have the same hash code). Operations
will take time logarithmic in the number of distinct hash codes and linear in
the number of keys in a single hash code. Hashed tables have four constructors:
> (make-hashed key-hash key=? key value ...) : (Table Key Value)
> (sexp->hashed key-hash key=? sexp) : (Table Key Value)
> (alist->hashed key-hash key=? alist) : (Table Key Value)
> (lists->hashed key-hash key=? keys values) : (Table Key Value)
These operations construct a table containing the given bindings with keys
distinguished by key=?.
--------------------
Galore also provides shortcut constructors for tables whose keys are
distinguished by the standard Scheme comparisons eq?, eqv?, and equal?.
> (make-eq key value ...) : (Table Key Value)
> (sexp->eq sexp) : (Table Key Value)
> (alist->eq alist) : (Table Key Value)
> (lists->eq keys values) : (Table Key Value)
These operations construct a hashed table containing the given bindings with
keys distinguished by eq?.
> (make-eqv key value ...) : (Table Key Value)
> (sexp->eqv sexp) : (Table Key Value)
> (alist->eqv alist) : (Table Key Value)
> (lists->eqv keys values) : (Table Key Value)
These operations construct an unordered table containing the given bindings with
keys distinguished by eqv?.
> (make-equal key value ...) : (Table Key Value)
> (sexp->equal sexp) : (Table Key Value)
> (alist->equal alist) : (Table Key Value)
> (lists->equal keys values) : (Table Key Value)
These operations construct a hashed table containing the given bindings with
keys distinguished by equal?.
----------------------------------------
TABLE PREDICATES
----------------------------------------
These operations determine whether values are tables.
> (table? v) : Boolean
Reports whether v is a table.
> table/c : FlatContract
> non-empty-table/c : FlatContract
These contracts accept tables. The non-empty-table/c contract requires tables
to contain at least one binding.
> (table-of/c key/c value/c) : FlatContract
> (non-empty-table-of/c key/c value/c) : FlatContract
key/c : FlatContract (or predicate)
value/c : FlatContract (or predicate)
These produce a contract that accepts tables of type (Table Key Value), where
key/c accepts keys of type Key and value/c accepts values of type Value. The
result of non-empty-table-of/c requires tables to contain at least one binding.
----------------------------------------
TABLE ACCESSORS
----------------------------------------
These operations extract information from a table.
For the following specifications, assume:
key : Key
table : (Table Key Velue)
> (keys table) : (Listof Key)
Produces a list of table's keys. For ordered tables, the keys are sorted from
least to greatest.
> (values table) : (Listof Value)
Produces a list of table's values. The values appear in the same order as their
respective keys in (keys table).
> (to-sexp table) : (Listof (list Key Value))
Produces a list of table's bindings as two-element lists, each a key followed by
its value. The bindings appear in the same order as their respective keys in
(keys table).
> (to-alist table) : (Listof (cons Key Value))
Produces an association list of table's bindings as key/value pairs. The
bindings appear in the same order as their respective keys in (keys table).
> (empty? table) : Boolean
Reports whether table contains no bindings.
> (size table) : NaturalNumber
Produces the number of bindings in table.
> (contains? key table) : Boolean
Reports whether table contains key.
> (lookup key table [failure-thunk success-function]) : T
failure-thunk : -> T
success-function : Value -> T
Looks up the value bound to key in table.
If such a value v is found, lookup preoduces (success-function v).
If no such value is found, lookup produces (failure-thunk).
The default success-function returns v.
The default failure-thunk returns #f.
> (lookup/key key table [failure-thunk success-function]) : T
failure-thunk : -> T
success-function : Key Value ->T
Looks up the binding for key in table.
If a binding of k to v is found, lookup/key produces (success-function k v).
If no such binding is found, lookup/key produces (failure-thunk).
The default success-function returns k.
The default failure-thunk returns #f.
> (select table) : (values Key Value)
> (select/key table) : Key
> (select/value table) : Value
These operations select a binding from a non-empty table, returning its key,
value, or both as appropriate. It is not specified which binding is chosen.
----------------------------------------
TABLE UPDATERS
----------------------------------------
These operations construct updated forms of their input table. The result is
always of the same implementation as the input.
For the following specifications, assume:
key : Key
value : Value
table : (Table Key Value)
> (insert key value table) : (Table Key Value)
Produces a table in which key is bound to value and containing all other
bindings of table.
> (remove key table) : (Table Key Value)
Produces a table containing all bindings of table except any binding for key.
> (update key transform table) : (Table Key Value)
transform : Key Value -> Value
Produces a table with all bindings of table except any binding for key. If
table maps k to v (with k equal to key), the result maps k to (transform k v).
If table has no binding for key, the result has none.
> (update/value key transform table) : (Table Key Value)
transform : Value -> Value
As update, but produces a new value based only on the previous value.
> (update/insert key transform value table) : (Table Key Value)
transform : Key Value -> Value
Produces a table with all bindings of table except any binding for key. If
table maps key to v, the result maps key to (transform v). If table has no
binding for key, the result maps key to value.
> (update/insert/value key transform value table) : (Table Key Value)
transform : Value -> Value
As update/insert, but produces a new value based only on the previous value.
> (clear table) : (Table Key Value)
Produces an empty table.
----------------------------------------
TABLE TRAVERSALS
----------------------------------------
These operations work on each binding of a table. Each traversal works on
bindings in the same order their keys are produced by the keys operation. Each
traversal has three forms. The basic form processes they key and value of each
binding. The "/key" form processes only the key of each binding. The "/value"
form processes only the value of each binding.
For the following specifications, assume:
set : (Set Elem)
> (fold combine init table) : T
> (fold/key combine/key init table) : T
> (fold/value combine/value init table) : T
combine : Key Value T -> T
combine/key : Key T -> T
combine/value : Value T -> T
These operations build a result from table's bindings. If (keys table) produces
(list k1 k2 ... kn) and (values table) produces (list v1 v2 ... vn), the
respective results will be:
(combine kn vn ... (combine k2 v2 (combine k1 v1 init))...)
(combine/key kn ... (combine/key k2 (combine/key k1 init))...)
(combine/value vn ... (combine/value v2 (combine/value v1 init))...)
> (for-each action table) : T
> (for-each/key action/key table) : T
> (for-each/value action/value table) : T
action : Key Value -> Void
action/key : Key -> Void
action/value : Value -> Void
These operations call action (or action/key or action/value) for each binding in
table.
> (map transform table) : (Table Key Image)
> (map/key transform/key table) : (Table Key Image)
> (map/value transform/value table) : (Table Key Image)
transform : Key Value -> Image
transform/key : Key -> Image
transform/value : Value -> Image
These operations produce a table binding each key from table to the image of the
previous binding produced by transform (or transform/key or transform/value).
The result is of the same implementation as table.
> (filter predicate table) : (Table Key Value)
> (filter/key predicate/key table) : (Table Key Value)
> (filter/value predicate/value table) : (Table Key Value)
predicate : Key Value -> Boolean
predicate/key : Key -> Boolean
predicate/value : Value -> Boolean
These operations produce a table containing each binding in table that satisfies
predicate (or predicate/key or predicate/value). The result is of the same
implementation as table.
> (all? predicate table) : Boolean
> (all?/key predicate/key table) : Boolean
> (all?/value predicate/value table) : Boolean
> (andmap predicate table) : Boolean
> (andmap/key predicate/key table) : Boolean
> (andmap/value predicate/value table) : Boolean
predicate : Key Value -> Boolean
predicate/key : Key -> Boolean
predicate/value : Value -> Boolean
Reports whether all bindings of table satisfy predicate (or predicate/key or
predicate/value). The all? variants are synonymous with the andmap variants.
> (any? predicate table) : Boolean
> (any?/key predicate/key table) : Boolean
> (any?/value predicate/value table) : Boolean
> (ormap predicate table) : Boolean
> (ormap/key predicate/key table) : Boolean
> (ormap/value predicate/value table) : Boolean
predicate : Key Value -> Boolean
predicate/key : Key -> Boolean
predicate/value : Value -> Boolean
Reports whether any binding of table satisfies predicate (or predicate/key or
predicate/value). The any? variants are synonmous with the ormap variants.
----------------------------------------
TABLE COMBINATIONS
----------------------------------------
These operations mimic set operations combining the bindings of multiple tables
by their corresponding keys. In all cases, the result is of the same
implementation as the first table argument.
Multiple tables may only be combined if their notion of distinct keys are the
same. If two tables with different equality are combined the result will be
unpredictable and may yield an error. For concrete examples, see the section on
Set Combinations above.
For the following specifications, assume:
table1 : (Table Key Value)
table2 : (Table Key Value)
combine : Key Value Value -> Value
combine/value : Value Value -> Value
> (union table1 table2 [combine]) : (Table Key Value)
> (union/value table1 table2 [combine/value]) : (Table Key Value)
These operations produce a table containing all bindings present in either
table1 or table2. If table1 and table2 bind key k to values v1 and v2
respectively, union binds k to (combine k v1 v2) and union/value binds k to
(combine/value v1 v2) in the result. The default combine and combine/value
return v1.
> (intersection table1 table2 [combine]) : (Table Key Value)
> (intersection/value table1 table2 [combine/value]) : (Table Key Value)
These operations produce a table containing all bindings present in both table1
and table2. For each key k bound to values v1 and v2 in table1 and table2
respectively, intersection binds k to (combine k v1 v2) and intersection/value
binds k to (combine/value v1 v2) in the result. The default combine and
combine/value return v1.
> (difference table1 table2) : (Table Key Value)
Produces a table containing all bindings of table1 whose key is not in table2.
----------------------------------------
TABLE RELATIONS
----------------------------------------
These operations compare multiple tables. As in table combinations (above),
multiple tables may only be meaningfully compared if their notions of distinct
keys are the same.
For the following specifications, assume:
table1 : (Table Key Value)
table2 : (Table Key Value)
value=? : (Value Value -> Boolean)
> (subtable? value=? table1 table2) : Boolean
Reports whether all keys in table1 are present in table2, and that the values
bound to each key in both tables are the same with respect to value=?.
> (equal? value=? table1 table2) : Boolean
Reports whether both tables contain the same keys, and that the values bound to
each key in both tables are the same with respect to value=?.
------------------------------------------------------------
_Galore Chapter 3: Bags_
------------------------------------------------------------
A (Bag Elem) is a collection of elements, each of type Elem. Unlike sets,
the elements in a bag need not be distinct.
Galore provides the following operations for creating and manipulating bags.
----------------------------------------
BAG CONSTRUCTORS
----------------------------------------
A bag implementation must have a way to distinguish its elements (how to tell
whether one element is the same as another). Some implementations need to know
more about their elements, and use this to provide better invariants.
Each implementation provides two constructors. The first accepts bag elements
as additional arguments. The second accepts bag elements as a list.
For the following specifications, assume:
elem : Elem
elems : (Listof Elem)
--------------------
Unordered bags require an equality predicate for their elements. Most single
element operations will complete in linear time. Unordered bags have two
constructors:
> (make-unordered elem=? elem ...) : (Bag Elem)
> (list->unordered elem=? elems) : (Bag Elem)
elem=? : Elem Elem -> Boolean
These operations construct a bag containing the given elements as distinguished
by elem=?.
--------------------
Ordered bags require a total ordering for their elements. These orderings are
represented as comparisons in the SRFI 67 style. A comparison produces 0 if its
arguments are equal, 1 if the first argument is greater, and -1 if its second
argument is greater. Most single element operations will complete in
logarithmic time. Ordered bags have two constructors:
> (make-ordered elem-compare elem ...) : (Bag Elem)
> (list->ordered elem-compare elems) : (Bag Elem)
elem-compare : Elem Elem -> -1 or 0 or 1
These operations construct a bag containing the given elements as distinguished
by elem-compare. Operations which traverse the bag will traverse the elements
in increasing order.
--------------------
Hashed bags group their elements by hash code; the hash function must respect
the given equality predicate (equal values must have the same hash code).
Operations will take time logarithmic in the number of distinct hash codes and
linear in the number of elements in a single hash code. Hashed bags have two
constructors:
> (make-hashed elem-hash elem=? elem ...) : (Bag Elem)
> (list->hashed elem-hash elem=? elems) : (Bag Elem)
elem-hash : Elem -> Integer
elem=? : Elem Elem -> Boolean
These operations construct a bag containing the given elements as distinguished
by elem=?.
--------------------
Galore also provides six shortcut constructors for bags whose elements are
distinguished by the standard Scheme comparisons eq?, eqv?, and equal?.
> (make-eq elem ...) : (Bag Elem)
> (list->eq elems) : (Bag Elem)
These operations construct a hashed bag containing the given elements as
distinguished by eq?.
> (make-eqv elem ...) : (Bag Elem)
> (list->eqv elems) : (Bag Elem)
These operations construct an unordered bag containing the given elements as
distinguished by eqv?.
> (make-equal elem ...) : (Bag Elem)
> (list->equal elems) : (Bag Elem)
These operations construct a hashed bag containing the given elements as
distinguished by equal?.
----------------------------------------
BAG PREDICATES
----------------------------------------
These operations determine whether values are bags.
> (bag? v) : Boolean
Reports whether v is a bag.
> bag/c : FlatContract
> non-empty-bag/c : FlatContract
These contracts accept bags. The non-empty-bag/c contract requires bags to
contain at least one element.
> (bag-of/c elem/c) : FlatContract
> (non-empty-bag-of/c elem/c) : FlatContract
elem/c : FlatContract (or predicate)
These produce a contract that accepts bags of type (Bag Elem), where elem/c
accepts elements of type Elem. The result of non-empty-bag-of/c requires bags
to contain at least one element.
----------------------------------------
BAG ACCESSORS
----------------------------------------
These operations extract information from a bag.
For the following specifications, assume:
elem : Elem
bag : (Bag Elem)
> (elements bag) : (Listof Elem)
Produces a list of all of the bag's elements. The elements are in increasing
order for ordered bags.
> (to-sexp bag) : (Listof (List Elem PositiveNumber))
Produces a list of lists where each list contains an element of the
bag and how many times that element appears in the bag. The ordering
is the same as for (elements bag).
> (to-alist bag) : (Listof (cons Elem PositiveNumber))
Produces a list of pairs where each pair contains an element of the
bag and how many times that element appears in the bag. The ordering
is the same as for (elements bag).
> (empty? bag) : Boolean
Reports whether bag contains no elements.
> (size bag) : NaturalNumber
Produces the number of elements in bag.
> (size/unique bag) : NaturalNumber
Produces the number of distinct elements in the bag.
> (member? elem bag) : Boolean
Reports whether bag contains elem.
> (count elem bag) : NaturalNumber
Produces the number of times the element appears in the bag. If it does
not, then 0 is produced.
> (lookup elem bag [failure-thunk success-function]) : T
failure-thunk : -> T
success-function : Elem -> T
Finds an element in bag that is equal to elem.
If such an element e is found, lookup produces (success-function e).
If no such element is found, lookup produces (failure-thunk).
The default success-function returns e.
The default failure-thunk returns #f.
> (lookup/count elem bag [failure-thunk success-function]) : T
failure-thunk : -> T
success-function : Elem PositiveNumber -> T
Finds an element in bag that is equal to elem.
If such an element e is found, lookup produces (success-function e c)
(where c is the element's count).
If no such element is found, lookup produces (failure-thunk).
The default success-function returns e.
The default failure-thunk returns #f.
> (select bag) : Elem
Produces an element from the non-empty bag. It is unspecified which
element is produced.
> (select/count bag) : (values Elem PositiveNumber)
Produces an element and its count from the non-empty bag. It is
unspecified which element is produced.
----------------------------------------
BAG UPDATERS
----------------------------------------
These operations construct updated forms of their input bag. The result is
always of the same implementation as the input.
For the following specifications, assume:
elem : Elem
n : NaturalNumber
bag : (Bag Elem)
> (insert elem bag) : (Bag Elem)
Produces a bag containing all elements of bag, plus one more occurrence of
elem.
> (insert/count elem n bag) : (Bag Elem)
Produces a bag containing all elements of bag, plus n more occurrences of elem.
> (remove elem bag) : (Bag Elem)
Produces a bag containing all elements of bag except one less occurence of elem,
or no occurrences if bag had none.
> (remove/count elem n bag) : (Bag Elem)
Produces a bag containing all elements of bag except n less occurrences of elem,
or no occurrences if there were less than n occurrences.
> (clear bag) : (Bag Elem)
Produces an empty bag.
----------------------------------------
BAG TRAVERSALS
----------------------------------------
These operations work on each element of a bag. Each traversal works on
elements in the same order they are produced by the elements operation.
For the following specifications, assume:
bag : (Bag Elem)
predicate : Elem -> Boolean
> (fold combine init bag) : T
combine : Elem T -> T
init : T
Builds a result from bag's elements. If (elements bag) is (list e1 e2 ... en),
the result is (combine en ... (combine e2 (combine e1 init))...).
> (fold/count combine init bag) : T
combine : Elem PositiveNumber T -> T
init : T
Like fold, but the combining function also takes an element count.
> (map transform bag) : (Bag Elem)
transform : Elem -> Elem
Produces a new bag containing the transformed image of each element of the bag.
> (map/count transform bag) : (Bag Elem)
transform : Elem PositiveNumber -> Elem
Like map, but the transforming function also takes an element count.
> (for-each action bag) : Void
action : Elem -> Void
Calls action for each element of bag.
> (for-each/count action bag) : Void
action : Elem PositiveNumber -> Void
Like for-each, but the action takes an element count as well.
> (filter predicate bag) : (Bag Elem)
Produces a bag containing the elements of bag that satisfy predicate. The
result is of the same implementation as bag.
> (filter/count predicate/count bag) : (Bag Elem)
predicate/count : Elem PositiveNumber -> Boolean
Like filter, but the predicate takes an element count as well.
> (all? predicate bag) : Boolean
> (andmap predicate bag) : Boolean
Reports whether all elements of bag satify predicate. These operations are
synonymous.
> (any? predicate bag) : Boolean
> (ormap predicate bag) : Boolean
Reports whether any element of bag satisfies predicate. These operations are
synonymous.
> (all?/count predicate/count bag) : Boolean
> (andmap/count predicate/count bag) : Boolean
> (any?/count predicate/count bag) : Boolean
> (ormap/count predicate/count bag) : Boolean
predicate/count : Elem PositiveNumber -> Boolean
Like their non-/count versions, except the predicate also takes an element
count.
----------------------------------------
BAG COMBINATIONS
----------------------------------------
These operations represent bag-theoretic operations combining multiple bags. In
all cases, the result is of the same implementation as the first bag argument.
Multiple bags may only be combined if their notions of distinct elements are the
same. If two bags with different equality are combined the result will be
unpredictable and may yield an error. Here are some concrete examples:
- (make-unordered = 1 2 3) and (make-ordered number-compare 4 5 6) may be
combined, because = and number-compare represent the same equality relation.
Both will distinguish numbers based on numerical equivalence.
- (make-equal "A" "B" "C") and (make-eq "A" "B" "C") may not be combined,
because equal? and eq? do not represent the same equality relation.
Specifically, it is ambiguous whether both "A"s represent equivalent elements.
For the following specifications, assume:
bag1 : (Bag Elem)
bag2 : (Bag Elem)
> (union bag1 bag2) : (Bag Elem)
Produces a bag containing all elements present in either bag1 or bag2.
If bag1 and bag2 contain equivalent elements e1 and e2 respectively,
union adds e1 to the result in their place with a total number of
occurrences equal to the maximum of either e1's occurrences in bag1 or
e2's occurrences in bag2.
> (intersection bag1 bag2) : (Bag Elem)
Produces a bag containing all elements present in both bag1 or bag2.
If bag1 and bag2 contain equivalent elements e1 and e2 respectively,
intersection adds e1 to the result in their place with a total number
of occurrences equal to the minimum of either e1's occurrences in bag1
and e2's occurrences in bag2.
> (difference bag1 bag2) : (Bag Elem)
Produces a bag containing all elements of bag1 not found in bag2.
This means that if an element appears in bag1 n times and bag2 m
times, then the resulting bag will have n - m copies of the element
(and will not contain it if n - m <= 0).
----------------------------------------
BAG RELATIONS
----------------------------------------
These operations compare multiple bags. As in bag combinations (above),
multiple bags may only be meaningfully compared if their notions of distinct
elements are the same.
For the following specifications, assume:
bag1 : (Bag Elem)
bag2 : (Bag Elem)
> (subbag? bag1 bag2) : Boolean
Reports whether all elements in bag1 are present in bag2. This includes
checking that the number of times the element appears in bag2 is at least
as many as the number of times it appears in bag1.
> (equal? bag1 bag2) : Boolean
Reports whether both bags contain the same elements with the same number of
occurrences.
------------------------------------------------------------
Acknowledgements
------------------------------------------------------------
- The red-black trees implementation started as a port of
Jean-Christophe Filliatre's Ocaml implementation.
- Versions 1 and 2 of Galore and its documentation were
written entirely by Jens Axel S�gaard.
- Many thanks to Richard Cobbe and Sam Tobin-Hochstadt
for helpful proofreading and functionality suggestions.
------------------------------------------------------------
References
------------------------------------------------------------
For more information on persistent data structures, see the following sources.
[Ada] Adams, Stepehn, "Implementing Sets Efficiently in a Functional Language"
[Mar] Martinez, Conrado and Roura, Salvador: "Randomized Binary Search Trees"
[Oka] Chris Okasaki, "Purely Functional Data Structures"
------------------------------------------------------------
Contact Information
------------------------------------------------------------
For any questions not answered by this documentation, write to the PLT Scheme
mailing list at:
[email protected]
Alternately, contact one of the authors:
Carl Eastlund <[email protected]>
Jens Axel S�gaard <[email protected]>
Stevie Strickland <[email protected]>
------------------------------------------------------------
Copyright and License
------------------------------------------------------------
This documentation and all source code of Galore are published under the terms
of the GNU LGPL. See license.txt and lgpl.txt in the Galore collection for more
details.
------------------------------------------------------------
Keywords
------------------------------------------------------------
_galore_ _set_ _table_ _hash_ _association_ _binding_ _mapping_ _key_
_functional_ _persistent_ _immutable_
![[logo]](/logo.png){kind=logo}