[ 目次, 前節, 次節, 索引 ]

2.2.1 並びの表現





図2.4 対の鎖で表現した1, 2, 3, 4の並び

対を使って作ることの出来る有用な構造は 並び(sequence)---データオブジェクトの順序づけられた集り---である. 対を使って並びを表現する方法はもちろんいろいろある. 特に直截的な表現を図2.4に示すが, 1, 2, 3, 4の並びが鎖状の対で表現される. 鎖での, それぞれの対のcarが対応する項で, cdrが鎖での次の対である. 最後の対のcdrは箱とポインタ記法では, 斜線, プログラムでは変数 nilの値で表現される, 対でない特別の値を指すことで, 並びの終りを示す. 全体の並びは入れ子になったcons演算で構成される.
(cons 1
      (cons 2
            (cons 3
                  (cons 4 nil))))

   入れ子のconsで作られた対の並びを リスト(list)といい, Schemeはリストを作るのに役立つ listという基本的手続きを提供する.8 上の並びは(list 1 2 3 4)で作ることが出来る. 一般に

(list a1⟩  ⟨a2⟩   ...   ⟨an)



(cons a1(cons a2(cons ... (cons an⟩  nil) ... )))

と等価である. Lispシステムはリストを印字する時は便宜的にかっこで囲まれた要素の並びを印字する. そこで図2.4のデータオブジェクトは(1 2 3 4)と印字される.

(define one-through-four (list 1 2 3 4))

one-through-four
(1 2 3 4)
(list 1 2 3 4)と, その式を評価して得たリスト(1 2 3 4)を混同しないよう注意しよう. 式(1 2 3 4)を評価しようとすると, 解釈系が手続き1を引数2, 34に作用しようとしたというエラーになる.

   carはリストの最初の項を選択し, cdrは先頭の項以外からなる部分リストを選択すると考えてよい. carcdrの入れ子の作用はリストの二番目, 三番目, それに続く項を取り出すのに使う.9 構成子consは, 先頭に追加の項がつく他は元と同じリストを作る.

(car one-through-four)
1

(cdr one-through-four)
(2 3 4)

(car (cdr one-through-four))
2

(cons 10 one-through-four)
(10 1 2 3 4)

(cons 5 one-through-four)
(5 1 2 3 4)
対の鎖を終端するのに使うnilの値は要素の一つもない並び, 空リスト(empty list)と考えてよい. nilという言葉はラテン語の「何もない」という意味の語nihilの短縮形である.10
リスト演算
要素の並びをリストとして表現する対の使用法には, リストを順に cdrダウン」することで, リストを操作する慣習的な技法を伴う. 例えば手続き list-refは引数としてリストと数値nをとり, リストのn番目のものを返す. リストの要素は0から番号をつける習わしである. list-refを計算する方法は次の通り:

n = 0 なら list-refはリストのcarを返す.

• そうでなければ, list-refはリストのcdrの(n - 1) 番目の項を返す.

(define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) (- n 1))))

(define squares (list 1 4 9 16 25))

(list-ref squares 3)
16

   リスト全体をcdrダウンすることもよくある. これに役立つようにSchemeには null?という基本手続きがあり, 引数が空リストかどうかテストする. リストの中にある項の個数を返す手続き lengthは, その典型的な使い方を示す:


(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))

(define odds (list 1 3 5 7))

(length odds)
4
length手続きは単純な再帰的計画で実装してある. 簡約ステップは:

• 任意のリストのlengthはそのリストのcdr length足す1である.

これが基底の場合:

• 空リストのlengthは0である.

にたどり着くまで繰り返し作用させられる. lengthはまた反復の形で計算出来る:

(define (length items)
  (define (length-iter a count)
    (if (null? a)
        count
        (length-iter (cdr a) (+ 1 count))))
  (length-iter items 0))

   もう一つの慣習的プログラミングは, 引数として二つのリストをとり, その要素を結合して新しいリストを作る手続きappendのように, リストを cdrダウンしつつ, consアップ」するものである:

(append squares odds)
(1 4 9 16 25 1 3 5 7)

(append odds squares)
(1 3 5 7 1 4 9 16 25)
appendは再帰的計画を使っても実装出来る. リストlist1 list2appendするには, 次を行う:

list1が空リストなら, 結果は単にlist2である.

• そうでなければ, list1cdrlist2 appendし,その結果にlist1carconsする:

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

問題 2.17


与えられた(空でない)リストの最後の要素だけからなるリストを返す手続き last-pairを定義せよ:
(last-pair (list 23 72 149 34))
(34)


問題 2.18


引数としてリストをとり, 同じ要素の逆順のリストを返す手続き reverseを定義せよ:
(reverse (list 1 4 9 16 25))
(25 16 9 4 1)


問題 2.19


1.2.2節の両替の計算のプログラムを考えよう. プログラムの使っている通貨が簡単に変えられると, 例えば英国の1ポンドの両替の出し方の数を計算することも出来, 嬉しい. あのプログラムを書いた時, 通貨の知識は一部は手続きfirst-denominationに, また一部は手続きcount-changeに分散されていた. (これが米国に5種類の硬貨のあることを知っていた.) 両替をするのに使う硬貨のリストを与えることが出来れば, さらに嬉しいに違いない.

   手続きccを書き直し, その第二引数を, どの硬貨を使うかでなく, 使う硬貨の値のリストとする. 硬貨の種類を定義するリストが作れる.

(define us-coins (list 50 25 10 5 1))

(define uk-coins (list 100 50 20 10 5 2 1 0.5))
ccを次のように呼び出す:
(cc 100 us-coins)
292
こうするには, プログラムccを多少変える必要がある. 同じ恰好をしているが, 第二引数のアクセスが次のように変る:
(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))
手続きfirst-denomination, except-first-denominationおよびno-more?をリスト構造の基本的演算を使って定義せよ. リスト coin-valuesの順は, ccの答に影響があるか. なぜか.

問題 2.20


手続き+, *およびlistは任意個の引数をとる. そういう手続きを定義する一つの方法は, defineドット末尾記法 (dotted-tail notation)で使うことだ. 手続き定義で, 最後のパラメタの名前の前にドットがあるパラメタ並びは, 手続きが呼び出される時, 前の方のパラメタはいつものように前の方の引数の値になるが, 最後のパラメタの値は残りの引数のリストになることを意味する. 例えば,

(define (f x y . z) body)

の定義なら, 手続きfは二つかそれを超える個数の引数で呼び出すことが出来る.
(f 1 2 3 4 5 6)
を評価すると, fの本体でxは1, yは2, zはリスト(3 4 5 6)になる.

(define (g . w) body)

の定義なら, 手続きgは零個かそれを超える個数の引数で呼び出すことが出来る.
(g 1 2 3 4 5 6)
を評価すると, gの本体でwはリスト(1 2 3 4 5 6)になる.11

   この記法を使って, 一つかそれを超える個数の整数をとり, 先頭と同じ偶奇性を持つ引数のリストを返す手続きsame-parityを書け. 例えば

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

(same-parity 2 3 4 5 6 7)
(2 4 6)

リストの写像
極めて有用な演算は, ある変換をリストの各要素に作用させ, 結果のリストを作るものである. 例えば次の手続きはリストの各数値を与えられた係数倍する:

(define (scale-list items factor)
  (if (null? items)
      nil
      (cons (* (car items) factor)
            (scale-list (cdr items) factor))))

(scale-list (list 1 2 3 4 5) 10)
(10 20 30 40 50)

この一般的考えを抽象化し, 1.3節のように, 高階手続きとして表した共通パターンに取り込むことが出来る. この高階手続きをmapという. mapは引数として一引数の手続きとリストをとり, その手続きをリストの各要素に作用させて出来た結果のリストを返す:12


(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

(map abs (list -10 2.5 -11.6 17))
(10 2.5 11.6 17)

(map (lambda (x) (* x x))
     (list 1 2 3 4))
(1 4 9 16)
mapを使ってscale-listを新しく定義出来る:

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

   mapは共通パターンを取り込んだだけでなく, リストを扱うより高いレベルの抽象化を達成するが故に重要な構成要素である. scale-listの初めの定義では, プログラムの再帰的構造のため, リストの要素ごとの処理に注目させた. mapを使ったscale-listの定義では, そのレベルでの細部を押し隠し, 係数倍が要素のリストを結果のリストに変換することを強調する. 二つの定義の違いは, 計算機が異るプロセスを実行すること(そんなことはないが)ではなく, われわれがプロセスを異って考えることにある. 実際mapは抽象の壁を建て, リストを変換する手続きの実装を, リストの要素をどう取り出し, どう組み合せるかのような細部から隔離する. 図2.1の壁と同様に, この抽象は並びを並びに変換する操作の考え方は保存したまま, 並びをどう実装するかの低レベルの詳細を変更する柔軟さをもたらす. 2.2.3節では, プログラムを構成する枠組として並びの使い方を拡大する.

問題 2.21


手続きsquare-listは引数として数のリストをとり, これらの数の二乗のリストを返す.

(square-list (list 1 2 3 4))
(1 4 9 16)
ここにsquare-listの二つの定義がある. 欠けている式を補い, それぞれを完成せよ:
(define (square-list items)
  (if (null? items)
      nil
      (cons ⟨??⟩ ⟨??⟩)))

(define (square-list items)
  (map ⟨??⟩ ⟨??⟩))


問題 2.22


Louis Reasonerは問題2.21の初めのsquare-listを書き直し, 反復プロセスを生成するようにした:
(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things) 
              (cons (square (car things))
                    answer))))
  (iter items nil))
困ったことにこのsquare-listの定義は, 考えていたのと逆の順に答のリストを作った. なぜか.

   Louisはconsの引数を交換して虫をとろうとした:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))
これも動かなかった. なぜか.

問題 2.23


手続きfor-eachmapに似ている. 引数として手続きと要素のリストをとる. しかし, 結果のリストを作るのではなく, for-eachは要素のそれぞれに左から右へ順に手続きを作用させる. 手続きを要素に作用させて返される値は使わない. for-eachは, 印字のような行動を起す手続きと一緒に使う. 例えば
(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
57
321
88
for-eachの呼出しが返す値(上には示さない)は真のような任意のものであってよい. for-eachを実装せよ.



8 本書では, リスト (list)はリスト終りの印で終端した対の鎖を意味する. リスト構造(list structure)は反対に, リストだけでなく, 対で作られた任意のデータ構造を指す.

9 carcdrの入れ子の作用は書くのが煩わしいので, Lispの方言はその省略形を用意している. 例えば

(cadr ⟨arg⟩) = (car (cdr ⟨ arg⟩))

こういう手続きの名前はcで始りrで終る. その間の acar演算, dcdr演算を表し, 名前に現れる順に作用させる. 名前carcdrは, cadrのような単純な組合せが発音出来るために生き延びている.

10 注意すべきはLisp方言の標準化で, いかに多くのエネルギーが, 文字通り何もないものの議論に費されたかである. nilは普通の名前であるべきか, nilの値は記号であるべきか, それはリストであるべきか, 対であるべきか. Schemeではnilは普通の名前であり, 本節ではその値がリスト終りの印である変数として使う. (ちょうどtrueが真の値を持つ普通の変数であるのと同じ.) CommonLispを含むLispの他の方言では, nilを特別な記号として扱う. 多くの言語の標準化口論に耐えてきた本書の筆者は, この問題を避けて通りたい. 2.3節でクォートを紹介すると, 空リストを'()と書き, 変数nilを完全に排除する.

11 lambdaを使ってfgを定義するには
(define f (lambda (x y . z) ⟨body⟩))
(define g (lambda w ⟨body⟩))
と書く.

12 Schemeが標準的に用意しているmap手続きは, ここに述べたものより一般的である. より一般的 mapは, n引数の手続きとn個のリストをとり, 手続きをリストのすべての第一要素に作用させ, リストのすべての第二要素に作用させ, 等々させて, 結果のリストを返す. 例えば

(map + (list 1 2 3) (list 40 50 60) (list 700 800 900))
(741 852 963)

(map (lambda (x y) (+ x (* 2 y)))
     (list 1 2 3)
     (list 4 5 6))
(9 12 15)

[ 目次, 前節, 次節, 索引 ]