(はじめよう Scheme 6)

ペア、リスト及びベクタ

Schemeでは2種類のコンテナが標準で用意されている。

ベクタ型

ベクタは固定長のコンテナである。ランダムアクセス及びサイズ取得が定数時間で完了可能である。文字列同様、ベクタもリテラルベクタとそうではないものの2種類があり、前者を破壊的変更することはR7RSではエラーである。
ベクタの例：

;; リテラルなベクタ
#(1 2 3)    ;; 1, 2 及び3を含む長さ3のベクタ
#(1 b "c")  ;; 要素は何を含んでもよい

;; 実行時に生成されるベクタ
(vector 1 2 3)      ;; #(1 2 3)
(make-vector 3 'a)  ;; #(a a a)


;; 参照は0始まり
(vector-ref #(1 2 3) 0)
;; -> 1

;; 破壊的変更
(let ((v (vector 1 2 3)))
  (vector-set! v 0 4)
  v)
;; -> #(4 2 3)

;; エラー(処理系によっては問題ない)
(vector-set! #(1 2 3) 0 4)

;; 長さを取得
(vector-length #(1 2 3))
;; -> 3

ペアとリスト型

ペアはSchemeにおいてもっともよく使われ、かつもっとも重要なデータ型である。ベクタ同様リテラルなペアとそうでないものがある。ペアは以下のように記述可能である。

;; リテラルなペア
'(a . b)

;; 実行時に生成されるペア
(cons 'a 'b)

;; 判別
(pair? '(a . b)) ;; -> #t

他の型と違いconsという手続きを使うことに注意したい。要素を参照するには以下のようにする。

(car '(a . b))
;; -> a

(cdr '(a . b))
;; -> b

carで先頭の要素、cdrで後方の要素を取り出す。

リストは複数のペアから構成される型である。ペアの後方の要素にペアが入るとリストになる。Schemeではもっとも後ろの要素が空要素(())だった場合にリスト(proper list)と呼び、そうでない場合にはドットリスト(dotted list)と呼ぶ。

;; ドットリスト
(cons 'a (cons 'b 'c))
;; -> (a b . c)

;; リスト
(cons 'a (cons 'b '())
;; -> (a b)

(list 'a 'b)
;; -> (a b)

リストの要素参照及びサイズ取得は先頭から末尾までたどる必要があるので線形時間処理になる。

;; ペアの特殊系なので、car及びcdrが使える
(car '(1 2 3)) ;; -> 1
(cdr '(1 2 3)) ;; -> (2 3)

;; 要素の位置を指定することも可能(0開始)
(list-ref '(a b c) 2) ;; -> c

;; 判別
(list? '(1 2 3))   ;; -> #t
(list? '(1 2 . 3)  ;; -> #f
;; リストはペアの特殊系なのでこれも真になる
(pair? '(1 2 3))   ;; -> #t

;; 長さ取得(リストのみ)
(length '(1 2 3)) ;; -> 3

;; これはエラー(処理系によっては何らかの値を返す)
(length '(1 2 . 3))

ここでリストの表記に注目したい。リストの表記とSchemeのコードは酷似していることに気付いただろうか？これはSchemeのコードもリストで記述されているということを意味する。ソースがリストであるということが真価を発揮するのは、マクロを記述するときである。マクロについては次回にやることとする。

設問 6.1
以下の動作をする手続きiotaを作成せよ。

(iota 10) ;; -> (0 1 2 3 4 5 6 7 8 9)
(iota 5)  ;; -> (0 1 2 3 4 5)