[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5. リスト

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=Lists"
"texi/elisp21/リスト"へのコメント(無し)
検索全文Elisp

リスト(list)は、0個以上の(任意のLispオブジェクトの)要素の列を 表現します。 リストとベクトルの重要な相違点は、 複数のリストがそれらの構造の一部を共有できることです。 さらに、リスト全体をコピーすることなく、 リストに要素を追加したり削除できることです。



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5.1 リストとコンスセル

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=Cons%20Cells"
"texi/elisp21/リストとコンスセル"へのコメント(無し)
検索全文Elisp

Lispのリストは基本データ型ではありません。 リストはコンスセル(cons cells)で構成されます。 コンスセルはドット対を表現するデータオブジェクトです。 ドット対は2つのLispオブジェクトを保持、つまり、『指し』ます。 その2つのLispオブジェクトの一方をCAR、他方をCDRといいます。 これらの名前は歴史的なものです。 See 節 2.3.6 コンスセルとリスト型。 CDRは『クダー』と読みます。

リストはコンスセルを連ねたものであり、 リストの各要素ごとにコンスセルが1つあります。 慣習として、コンスセルのCARはリストの要素であり、 CDRはリストを繋ぐために使います。 つまり、各コンスセルのCDRは後続のコンスセルです。 最後のコンスセルのCDRはnilです。 CARとCDRの非対称性は単なる慣習によるものです。 コンスセルのレベルでは、CARとCDRには同じ性質があります。

ほとんどのコンスセルはリストの一部として使われるので、 リスト構造(list structure)という用語は、 コンスセルで構成した任意の構造を意味するようになりました。

シンボルnilは、シンボルであるとともにリストでもあるとみなします。 これは要素を持たないリストです。 慣習として、シンボルnilのCDR(およびCAR)は nilであるとみなします。

空でない任意のリストlのCDRは、 lの先頭要素を除くすべての要素を含んだリストです。



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5.2 箱の対を連ねたリスト

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=Lists%20as%20Boxes"
"texi/elisp21/箱の対を連ねたリスト"へのコメント(無し)
検索全文Elisp

コンスセルは1対の箱で図示できます。 最初の箱はCARを表し、2番目の箱はCDRを表します。 つぎは、2つのコンスセルから成る 2要素のリスト(tulip lily)を図示したものです。

 
 ---------------         ---------------
| car   | cdr   |       | car   | cdr   |
| tulip |   o---------->| lily  |  nil  |
|       |       |       |       |       |
 ---------------         ---------------

各1対の箱がコンスセルを表します。 各箱は、Lispオブジェクトを『参照する』、『指す』、『含む』のです。 (これらの用語は同義語。) 最初のコンスセルのCARを表す最初の箱は、 シンボルtulipを含みます。 最初のコンスセルのCDR箱から2番目のコンスセルへ向かう矢印は、 最初のコンスセルのCDRが2番目のコンスセルであることを表します。

同じリストは、つぎのような別の箱記法でも図示できます。

 
    --- ---      --- ---
   |   |   |--> |   |   |--> nil
    --- ---      --- ---
     |            |
     |            |
      --> tulip    --> lily

つぎは、より複雑で、最初の要素が2要素リストであるような 3要素リストを図示したものです。

 
    --- ---      --- ---      --- ---
   |   |   |--> |   |   |--> |   |   |--> nil
    --- ---      --- ---      --- ---
     |            |            |
     |            |            |
     |             --> oak      --> maple
     |
     |     --- ---      --- ---
      --> |   |   |--> |   |   |--> nil
           --- ---      --- ---
            |            |
            |            |
             --> pine     --> needles

同じリストを最初の箱記法で表現するとつぎのようになります。

 
 --------------       --------------       --------------
| car   | cdr  |     | car   | cdr  |     | car   | cdr  |
|   o   |   o------->| oak   |   o------->| maple |  nil |
|   |   |      |     |       |      |     |       |      |
 -- | ---------       --------------       --------------
    |
    |
    |        --------------       ----------------
    |       | car   | cdr  |     | car     | cdr  |
     ------>| pine  |   o------->| needles |  nil |
            |       |      |     |         |      |
             --------------       ----------------

コンスセルとリストの入力構文と表示表現、および、 『箱と矢印』によるリストの図示については、See 節 2.3.6 コンスセルとリスト型



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5.3 リスト向け述語

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=List-related%20Predicates"
"texi/elisp21/リスト向け述語"へのコメント(無し)
検索全文Elisp

以下の述語は、Lispオブジェクトが、アトムであるか、 コンスセル、つまり、リストであるか、 特別なオブジェクトnilであるか調べます。 (これらの多く述語は、それぞれ残りの述語で定義可能である。 しかし、多用するため、これらすべてを用意しておく価値がある。)

Function: consp object
この関数は、objectがコンスセルならばtを返し、 さもなければnilを返す。 nilはコンスセルではないが、空リストである

Function: atom object
この関数は、objectがアトムならばtを返し、 さもなければnilを返す。 コンスセルを除くすべてのオブジェクトはアトムである。 シンボルnilはアトムでもありリストでもある。 このようなLispオブジェクトはnilだけである。

 
(atom object) == (not (consp object))

Function: listp object
この関数は、objectがコンスセルかnilならばtを返す。 さもなければnilを返す。

 
(listp '(1))
     => t
(listp '())
     => t

Function: nlistp object
この関数は、listpの反対である。 objectがリストでなければtを返す。 さもなければnilを返す。

 
(listp object) == (not (nlistp object))

Function: null object
この関数は、objectnilならばtを返し、 さもなければnilを返す。 この関数は、notと同一であるが、意図を明確にするために、 objectをリストと考えるときにはnullを使い、 objectを真理値と考えるときにはnotを使う (9.3 条件の組み合わせnotを参照)

 
(null '(1))
     => nil
(null '())
     => t



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5.4 リストの要素の参照

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=List%20Elements"
"texi/elisp21/リストの要素の参照"へのコメント(無し)
検索全文Elisp

Function: car cons-cell
この関数は、コンスセルcons-cellの最初のポインタが指す値を返す。 別のいい方をすれば、cons-cellのCARを返す。

特別な場合として、cons-cellnilのときには、 carnilを返すと定義する。 したがって、任意のリストはcarの正しい引数である。 引数がコンスセルでもnilでもなければエラーを通知する。

 
(car '(a b c))
     => a
(car '())
     => nil

Function: cdr cons-cell
この関数は、コンスセルcons-cellの2番目のポインタが指す値を返す。 別のいい方をすれば、cons-cellのCDRを返す。

特別な場合として、cons-cellnilのときには、 cdrnilを返すと定義する。 したがって、任意のリストはcdrの正しい引数である。 引数がコンスセルでもnilでもなければエラーを通知する。

 
(cdr '(a b c))
     => (b c)
(cdr '())
     => nil

Function: car-safe object
この関数は、コンスセルのCARを取り出すが、 他のデータ型に対するエラーを回避する。 objectがコンスセルならばobjectのCARを返すが、 さもなければnilを返す。 これはcarと対照的であり、 carobjectがリストでないとエラーを通知する。

 
(car-safe object)
==
(let ((x object))
  (if (consp x)
      (car x)
    nil))

Function: cdr-safe object
この関数は、コンスセルのCDRを取り出すが、 他のデータ型に対するエラーを回避する。 objectがコンスセルならばobjectのCDRを返すが、 さもなければnilを返す。 これはcdrと対照的であり、 cdrobjectがリストでないとエラーを通知する。

 
(cdr-safe object)
==
(let ((x object))
  (if (consp x)
      (cdr x)
    nil))

Function: nth n list
この関数は、listn番目の要素を返す。 要素は0から数えるので、listのCARは要素番号0。 listの長さがnかそれ未満であると、値はnilになる。

nが負であると、nthlistの最初の要素を返す。

 
(nth 2 '(1 2 3 4))
     => 3
(nth 10 '(1 2 3 4))
     => nil
(nth -3 '(1 2 3 4))
     => 1

(nth n x) == (car (nthcdr n x))

関数eltも同様であるが、任意のシーケンスに適用できる。 歴史的な理由で引数の順序は逆である。 see 節 6.1 シーケンス

Function: nthcdr n list
この関数は、listn番目のCDRを返す。 いいかえれば、listの始めのn個のリンクを飛び越えて、 そのあとにあるものを返す。

nが0か負であると、nthcdrlist全体を返す。 listの長さがnかそれ未満であると、 nthcdrnilを返す。

 
(nthcdr 1 '(1 2 3 4))
     => (2 3 4)
(nthcdr 10 '(1 2 3 4))
     => nil
(nthcdr -3 '(1 2 3 4))
     => (1 2 3 4)

Function: safe-length list
この関数は、エラーや無限ループを回避して、listの長さを返す。

listが実際にはリストでない場合には、safe-lengthは0を返す。 listに循環があると、少なくとも異なる要素の個数を表す有限値を返す。

循環はないと思われるリストの長さを計算するもっとも一般的な方法は、 lengthです。 See 節 6.1 シーケンス

Function: caar cons-cell
これは(car (car cons-cell))と同じ。

Function: cadr cons-cell
これは(car (cdr cons-cell))(nth 1 cons-cell)と同じ。

Function: cdar cons-cell
これは(cdr (car cons-cell))と同じ。

Function: cddr cons-cell
これは(cdr (cdr cons-cell))(nthcdr 2 cons-cell)と同じ。



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5.5 コンスセルとリストの構築

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=Building%20Lists"
"texi/elisp21/コンスセルとリストの構築"へのコメント(無し)
検索全文Elisp

リストはLispの中核なので、多くの関数はリストを構築します。 consは基本的なリスト構築関数です。 しかし、Emacsのソースコードでは、consよりlistを 多用していることは興味深いことです。

Function: cons object1 object2
この関数は、新たなリスト構造を構築するために使う基本関数。 object1をCAR、object2をCDRとする 新たなコンスセルを作成し、このコンスセルを返す。 引数object1object2はどんなLispオブジェクトでもよいが、 ほとんどの場合、object2はリストである。

 
(cons 1 '(2))
     => (1 2)
(cons 1 '())
     => (1)
(cons 1 2)
     => (1 . 2)

consは、リストの先頭に要素を1つ追加するために しばしば使われる。 これを要素をリストにコンスするという。 たとえば、つぎのとおり。

 
(setq list (cons newelt list))

この例におけるlistという名前の変数と 以下に述べるlistという名前の関数とは衝突しない。 任意のシンボルはどちらの目的にも使える。

Function: list &rest objects
この関数は、objectsを要素とするリストを作成する。 結果のリストはつねにnil終端になる。 objectsを指定しないと空リストを返す。

 
(list 1 2 3 4 5)
     => (1 2 3 4 5)
(list 1 2 '(3 4 5) 'foo)
     => (1 2 (3 4 5) foo)
(list)
     => nil

Function: make-list length object
この関数は、すべての要素が同一の値objectであり 長さがlengthのリストを作成する。 make-stringと比較してほしい(see 節 4.3 文字列の作成)。

 
(make-list 3 'pigs)
     => (pigs pigs pigs)
(make-list 0 'pigs)
     => nil

Function: append &rest sequences
この関数はsequencesのすべての要素から成るリストを返す。 sequencesは、リスト、ベクトル、ブールベクトル、文字列のいずれかであるが、 普通、最後の要素はリストである。 最後の引数を除いてすべての引数をコピーするので、どの引数も変更しない (コピーせずにリストを繋ぐ方法については、 5.6.3 リストの順序を変更する関数nconcを参照。)

一般には、appendの最後の引数はどんなLispオブジェクトでもよい。 最後の引数をコピーしたり変換したりしない。 それは、新たなリストの最後のコンスセルのCDRになる。 最後の引数がそれ自体リストであれば、それらの要素は、実質的には、 結果のリストの要素になる。 最後の要素がリストでなければ、結果は『ドット対』になる。 なぜなら、結果の最後のCDRは、 真のリストに必要とされるnilではないからである。

関数appendは、引数として整数も受け付ける。 整数を10進の表示表現の文字列に変換してから、 その文字列を整数のかわりに使う。 この機能を使わないでほしい。 削除する予定である。 読者がこの機能を使っていたら、今すぐプログラムを直すこと! 整数をこのような10進数に変換する正しい方法は、 format(see 節 4.7 文字列の書式付け)や number-to-string(see 節 4.6 文字と文字列の変換)を使うことである。

appendの使用例をつぎに示します。

 
(setq trees '(pine oak))
     => (pine oak)
(setq more-trees (append '(maple birch) trees))
     => (maple birch pine oak)

trees
     => (pine oak)
more-trees
     => (maple birch pine oak)
(eq trees (cdr (cdr more-trees)))
     => t

箱表示を見ればappendの動作を理解できるでしょう。 変数treesにリスト(pine oak)を設定し、ついで、 変数more-treesにはリスト(maple birch pine oak)を設定します。 しかし、変数treesはもとのリストを指し続けます。

 
more-trees                trees
|                           |
|     --- ---      --- ---   -> --- ---      --- ---
 --> |   |   |--> |   |   |--> |   |   |--> |   |   |--> nil
      --- ---      --- ---      --- ---      --- ---
       |            |            |            |
       |            |            |            |
        --> maple    -->birch     --> pine     --> oak

空シーケンスはappendが返す値にはまったく寄与しません。 この結果、最後のnil引数は直前の引数をコピーするように強制します。

 
trees
     => (pine oak)
(setq wood (append trees nil))
     => (pine oak)
wood
     => (pine oak)
(eq wood trees)
     => nil

この方法は、関数copy-sequenceを導入するまでは、 リストをコピーする普通の方法でした。 See 節 6. シーケンス、配列、ベクトル

appendの引数にベクトルと文字列を使った例をつぎに示します。

 
(append [a b] "cd" nil)
     => (a b 99 100)

apply(see 節 11.5 関数呼び出し)の助けを借りれば、 リストのリストの中にあるすべてのリストを連結できます。

 
(apply 'append '((a b c) nil (x y z) nil))
     => (a b c x y z)

sequencesをまったく指定しないとnilを返します。

 
(append)
     => nil

最後の引数がリストではない例をいくつか示します。

 
(append '(x y) 'z)
     => (x y . z)
(append '(x y) [z])
     => (x y . [z])

最後の引数がリストではなくシーケンスである2番目の例は、 シーケンスの要素が結果のリストの要素にはならないことを示しています。 そのかわりに、最後の引数がリストでない場合と同様に、 シーケンスが最後のCDRになります。

Function: reverse list
この関数は、listの要素を逆順にした新たなリストを作成する。 もとの引数listは変更しない

 
(setq x '(1 2 3 4))
     => (1 2 3 4)
(reverse x)
     => (4 3 2 1)
x
     => (1 2 3 4)



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5.6 既存のリスト構造の修正

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=Modifying%20Lists"
"texi/elisp21/既存のリスト構造の修正"へのコメント(無し)
検索全文Elisp

基本関数setcarsetcdrを使って、 コンスセルのCARやCDRの内容を変更できます。 これらは、既存のリスト構造を変更するので、 『破壊的』な操作と呼びます。

Common Lispに関した注意: Common Lispでは、 リスト構造を変更するにはrplacarplacdを使う。 これらはsetcarsetcdrと同様に構造を変更する。 しかし、Common Lispの関数はコンスセルを返すが、 setcarsetcdrは新たなCARやCDRを返す。

5.6.1 setcarによるリスト要素の変更  Replacing an element in a list.
5.6.2 リストのCDRの変更  Replacing part of the list backbone. This can be used to remove or add elements.
5.6.3 リストの順序を変更する関数  Reordering the elements in a list; combining lists.



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5.6.1 setcarによるリスト要素の変更

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=Setcar"
"texi/elisp21/setcarによるリスト要素の変更"へのコメント(無し)
検索全文Elisp

コンスセルのCARを変更するには、setcarを使います。 リストに対して使用すると、 setcarはリストの1つの要素を別の要素に置き換えます。

Function: setcar cons object
この関数は、consの新たなCARとしてobjectを格納し、 以前のCARを置き換える。 いいかえれば、consのCARスロットがobjectを指すように変更する。 この関数は値objectを返す。 たとえば、つぎのようになる。

 
(setq x '(1 2))
     => (1 2)
(setcar x 4)
     => 4
x
     => (4 2)

コンスセルが複数のリストの共有構造の一部であるときには、 コンスセルに新たなCARを格納すると、 そのような各リストの1つの要素を変更することになります。

 
;; 共有部分がある2つのリストを作る
(setq x1 '(a b c))
     => (a b c)
(setq x2 (cons 'z (cdr x1)))
     => (z b c)

;; 共有部分のCARを置き換える
(setcar (cdr x1) 'foo)
     => foo
x1                           ; 両方のリストが変更されている
     => (a foo c)
x2
     => (z foo c)

;; 非共有部分のCARを置き換える
(setcar x1 'baz)
     => baz
x1                           ; 1つのリストだけが変更されている
     => (baz foo c)
x2
     => (z foo c)

変数x1x2に入っている共有部分を持つ2つのリストを図示すると つぎのようになります。 bを置き換えるとなぜ両者が変更されるのかわかるでしょう。

 
        --- ---        --- ---      --- ---
x1---> |   |   |----> |   |   |--> |   |   |--> nil
        --- ---        --- ---      --- ---
         |        -->   |            |
         |       |      |            |
          --> a  |       --> b        --> c
                 |
       --- ---   |
x2--> |   |   |--
       --- ---
        |
        |
         --> z

同じ関係を別の箱表示で示します。

 
x1:
 --------------       --------------       --------------
| car   | cdr  |     | car   | cdr  |     | car   | cdr  |
|   a   |   o------->|   b   |   o------->|   c   |  nil |
|       |      |  -->|       |      |     |       |      |
 --------------  |    --------------       --------------
                 |
x2:              |
 --------------  |
| car   | cdr  | |
|   z   |   o----
|       |      |
 --------------



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5.6.2 リストのCDRの変更

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=Setcdr"
"texi/elisp21/リストのCDRの変更"へのコメント(無し)
検索全文Elisp

CDRを修正するもっとも低レベルの基本関数はsetcdrです。

Function: setcdr cons object
この関数は、consの新たなCDRとしてobjectを格納し、 以前のCDRを置き換える。 いいかえれば、consのCDRスロットがobjectを指すように変更する。 この関数は値objectを返す。

リストのCDRを別のリストで置き換える例を示します。 リストの最初の要素以外は取り除かれ、 要素の別のシーケンスになります。 最初の要素は変更されません。 というのは、それはリストのCARの中にあり、 CDRからは辿れないからです。

 
(setq x '(1 2 3))
     => (1 2 3)
(setcdr x '(4))
     => (4)
x
     => (1 4)

リスト内のコンスセル群のCDRを変更することで、 リストの中ほどの要素を削除できます。 つぎの例は、リスト(a b c)の最初のコンスセルのCDRを変更することで、 このリストの第2要素bを削除します。

 
(setq x1 '(a b c))
     => (a b c)
(setcdr x1 (cdr (cdr x1)))
     => (c)
x1
     => (a c)

箱表記では、この結果はつぎのようになります。

 
                   --------------------
                  |                    |
 --------------   |   --------------   |    --------------
| car   | cdr  |  |  | car   | cdr  |   -->| car   | cdr  |
|   a   |   o-----   |   b   |   o-------->|   c   |  nil |
|       |      |     |       |      |      |       |      |
 --------------       --------------        --------------

以前に要素bを保持していた2番目のコンスセルはまだ存在していて、 そのCARもまだbですが、このリストの一部ではありません。

CDRを変更して新たな要素を挿入するのも同様に簡単です。

 
(setq x1 '(a b c))
     => (a b c)
(setcdr x1 (cons 'd (cdr x1)))
     => (d b c)
x1
     => (a d b c)

箱表記では、この結果はつぎのようになります。

 
 --------------        -------------       -------------
| car  | cdr   |      | car  | cdr  |     | car  | cdr  |
|   a  |   o   |   -->|   b  |   o------->|   c  |  nil |
|      |   |   |  |   |      |      |     |      |      |
 --------- | --   |    -------------       -------------
           |      |
     -----         --------
    |                      |
    |    ---------------   |
    |   | car   | cdr   |  |
     -->|   d   |   o------
        |       |       |
         ---------------



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

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

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=Rearrangement"
"texi/elisp21/リストの順序を変更する関数"へのコメント(無し)
検索全文Elisp

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

コンスセルを変更する他の関数については、 5.7 集合としてのリストの利用のSee delqを参照してください。

Function: nconc &rest lists
この関数は、listsのすべての要素を入れたリストを返す。 append(see 節 5.5 コンスセルとリストの構築)と異なり、 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 節 31.15 テキストのソートsortの有用な例については、 23.2 説明文字列の参照documentationを参照。



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5.7 集合としてのリストの利用

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=Sets%20And%20Lists"
"texi/elisp21/集合としてのリストの利用"へのコメント(無し)
検索全文Elisp

リストで、数学の順序のない集合を表現できます。 つまり、リストに現れる要素を集合の要素と考え、 リスト内での順序は無視します。 2つの集合の和集合を作るには、 (要素が重複することを気にしなければ)appendを使います。 集合向けの他の有用な関数には、memqdelq、および、 これらのequal版であるmemberdeleteがあります。

Common Lispに関した注意: Common Lispには、集合演算向けに (要素の重複を避ける)関数unionintersectionがあるが、 GNU Emacs Lispにはない。 必要ならば、読者みずからLispでこれらを書ける。

Function: memq object list
この関数は、objectlistの要素かどうか調べる。 そうならば、 memqobjectが最初に現れるところから始まるリストを返す。 さもなければnilを返す。 memqの文字`q'は、リストの要素に対するobjectの比較に eqを使うことを意味する。 たとえば、

 
(memq 'b '(a b c b a))
     => (b c b a)
(memq '(2) '((1) (2)))    ; (2)(2)eqではない
     => nil

Function: delq object list
この関数は、listからobjecteqであるすべての要素を 破壊的に削除する。 delqの文字`q'は、memqと同様に、 リストの要素に対するobjectの比較にeqを使うことを意味する。

delqがリストの先頭から要素を削除する場合には、 単にリストを辿って削除した要素のつぎから始まる部分リストを返します。

 
(delq 'a '(a b c)) == (cdr '(a b c))

リストの中ほどの要素を削除する場合には、 削除にはCDRの変更を伴います(see 節 5.6.2 リストのCDRの変更)。

 
(setq sample-list '(a b c (4)))
     => (a b c (4))
(delq 'a sample-list)
     => (b c (4))
sample-list
     => (a b c (4))
(delq 'c sample-list)
     => (a b (4))
sample-list
     => (a b (4))

(delq 'c sample-list)は、 3番目の要素を切り取ってsample-listを変更しますが、 (delq 'a sample-list)では、 なにも切り取らずに単に短いリストを返すことに注意してください。 引数listを保持していた変数が、実行後には少ない要素を持つと仮定したり、 もとのリストを保持し続けていると仮定したりしないでください! そのかわりに、delqの結果を保存して、それを使ってください。 多くの場合、つぎのように、 もとのリストを保持していた変数に結果を保存し直します。

 
(setq flowers (delq 'rose flowers))

つぎの例では、delqが一致を取ろうとしている(4)sample-list(4)とはeqではありません。

 
(delq '(4) sample-list)
     => (a c (4))

つぎの2つの関数は、memqdelqに似ていますが、 比較にはeqのかわりにequalを使います。 See 節 2.6 同値述語

Function: member object list
関数memberは、equalを使ってobjectと要素を比較して、 objectlistの要素かどうか調べる。 objectが要素であれば、 memberlist内でそれが最初に現れるところから始まるリストを返す。 さもなければnilを返す。

memqと比較してほしい。

 
(member '(2) '((1) (2)))  ; (2)(2)equalである
     => ((2))
(memq '(2) '((1) (2)))    ; (2)(2)eqではない
     => nil
;; 同じ内容の2つの文字列はequalである
(member "foo" '("foo" "bar"))
     => ("foo" "bar")

Function: delete object list
この関数は、listからobjectequalであるすべての要素を 破壊的に削除する。 membermemeqに対応するように、delqに対応する。 memberと同様に、 要素とobjectとの比較にはequalを使う。 一致する要素をみつけると、delqと同様に要素を削除する。 たとえば、つぎのとおり。

 
(delete '(2) '((2) (1) (2)))
     => ((1))

Common Lispに関した注意: GNU Emacs Lispの関数memberと関数deleteは Maclispから受け継いだものであり、Common Lispからではない。 Common Lisp版では要素の比較にはequalを使わない。

変数に格納したリストに要素を追加する別の方法については、 10.8 変数値の変更の関数add-to-listを参照してください。



[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [表紙] [目次] [索引] [検索] [上端 / 下端]

5.8 連想リスト

URL="http://www.bookshelf.jp/cgi-bin/goto.cgi?file=elisp21&node=Association%20Lists"
"texi/elisp21/連想リスト"へのコメント(無し)
検索全文Elisp

連想リスト(association list)、略してalistは、 キーから値への対応付けを記録しています。 これは連想(associations)と呼ばれるコンスセルのリストです。 各コンスセルのCARはkeyであり、 CDRは連想値(associated value)です。 (6)

連想リストの例を示します。 キーpineを値conesに、キーoakを値acornsに、 キーmapleを値seedsに対応付けています。

 
'((pine . cones)
  (oak . acorns)
  (maple . seeds))

連想リスト内の連想値は任意のLispオブジェクトでよく、キーもそうです。 たとえば、つぎの連想リストでは、シンボルaに数1を、 文字列"b"リスト(2 3)を対応付けています。 リスト(2 3)は連想リストの要素のCDRです。

 
((a . 1) ("b" 2 3))

要素のCDRのCARに連想値を格納するように 連想リストを設計したほうがよい場合もあります。 つぎのようにします。

 
'((rose red) (lily white) (buttercup yellow))

ここで、redroseに対応付けた値と考えます。 この種の連想リストの利点の1つは、関連する別の情報を、 他の項目から成るリストでさえも、CDRのCDRに格納できることです。 1つの欠点は、rassq(下記参照)を使って 指定した値を含む要素を探せないことです。 これらの条件が重要でない場合には、1つの連想リストに関する限り、 一貫性があればどちらを選ぶかは好みの問題です。

上に示した連想リストは、要素のCDRに連想値が収めてあると 考えることもできます。 roseの連想値はリスト(red)になります。

連想リストはスタックなどに置くような情報の記録に使います。 というには、リストの先頭に新たな連想を追加するのが簡単だからです。 指定したキーに対する連想を連想リストから探すとき、 それらが複数個存在する場合には、最初にみつかったものを返します。

Emacs Listでは、連想リストの要素がコンスセルでなくても エラーではありません。 連想リスト探索関数はそのような要素を単に無視します。 他の多くのLispでは、そのような場面ではエラーを通知します。

属性リストもいろいろな意味で連想リストに類似しています。 属性リストは、キーが一度しか現れない連想リストのようにふるまいます。 属性リストと連想リストの比較については、See 節 7.4 属性リスト

Function: assoc key alist
この関数は、alist内のkeyに対する最初の連想を返す。 keyと連想リストの各要素との比較には、 equal(see 節 2.6 同値述語)を用いる。 alistの中にCARがkeyequalである連想が 存在しなければ、nilを返す。 たとえば、つぎのとおり。

 
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
     => ((pine . cones) (oak . acorns) (maple . seeds))
(assoc 'oak trees)
     => (oak . acorns)
(cdr (assoc 'oak trees))
     => acorns
(assoc 'birch trees)
     => nil

つぎは、キーと値がシンボルではない例。

 
(setq needles-per-cluster
      '((2 "Austrian Pine" "Red Pine")
        (3 "Pitch Pine")
        (5 "White Pine")))

(cdr (assoc 3 needles-per-cluster))
     => ("Pitch Pine")
(cdr (assoc 2 needles-per-cluster))
     => ("Austrian Pine" "Red Pine")

関数assoc-ignore-representationassoc-ignore-caseassocに似ていますが、 それらは比較にcompare-stringsを使う点が異なります。 See 節 4.5 文字と文字列の比較

Function: rassoc value alist
この関数は、alistの中でvalueを値とする最初の連想を返す。 alistの中にCDRがvalueequalである連想が 存在しなければ、nilを返す。

rassocassocに似ているが、 alistの各連想のCARのかわりにCDRを比較する点が異なる。 指定した値に対するキーを探す『assocの逆演算』と考えることができる。

Function: assq key alist
この関数は、alist内のkeyに対する最初の連想を返すという意味で assocに似ているが、equalのかわりにeqで比較する。 alist内の連想のCARがkeyeqであるものが存在しないと、 assqnilを返す。 この関数はassocより多用される。 というのは、eqequalより高速であり、 ほとんどの連想リストではキーとしてシンボルを使うからである。

 
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
     => ((pine . cones) (oak . acorns) (maple . seeds))
(assq 'pine trees)
     => (pine . cones)

一方で、キーがシンボルではない連想リストでは、 assqは、通常、有用ではない。

 
(setq leaves
      '(("simple leaves" . oak)
        ("compound leaves" . horsechestnut)))

(assq "simple leaves" leaves)
     => nil
(assoc "simple leaves" leaves)
     => ("simple leaves" . oak)

Function: rassq value alist
この関数は、alistの中でvalueを値とする最初の連想を返す。 alistの中にCDRがvalueeqである連想が 存在しなければ、nilを返す。

rassqassqに似ているが、 alistの各連想のCARのかわりにCDRを比較する点が異なる。 指定した値に対するキーを探す『assqの逆演算』と考えることができる。

たとえばつぎのとおり。

 
(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))

(rassq 'acorns trees)
     => (oak . acorns)
(rassq 'spores trees)
     => nil

rassqでは、 要素のCDRのCARに格納された値を探せないことに注意。

 
(setq colors '((rose red) (lily white) (buttercup yellow)))

(rassq 'white colors)
     => nil

この場合、連想(lily white)のCDRは、 シンボルwhiteではなくリスト(white)である。 連想をドット対記法で書くとこれが明確になる。

 
(lily white) == (lily . (white))

Function: assoc-default key alist test default
この関数は、keyに一致するものをalistから探す。 alistの各要素について、(アトムならば)要素とkeyを、 あるいは、(コンスならば)要素のCARとkeyを比較する。 比較にはこれらを2つの引数としてtestを呼び出す。 引数を渡す順序はこの順なので、 正規表現(see 節 33.3 正規表現の探索)を収めた連想リストに対して string-matchを使うと有益な結果を得られる。 testを省略したりnilであると、比較にはequalを用いる。

上の条件で連想リストの要素がkeyに一致するならば、 assoc-defaultはその要素に基づく値を返す。 要素がコンスならば値は要素のCDR。 さもなければ、戻り値はdefault

keyに一致する連想リストの要素が存在しなければ、 assoc-defaultnilを返す。

Function: copy-alist alist
この関数は、alistを2レベルの深さまでコピーしたものを返す。 各連想ごとに新たなコピーを作るので、 新たな連想リストの連想を変更しても、もとの連想リストは変更しない。

 
(setq needles-per-cluster
      '((2 . ("Austrian Pine" "Red Pine"))
        (3 . ("Pitch Pine"))
        (5 . ("White Pine"))))
=>
((2 "Austrian Pine" "Red Pine")
 (3 "Pitch Pine")
 (5 "White Pine"))

(setq copy (copy-alist needles-per-cluster))
=>
((2 "Austrian Pine" "Red Pine")
 (3 "Pitch Pine")
 (5 "White Pine"))

(eq needles-per-cluster copy)
     => nil
(equal needles-per-cluster copy)
     => t
(eq (car needles-per-cluster) (car copy))
     => nil
(cdr (car (cdr needles-per-cluster)))
     => ("Pitch Pine")
(eq (cdr (car (cdr needles-per-cluster)))
    (cdr (car (cdr copy))))
     => t

この例は、copy-alistにより、 コピーの連想を変更して他のものになぜ影響しないかを示す。

 
(setcdr (assq 3 copy) '("Martian Vacuum Pine"))
(cdr (assq 3 needles-per-cluster))
     => ("Pitch Pine")


[ << ] [ >> ]           [表紙] [目次] [索引] [検索] [上端 / 下端]