• Home
• All tickets
• All wiki pages

Source for wiki ImmutableDataStructuresWortman version 2

author

kevinwortman

comment

Minor edits

ipnr

127.10.177.1

name

ImmutableDataStructuresWortman

readonly

0

text

= Introduction =

(TODO)

= Efficiency bounds =

We specify required time efficiency upper bounds using big-O notation. We note when, in some cases, there is "slack" between the required bound and the theoretically optimal bound for an operation. Implementations may use data structures with amortized time bounds, but should document which bounds hold in only an amortized sense. The use of randomized data structures with expected time bounds is discouraged.

= Deque =

A deque (conventionally pronounced "deck") is a queue data structure that supports efficient manipulation of either of its ends. It may be used in place of a (LIFO) stack or (FIFO) queue.

The ''unlabeled finger tree'' data structure can meet all these requirements rather conveniently.

=== Construction ===

{{{#!scheme
(ideque [element...])
}}}

Create a new deque containing {{{element...}}}. The leftmost element (if any) will be at the front of the deque and the rightmost element (if any) will be at the back. Takes O(n) time, where n is the number of elements.

=== Queries ===

{{{#!scheme
(ideque? x)
(ideque-empty? deque)
(ideque-size deque)
}}}

{{{ideque?}}} and {{{ideque-empty?}}} take O(1) time; {{{ideque-size}}} may take O(n) time, though O(1) is optimal.

=== Queue operations ===

{{{#!scheme
(ideque-front deque)
(ideque-back deque)
}}}
Return the front/back element. It is an error for {{{deque}}} to be empty. Each takes O(1) time.

{{{#!scheme
(ideque-push-front deque x)
(ideque-push-back deque x)
}}}
Return a new deque with {{{x}}} pushed to the front/back of {{{deque}}}. Each takes O(1) time.

=== Miscellaneous ===

{{{#!scheme
(ideque-append deque...)
}}}
Return a new deque with the contents of the first argument deque followed by the others. Takes O(kn) time, where k is the number of deques and n is the number of elements involved, though O(k log n) is possible.

=== Conversion ===

{{{#!scheme
(list->ideque list)
(ideque->list deque)
}}}

Conversion between deque and list structures. FIFO order is preserved, so the front of a list corresponds to the front of a deque. Each operation takes O(n) time.

= Set =

A sorted set data structure stores a finite collection of unique orderable (a.k.a. comparable or sortable) elements.

These requirements can be satisfied by many flavors of ''self-balancing binary trees.'' Red-black trees, 1-2 brother trees, and labeled 2-3 finger trees are particularly convenient in an immutable context.


=== Order predicates ===

An ''order predicate'' for a set of orderable elements is a procedure {{{precedes?}}} such that, for set elements {{{x}}} and {{{y}}},
{{{#!scheme
(precedes? x y)
}}}
returns non-{{{#false}}} iff {{{x}}} precedes {{{y}}} in the set's ordering. It returns {{{#false}}} when {{{x}}} succeeds (comes after) {{{y}}} or when the elements are tied for the same position.

Note that {{{<}}}, {{{char<?}}}, and {{{string<?}}} are valid order predicates for sets of numbers, characters, and strings, respectively.

It is essential that order predicates return {{{#false}}} in the case of equal elements, as implementations may test for element equality with expressions of the form
{{{#!scheme
(and (not (precedes? x y))
     (not (precedes? y x)))
}}}

The time bounds stated below are all based on the assumption that evaluating an order predicate takes O(1) time.

=== Construction ===

{{{#!scheme
(iset precedes? [element...])
}}}
Return a new set using the order predicate {{{precedes?}}} and containing elements {{{element...}}}. If any subset of element arguments are equal according to {{{precedes?}}} then only the leftmost of them is a member of the returned set. Takes O(n log n) time.

=== Set queries ===

{{{#!scheme
(iset? x)
(iset-empty? set)
(iset-size set)
(iset-order-predicate set)
}}}

{{{iset-size}}} may take O(n) time, though O(1) is optimal. The other procedures take O(1) time.

=== Set operations ===

{{{#!scheme
(iset-union set...)
(iset-intersection set...)
(iset-difference left right...)
(iset-symmetric-difference left right...)
}}}

Return a new set containing the union/intersection/difference/symmetric difference of the arguments. All the arguments must be sets sharing an equivalent order predicate. Runs in O(kn log n) time, where k is the number of sets and n is the number of elements involved; O(kn) time is optimal.

=== Element queries ===

{{{#!scheme
(iset-member? set x)
}}}

Returns non-{{{#false}}} iff {{{x}}} is an element of {{{set}}}, or {{{#false}}} otherwise. Takes O(log n) time.

{{{#!scheme
(iset-min set)
(iset-max set)
}}}

Returns the least/greatest element of {{{set}}}. It is an error for {{{set}}} to be empty. Takes O(log n) time; O(1) is optimal.

=== Element operations ===

{{{#!scheme
(iset-update set x present-proc absent-proc)
}}}

A continuation-based universal element update procedure. Attemps to find an element {{{y}}} equal to {{{x}}} in {{{set}}}. When such a {{{y}}} is found, calls
{{{#!scheme
(present-proc y update remove)
}}}
which must either tail-call
{{{#!scheme
(update new-y ret)
}}}
to replace {{{y}}} with {{{new-y}}}, or tail-call
{{{#!scheme
(remove ret)
}}}
to remove {{{y}}} from {{{set}}}. In either case {{{ret}}} will be returned from the enclosing {{{iset-update}}} call.

When no such {{{y}}} is found, {{{iset-update}}} calls
{{{#!scheme
(absent-proc insert ignore)
}}}
which should either tail-call
{{{#!scheme
(insert ret)
}}}
to insert {{{x}}} into {{{set}}}, or else tail-call
{{{#!scheme
(ignore ret)
}}}
to leave {{{set}}} unchanged. Again, {{{ret}}} will be returned from the enclosing {{{iset-update}}} call.

In any case, {{{iset-update}}} returns
{{{#!scheme
(values new-set ret)
}}}
where {{{new-set}}} is a new set reflecting the indicated modification, if any; and {{{ret}}} is the return value produced by one of the continuations. It runs in O(log n) time.

(This procedure is based on an analogous procedure for hash tables suggested by Alexey Radul and attributed to Taylor Campbell.)

{{{#!scheme
(iset-find iset x [absent-thunk])
}}}
Returns the element {{{y}}} equal to {{{x}}} in {{{set}}}, or the result of evaluating {{{(absent-thunk)}}} if no such element exists. If {{{absent-thunk}}} is unspecified then a default procedure that always returns {{{#false}}} is used. Takes O(log n) time.

{{{#!scheme
(iset-include set x)
(iset-exclude set x)
}}}
Return a new set that certainly does/doesn't include {{{x}}}. Each operation takes O(log n) time.

{{{#!scheme
(iset-predecessor set x [absent-thunk])
(iset-successor set x [absent-thunk])
}}}
Returns the element that immediately precedes/succeeds {{{x}}} in {{{set}}}'s ordering. If no such element exists because {{{x}}} is the minimum/maximum element, or because {{{set}}} is empty, returns the result of evaluating {{{(absent-thunk)}}}. If {{{absent-thunk}}} is unspecified then a default procedure that always returns {{{#false}}} is used. Takes O(log n) time.

=== Range queries ===

{{{#!scheme
(iset-between set least include-least most include-most)
}}}

Returns a new set containing the elements of {{{set}}} in the interval between {{{least}}} and {{{most}}}. If {{{include-least}}}/{{{include-most}}} is non-{{{#false}}} then the result includes elements equal to {{{least}}}/{{{most}}} respectively; otherwise those elements are not included. Takes O(k log k + log n) time, where n is the number of elements in the set and k is the number of elements returned; O(k + log n) is optimal.

{{{#!scheme
(iset-range< set x)
(iset-range<= set x)
(iset-range= set x)
(iset-range>= set x)
(iset-range> set x)
}}}

Returns a new set containing only the elements of {{{set}}} that are less/less-or-equal/equal/greater-or-equal/greater than {{{x}}}. Takes O(k log k + log n) time, where n is the number of elements in the set and k is the number of elements returned; O(k + log n) is optimal.

Note that since set elements are unique, {{{iset-range=}}} returns a set of at most one element.

=== Filter, fold, map ===

{{{#!scheme
(iset-filter predicate? set)
}}}

Returns a new set containing only those elements {{{x}}} for which {{{(predicate? x)}}} returns non-{{{#false}}}. Takes O(n log n) time; O(n) is optimal.

{{{#!scheme
(iset-fold proc base set)
}}}
The fundamental set iterator. Equivalent to, but may be more efficient than,
{{{#!scheme
(fold proc base (iset->ordered-list set))
}}}
Takes O(n) time.

{{{#!scheme
(iset-map/monotone proc set)
}}}
Returns a new set containing the elements {{{(proc x)}}} for every {{{x}}} in {{{set}}}. {{{proc}}} must be a ''monotone'' unary procedure that preserves the order and uniqueness of set elements. Takes O(n) time.

{{{#!scheme
(iset-map proc set)
}}}
Returns a new set containing the elements {{{(proc x)}}} for every {{{x}}} in {{{set}}}. {{{proc}}} must be a unary procedure, but is not required to be monotone, and so the result of the map operation may be out of order and may contain duplicates. When a subset of elements in {{{set}}} all map to the same result value, only the least of those elements is a member, in mapped form, of the resulting set. This operation is equivalent to, but may be more efficient than,
{{{#!scheme
(list->iset (set-order-predicate set) (map proc (set->ordered-list set)))
}}}
It takes O(n log n) time.

=== Conversion ===

{{{#!scheme
(iset->ordered-list set)
}}}

Returns a list containing the elements of {{{set}}} in increasing order. Takes O(n) time.

{{{#!scheme
(ordered-list->iset precedes? list)
}}}

Returns a set containing the elements of {{{list}}} and using order predicate {{{precedes?}}}. It is an error for {{{list}}} to be anything other than a proper list of elements in increasing order. Takes O(n log n) time; O(n) is optimal.

{{{#!scheme
(list->iset precedes? list)
}}}

Returns a set containing the elements of {{{list}}} and using order predicate {{{precedes?}}}. {{{list}}} must be a proper list, but may contain duplicates and need not be in order. When a subset of input elements are equal according to {{{precedes?}}}, only the first such element in {{{list}}} is a member of the returned set. Takes O(n log n) time.

=== Element comparison ===

{{{#!scheme
(iset-element<? set x y)
(iset-element=? set x y)
(iset-element>? set x y)
}}}

These procedures compare {{{x}}} to {{{y}}} according to {{{set}}}'s order predicate and the conventional meaning of {{{<}}}, {{{=}}}, and {{{>}}}.

= Maps =

(TODO)

= Open questions =

Should there be an explicitly-immutable pair and list?

time

2013-06-04 13:49:47

version

2