5.6.3 Functions that Rearrange Lists

以下では、リストの構成要素であるコンスセルのCDRを変更することにより、リストを“破壊的”に再配置する関数をいくつか示します。これらの関数が“破壊的”だという理由は、これらの関数が引数として渡された元のリストを処理して、return値となる新しいリストを形成するために、リストのコンスセルを再リンクするからです。

コンスセルを変更する他の関数については、Sets And Listsのdelqを参照してください。

Function: nconc &rest lists

この関数は、listsの要素すべてを含むリストをreturnします。append (Building Listsを参照してください)とは異なり、listsはコピーされません。かわりにlistsの各リストの最後のCDRが、次のリストを参照するように変更されます。listsの最後のリストは、変更されません。たとえば:

(setq x '(1 2 3))
     ⇒ (1 2 3)

(nconc x '(4 5))
     ⇒ (1 2 3 4 5)

x
     ⇒ (1 2 3 4 5)

nconcの最後の引数は変更されないので、上記の例のように、'(4 5)のような定数リストを使用するのが理に適っています。また、同じ理由により、最後の引数がリスとである必要はありません。

(setq x '(1 2 3))
     ⇒ (1 2 3)

(nconc x 'z)
     ⇒ (1 2 3 . z)

x
     ⇒ (1 2 3 . z)

しかし、(最後を除くすべての)他の引数はリストでなければなりません。

一般的な落とし穴としては、nconcにたいしてクォートされたリスト定数を、最後以外の引数として使用したときです。これを行なう場合、実行するごとにプログラムはリスト定数を変更するでしょう! 何が起こるのかを以下に示します:

(defun add-foo (x)            ; この関数ではfoo
  (nconc '(foo) x))           ;   を引数の前に追加させたい。

(symbol-function 'add-foo)
     ⇒ (lambda (x) (nconc (quote (foo)) x))

(setq xx (add-foo '(1 2)))    ; 動いているように見える。
     ⇒ (foo 1 2)

(setq xy (add-foo '(3 4)))    ; 何が起きているのか?
     ⇒ (foo 1 2 3 4)

(eq xx xy)
     ⇒ t

(symbol-function 'add-foo)
     ⇒ (lambda (x) (nconc (quote (foo 1 2 3 4) x)))

Function: nreverse list

この関数は、listの要素の順番を逆転します。reverseとは異なり、nreverseはリストを形成するCDR内のコンスセルを逆転することにより、引数を変更します。listの最後に使用されているコンスセルは、最初のコンスセルになります。

たとえば:

(setq x '(a b c))
     ⇒ (a b c)

x
     ⇒ (a b c)
(nreverse x)
     ⇒ (c b a)

;; 最初のコンスセルが最後になった。
x
     ⇒ (a)

わたしたちは通常、混乱を避けるために、nreverseの結果を、元のリストを保持していたのと同じ変数に格納します:

(setq x (nreverse x))

以下は、(a b c)を視覚的に表した、nreverseの例です:

元のリストの先頭:                         逆転されたリスト:
 -------------        -------------        ------------
| car  | cdr  |      | car  | cdr  |      | car | cdr  |
|   a  |  nil |<--   |   b  |   o  |<--   |   c |   o  |
|      |      |   |  |      |   |  |   |  |     |   |  |
 -------------    |   --------- | -    |   -------- | -
                  |             |      |            |
                   -------------        ------------

Function: sort list predicate

この関数は、listを安定的(しかし破壊的)にソートして、ソートされたリストをreturnします。この関数はpredicateを使用して要素を比較します。安定ソート(stable sort)では、同じソートキーをもつ要素が、ソートの前後で相対的に同じ順序が維持されます。安定性は、異なる条件によりソートするために要素を並び替えるために、連続したソートが使用されるときに重要です。

引数predicateは、2つの引数をとる関数でなければなりません。この関数はlistの2つの要素を引数として呼び出されます。昇順のソートを得るためのpredicateは、1番目の引数が、2番目の引数より“小さい”ときは非nil、それ以外はnilをreturnするようにします。

比較関数predicateは、少なくとも単独のsort呼び出しにおいて、任意の与えられた引数にたいして信頼できる結果を与えなければありません。比較関数は非対称的(antisymmetric) — つまりaがbより小さいとき、bはaより小さくない — でなければなりません。比較関数は推移的(transitive) — つまりaがbより小さく、bがcより小さい場合、cはaより小さい — でなければなりません。これらの要求を満たさない比較関数を使用した場合、sortの結果は予測できません。

sortの破壊的な側面は、CDRを変更することにより、listを形成するコンスセルを再配置することです。非破壊的なソート関数の場合は、ソートされた要素を格納するために、あたらしいコンスセルを作成します。元のリストを破壊せずにソートされたコピーを作成したい場合は、copy-sequenceで最初にコピーしてから、それをソートします。

ソートはlist内のコンスセルのCARは変更しません。list内でCARに要素aを保持していたコンスセル、ソート後にもaを保持しますが、CDRは変更されるので、ソート後の位置は異なります。たとえば:

(setq nums '(1 3 2 6 5 4 0))
     ⇒ (1 3 2 6 5 4 0)

(sort nums '<)
     ⇒ (0 1 2 3 4 5 6)

nums
     ⇒ (1 2 3 4 5 6)

警告: numsのリストには0が含まれていないことに注意してください。これは前と同じコンスセルですが、リストの1番目ではなくなります。引数を保持するように形成された変数が、ソートされたリストでも保持されると仮定しないでください! かわりにsortの結果を保存して、それを使用してください。元のリストを保持していた変数に、結果を書き戻すことはよく行なわれます。

(setq nums (sort nums '<))

ソート処理を行なう他の関数については、Sortingを参照してください。sortの有用な例は、Accessing Documentationのdocumentationを参照してください。