12.16 data.sparse - 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 follws the sequence protocol.

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.

Function: skew-list-car sl

{data.skew-list} Returns the first element of a skew-list sl. 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 firest one. 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. 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 シーケンスフレームワーク.

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.

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.

Sicne a skew-list is also a sequence, you can use generic size-of as well (see シーケンスフレームワーク.

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 シーケンスフレームワーク.

Function: list*->skew-list lis

{data.skew-list} The argument lis may be an improper 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 シーケンスフレームワーク.

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 シーケンスフレームワーク.

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.

NB: If you want ot map over multiple skew-lists, you can use generic map (see シーケンスフレームワーク). The skew-list-map employs optimization that’s specific to one-argument case.