12.21 data.sparse - Skew binary random-access lists

Module: data.skew-list

このモジュールは、Skew binary random-access list (以降は短くskew-listと表記します)を提供します。 skew-listは変更不可なデータ構造で、リストとベクタの中間のような 性質を持っています:要素数をnとするとき 最初の要素を取り出したり(car)、最初に要素を追加する(cons)のはO(1)、 最初以外の要素を返す(cdr)のはO(log n)、 そして整数インデックスにより任意の要素にアクセスするのもO(log n)です。

skew-listは常に「properなリスト」です。すなわち、それは 空のskew-list (skew-list-null)か、 skew-listの前に要素を付け足したもの、です。

Class: <skew-list>

{data.skew-list} skew-listのクラスです。

<sequence>を継承していて、シーケンスプロトコルを実装しています (シーケンスフレームワーク参照)。

Function: skew-list? obj

{data.skew-list} objがskew-listなら#tを、そうでなければ#fを返します。

Function: skew-list-empty? sl

{data.skew-list} 引数はskew listでなければなりません。 slが空のskew listなら#tを、そうでなければ#fを返します。

Variable: skew-list-null

{data.skew-list} 空のskew listに束縛されています。

Function: skew-list-cons obj sl

{data.skew-list} skew list slの先頭にobjを追加した新たなskew listを作って返します。 O(1)の操作です。

Function: skew-list-car sl

{data.skew-list} skew list slの先頭要素を返します。O(1)の操作です。 slが空であればエラーが投げられます。

Function: skew-list-cdr sl

{data.skew-list} skew list slの、最初の要素を取り除いたskew listを返します。 O(log n)の操作です。 slが空であればエラーが投げられます。

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

{data.skew-list} skew list slのk番目の要素を返します。O(log n)の操作です。 kがslの範囲外を指している場合、fallbackが与えられていればそれが 返され、与えられていなければエラーが投げられます。

skew listはシーケンスでもあるので、refでアクセスすることもできます (シーケンスフレームワーク参照)。

Function: skew-list-set sl k obj

{data.skew-list} skew list slの、k番目の要素をobjに変えた新たなskew listを 作って返します。元のslは変更されません。 O(log n)の操作です。

kがslの範囲外を指していた場合はエラーが投げられます。

Function: skew-list-length sl

{data.skew-list} skew list slの長さを返します。O(log n)の操作です。

skew listはシーケンスでもあるので、size-ofも使えます (シーケンスフレームワーク参照)。

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

{data.skew-list} skew list slの長さがn以下であれば#tを、そうでなければ #fを返します。slの全長を求めてnと比較するより効率的です。

Function: list->skew-list lis

{data.skew-list} リストlisと同じ要素を同じ並びで持つskew listを作って返します。 lisが正式なリストでなければエラーが投げられます。

skew listはシーケンスでもあるので、coerce-toを使うこともできます (シーケンスフレームワーク参照)。

Function: list*->skew-list lis

{data.skew-list} lisは正式なリストまたはドットリストです (循環リストであってはいけません)。 二つの値を返します。lisの最後のcdrを除いた要素をその並びで持つ新たな skew listと、lisの最後のcdrの値です。

Function: skew-list->list sl

{data.skew-list} skew list slの各要素を同じ並びで持つリストを作って返します。

skew listはシーケンスでもあるので、coerce-toを使うこともできます (シーケンスフレームワーク参照)。

Function: skew-list->generator sl

{data.skew-list} skew list slの要素を順に生成するジェネレータを作って返します。

Function: skew-list->lseq sl

{data.skew-list} skew list slを遅延シーケンスに変換します。

Function: skew-list-take sl k

Function: skew-list-drop sl k

{data.skew-list} skew list slの、最初のk要素だけのskew list、 あるいは最初のk要素を取り除いた残りのskew listを返します。

Function: skew-list-split-at sl k

{data.skew-list} (skew-list-take sl k)と(skew-list-drop sl k)の結果を 2つの値として返しますが、より効率が良いです。

Function: skew-list-append sl sl2 …

{data.skew-list} 2つのskew listをつなげたskew listを返します。

Function: skew-list-fold sl kons knil

{data.skew-list} skew list slに対して、リストに対するfoldと同じような動作をします。

skew listはシーケンスでもあるので、ジェネリックなfoldを使うこともできます (シーケンスフレームワーク参照)。

Function: skew-list-map sl proc

{data.skew-list} skew list slの各要素にprocを適用した結果を集めた新たなskew listを 作って返します。procが適用される順序は決められていません。

複数のskew listに対してmapしたい場合は、 ジェネリックのmapが使えます (シーケンスフレームワーク)。 skew-list-mapは単一引数の場合に使える最適化を施してあります。