Next: Sparse data containers, Previous: Ring buffer, Up: Library modules - Utilities [Contents][Index]

`data.skew-list`

- Skew binary random-access lists- Module:
**data.skew-list** -
This module implements skew binary random-access list (we call it skew-list for short). It’s an immutable data structure that has properties of both list and vector; constant time to take the first element (car) and append an element in front of existing one (cons), O(log n) to take the rest of the elements (cdr), and O(log n) for indexed access, wher n is the number of elements.

A skew-list is always ’proper’; that is, it is either an empty skew-list (

`skew-list-null`

), or an object appended in front of a skew-list.

- Class:
**<skew-list>** -
{

`data.skew-list`} The class for skew-lists.It inherits

`<sequence>`

and implements the sequence protocol (see Sequence framework).

- Function:
**skew-list?***obj* {

`data.skew-list`} Returns`#t`

iff`obj`is a skew-list.

- Function:
**skew-list-empty?***sl* {

`data.skew-list`} The argument must be a skew list. Returns`#t`

iff`sl`is an empty skew list.

- Variable:
**skew-list-null** {

`data.skew-list`} An empty skew list.

- Function:
**skew-list-cons***obj sl* {

`data.skew-list`} Returns a new skew-list which has`obj`prepended to a skew-list`sl`. O(1) operation.

- Function:
**skew-list-car***sl* {

`data.skew-list`} Returns the first element of a skew-list`sl`. O(1) operation. An error is raised when`sl`is empty.

- Function:
**skew-list-cdr***sl* {

`data.skew-list`} Returns a new skew-list that containts elements in`sl`but the first one. O(log n) operation. An error is raised when`sl`is empty.

- Function:
**skew-list-ref***sl k :optional fallback* {

`data.skew-list`} Returns the`k`-th element of a skew-list`sl`. O(log n) operation. If`k`points past the range of`sl`,`fallback`is returned if it is given, or an error is signaled.Sicne a skew-list is also a sequence, you can use generic

`ref`

as well (see Sequence framework).

- Function:
**skew-list-set***sl k obj* {

`data.skew-list`} Returns a new skew-list which is the same as`sl`except the`k`-th element is replaced with`obj`. The argument`sl`remains intact. O(log n) operation.It is an error if

`k`points beyond the last element of`sl`.

- Function:
**skew-list-length***sl* {

`data.skew-list`} Returns an integer length of a skew-list`sl`. O(log n) operation.Sicne a skew-list is also a sequence, you can use generic

`size-of`

as well (see Sequence framework).

- Function:
**skew-list-length<=?***sl n* {

`data.skew-list`} Returns`#t`

iff the length of a skew-list`sl`is less than or equal to`n`. It is more efficient than calculating the total length and compares with`n`.

- Function:
**list->skew-list***lis* {

`data.skew-list`} Returns a new skew-list which contains elements in`lis`, with the same order. It is an error if`lis`is not a proper list.Sicne a skew-list is also a sequence, you can use generic

`coerce-to`

as well (see Sequence framework).

- Function:
**list*->skew-list***lis* {

`data.skew-list`} The argument`lis`may be a dotted list (but can’t be circular). Returns two values: a new skew-list which contains elements in`lis`except the last cdr of it, and the last cdr of`lis`.

- Function:
**skew-list->list***sl* {

`data.skew-list`} Returns a new list that contains all the elements in a skew-list`sl`, with the same order.Sicne a skew-list is also a sequence, you can use generic

`coerce-to`

as well (see Sequence framework.

- Function:
**skew-list->generator***sl* {

`data.skew-list`} Returns a new generator that traverses a skew-list`sl`.

- Function:
**skew-list->lseq***sl* {

`data.skew-list`} Converts a skew-list`sl`to a lazy sequence.

- Function:
**skew-list-take***sl k* - Function:
**skew-list-drop***sl k* {

`data.skew-list`} Returns a new skew-list of the first`k`elements and the elements except the first`k`elements, respectively.

- Function:
**skew-list-split-at***sl k* {

`data.skew-list`} Returns two values, the result of`(skew-list-take sl k)`

and`(skew-list-drop sl k)`

, but more efficiently.

- Function:
**skew-list-append***sl sl2 …* {

`data.skew-list`} Returns a skew-list which is a concatenation of all the given skew-lists.

- Function:
**skew-list-fold***sl kons knil* {

`data.skew-list`} Like`fold`on a list.Sicne a skew-list is also a sequence, you can use generic

`fold`

as well (see Sequence framework.

- Function:
**skew-list-map***sl proc* {

`data.skew-list`} Returns a skew list, each element of which is the result of applying`proc`on the element of`sl`. The order of application of`proc`is not specified.NB: If you want ot map over multiple skew-lists, you can use generic

`map`

(see Sequence framework). The`skew-list-map`

employs optimization that’s specific to one-argument case.

DRAFT