Previous Up Next
3.8 リスト

Exercise 17  [難易度 2] リスト値が扱えるように mini Scheme5 インタプリタを変更せよ． Scheme のリストは空リストを ()，リストへの要素の追加を(2引数)プ リミティブ cons，要素を列挙しリストを構成するための(可変個引数) プリミティブ list で構成する．また，リストが空かどうかを判定する (真偽値を返す)null，先頭要素を返す car，後続リストを返す cdr というプリミティブを使ってリスト操作を行なう．

リストの出力結果は要素を空白で区切って並べ () で囲んだ形になる． 

⇒ (list 1 2 3 4)
(1 2 3 4)
⇒ (cons 0 (list 1 2 3 4))
(0 1 2 3 4)
⇒ (cons (list 1 2) (list 3 4))
((1 2) 3 4)
最後の例からわかるように，Scheme では要素の型が揃っている必要はないこと に注目．(第一要素がリスト (1 2)であり，残りの要素は整数である．) これで，リスト操作をする様々な関数をテストせよ． 

⇒ (letrec ((append (lambda (l1 l2)
                         (if (null l1) l2
                             (cons (car l1) (append (cdr l1) l2))))))
        (append (list 1 2) (list 3 4)))
(1 2 3 4)

Exercise 18  [難易度 2] Scheme では，リスト要素の型が揃う必要がないばかりか，cons の第二引数がリストである必要すらない．実は，Scheme のリストは (cons で作られる)ペア構造の特別な場合として扱われる．つまり， リストは空リストもしくは，リストを第二要素とするペアとして 定義される．このような cons を実装せよ． (この場合正確には car, cdr はそれぞれ，ペアの第一要素・ 第二要素を返すプリミティブである．)

以下のように，第二要素がペアでないペアは . を使って 表示する． 

⇒ (cons 1 2)
(1 . 2)
⇒ (cons 1 (cons 2 (cons 3 4)))
(1 2 3 . 4)
⇒ (cons (cons 1 2) 3)
((1 . 2) . 3)
⇒ (cdr (cons 1 2))
2

Exercise 19  [難易度 3] ML に見られるようなパターンマッチ構文を設計し実装せよ．

Exercise 20  [難易度 2] Scheme では，引用(quotation)といって，(リストなどの)データ値の 外部表現(インタプリタの表示結果)をプログラム中に直接記述して，cons や list などのプリミティブを使うことなく構成することができる． 具体的には外部表現の前に引用符 ' をつけることで，外部表現から 値を構成することができる． 

⇒ '1
1
⇒ '(1 2)
(1 2)
⇒ (cons 3 '(1 2))
(3 1 2)
⇒ (cons '(4 3) '((5 6) 7))
((4 3) (5 6) 7)
⇒ (cdr '(1 2 3))
(2 3)
このような引用機構を実装せよ．ここでは，引用されるものは，整数，リスト， (前の問題をやっている場合)ペアとする．

Previous Up Next