Next: , Up: Cons Cell Type   [Contents][Index]


2.3.6.1 Drawing Lists as Box Diagrams

コンスセルを表現するドミノのような1対のボックスによる図により、リストを説明することができます(Lispリーダーがこのような図を読み取ることはできません。人間およびコンピューターが理解できるテキスト表記と異なり、ボックスの図は人間だけが理解できます)。この図は3要素のリスト(rose violet buttercup)を表したものです:

    --- ---      --- ---      --- ---
   |   |   |--> |   |   |--> |   |   |--> nil
    --- ---      --- ---      --- ---
     |            |            |
     |            |            |
      --> rose     --> violet   --> buttercup

この図では、ボックスは任意のLispオブジェクトへの参照を保持できるスロットを表します。ボックスのペアはコンスセルを表します。矢印はLispオブジェクト(アトム、または他のコンスセル)への参照を表します。

この例では、1番目のボックスは1番目のコンスセルで、それのCARrose(シンボル)を参照または“保持(holds)”します。2番目のボックスは1番目のコンスセルのCDRを保持し、次のボックスペア、すなわち2番目のコンスセルを参照します。2番目のコンスセルのCARvioletで、CDRは3番目のコンスセルです。(最後の)3番目のコンスセルのCDRは、nilです。

同じリスト(rose violet buttercup)を、違うやり方で描いた別の図で表してみましょう:

 ---------------       ----------------       -------------------
| car   | cdr   |     | car    | cdr   |     | car       | cdr   |
| rose  |   o-------->| violet |   o-------->| buttercup |  nil  |
|       |       |     |        |       |     |           |       |
 ---------------       ----------------       -------------------

要素がないリストは空リスト(empty list)で、これはシンボルnilと同じです。別の言い方をすると、nilはシンボルであり、リストでもあります。

以下は、リスト(A ())、または等価な(A nil)をボックスと矢印で描いたものです:

    --- ---      --- ---
   |   |   |--> |   |   |--> nil
    --- ---      --- ---
     |            |
     |            |
      --> A        --> nil

以下はもっと複雑な例です。これは、1番目の要素が2等疎のリスとである、3要素のリスト((pine needles) oak maple)を表します:

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

同じリストを2番目のボックス表記で表すと、以下のようになります:

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