Previous: Setcdr, Up: Modifying Lists


5.6.3 リストの順序を変更する関数

以下は、リストを構成するコンスセルのcdrを変更することで、 『破壊的に』リストの順序を変更する関数です。 これらの関数を『破壊的』と呼ぶのは、 渡された引数であるもとのリストのコンスセルを繋ぎ換えて新たなリストに 変えるからです。

— Function: nconc &rest lists

この関数は、listsのすべての要素を入れたリストを返す。 append(see 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)            ; この関数は引数の先頭に
            (nconc '(foo) x))           ;   fooを追加する、としたい
          
          (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 '(1 2 3 4))
                (1 2 3 4)
          x
                (1 2 3 4)
          (nreverse x)
                (4 3 2 1)
          
          ;; 先頭にあったコンスセルは、今、最後になっている
          x
                (1)

混乱を避けるために、nreverseの結果は、 もとのリストを収めていたものと同じ変数に格納する。

          (setq x (nreverse x))

nreverse(a b c)に適用した結果を図示すると つぎのようになる。

          
          もとのリストの先頭                        逆順にしたリスト
           -------------        -------------        ------------
          | car  | cdr  |      | car  | cdr  |      | car | cdr  |
          |   a  |  nil |<--   |   b  |   o  |<--   |   c |   o  |
          |      |      |   |  |      |   |  |   |  |     |   |  |
           -------------    |   --------- | -    |   -------- | -
                            |             |      |            |
                             -------------        ------------
— Function: sort list predicate

この関数は、破壊的にではあるが、 listを順序を保ってソートしたリストを返す。 要素の比較にはpredicateを使う。 順序を保ったソートとは、同じソートキーを持つ要素の相対順序を、 ソート実行前後で変更しないソートである。 異なる基準でつぎつぎにソートするときには、 順序を保つことは重要である。

引数predicateは、2つの引数を取る関数である必要がある。 この関数は、listの2つの要素で呼び出される。 昇順のソートでは、predicateは、 第1引数が第2引数より『小さい』ときにtを返し、 さもなければnilを返す必要がある。

比較関数predicateは、少なくとも単一のsortの呼び出し中は、 引数の任意の対に対して信頼できる結果を返す必要がある。 まず、反対称であること。 つまり、abより小さいときには、 baより小さくてはいけない。 また、遷移則が成り立つこと。 つまり、abより小さく、かつ、bcより小さいときには、 acより小さくなければならない。 これらの要請を満たさない比較関数を用いると、 sortの結果は予測できない。

sortが破壊的であるというのは、 listを構成するコンスセルのcdrを変更して、 コンスセルの順序を変更するからである。 非破壊的なソート関数では、ソートした要素を格納するために新たなコンスセルを 作成するであろう。 もとのリストを破壊せずにソートしたければ、 まずcopy-sequenceでコピーを作り、それをソートする。

ソートする際、listのコンスセルのcarは変更しない。 list内の要素aを入れていたコンスセルは、 ソート後にもそのcarには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が入っていないことに注意。 (numsが指す)コンスセルはソート前と同じコンスセルだが、 それはもはやリストの先頭にはない。 引数を保持していた変数が、 ソートしたリスト全体を保持していると仮定しないこと! かわりに、sortの結果を保存して、それを使う。 多くの場合、つぎのように、もとのリストを保持していた変数に結果を保存し直す。

          (setq nums (sort nums '<))

ソートを行う他の関数については、see Sortingsortの有用な例については、 Accessing Documentationdocumentationを参照。