リスト構造

よくある質問

Schemeでは，(e)と e は異なる．



括弧の中の先頭の式は，関数として扱われる
(e)では，eを引数のない関数として扱う．
例：
> 10
10
> (10)
. . procedure application: expected procedure, given: 10
(no arguments)
よくある質問

Schemeの比較


数値： =
記号： eq?




内部で同じアドレスで表現されている
記号の比較に使える
記号のみの比較： symbol=?
例：
> (eq? (fact 100) (fact 100))
#f
> (eq? (/ 1 100) (/ 1 100))
#f
> (eq? 'abc 'abc)
#t
リスト



項目の集まり．
項目の数が計算中に変動する項目の集まりを
実現するデータ構造
リストと言う言葉は日常生活でも用いる



必需品リスト
リストアップする
コンピュータサイエンスのリストと日用語のリストとは
どこが似ていて，どこが違うか考えよ．
リストを作る


空のリスト empty
項目（要素） a1， a2， …， an のリストを作る



(list a1 a2 … an)
(list)で空のリストを作ることができる
リストの先頭に一つの項目を加える

(cons item alist)



リストalistの先頭に項目itemを入れた新しいリストを作
る
alistは変更されないことに注意
(list a1 a2)と(cons a1 (cons a2 empty))は同じ

言語レベルを変えて確認せよ
計算結果のリストの表示方法

言語: Beginning Student
> (cons 10 empty)
(cons 10 empty)
> (list 10 20)
(cons 10 (cons 20 empty))

リストはconsとemptyからできて
いる
言語: Beginning Student with List Abbreviations
> (cons 10 empty)
(list 10)
> (list 10 20)
(list 10 20)
略記
計算結果のリストの表示方法

言語: Pretty Big
> (cons 10 empty)
(10)
> (cons 10 (cons 20 empty))
(10 20)
さらに略記
リストからデータを取り出す

ｆirst: 最初の項目を取り出す


(first (cons 'pear alist)) => 'pear
任意のxに対して，
(first (cons x alist)) => xの評価結果
リストからデータを取り出す

rest: 最初の項目を除いた残りのリストを取り出
す



(rest (cons 'pear (cons 'apple empty)))
=> (cons 'apple empty)
(rest (list 'pear 'apple))
=> (list 'apple)
任意のx，任意のリストalistに対して，
(rest (cons x alist)) => alistの評価結果
２番目の項目を取り出す

second を用いる

(define (second x) (first (rest x)))
リストを調べる

空リストを判別する

empty?


(empty? (list))
空でないリストを判別する

cons?




(cons? empty)
(cons? (list))
(cons? (list 1 2))
(cons? 1)
リスト処理のプログラムー例

記号(symbol)からなるリストsymbolsに，ある特定
の記号sが含まれているか調べる
contain-apple? の仕様
;; contain-apple? : list of symbols -> boolean
;; リストが記号’appleを含んでいれば、trueを
;; さもなければ falseを返す関数
(define (contain-apple? symbols) ...)
;; (contain-apple? (cons 'orange (cons 'apple empty)))
;; => true
;; (contain-apple? (cons 'orange (cons 'pear empty)))
;; => false
contain-apple?
(define (contain-apple? symbols)
(cond
[(empty? symbols) false]
[else
(cond [(eq? (first symbols) ‘apple) true]
[else
(contain-apple? (rest symbols))])]))
リスト処理のプログラムの一般形
(define (prog-for-los alist)
(cond
[(empty? alist) ..... ]
[else ... (first alist) ...
(prog-for-los (rest alist)) ...]
)
)
リストの中のsymbolを数える
;; how-many : list of symbols -> number
;; to determine how many symbols are on symbols
(define (how-many symbols) ...)
how-manyのプログラム
(define (how-many symbols)
(cond
[(empty? symbols) ... ]
[else ... (first symbols)
(how-many (rest symbols)) ]))
(define (how-many symbols)
(cond
[(empty? symbols) 0]
[else (+ 1 (how-many (rest symbols)))] ))
consとappend


consはリストに新たな要素を加えて，新たなリス
トを作成する
appendは二つのリストを連結して新たなリスト
を作る
(cons 'a (cons 'b (cons 'c empty)))

ここでは３つのconsが使われている．

(cons ‘c empty)では，空リストに記号’cを付け加えて，c
からなるリスト(list 'c)を作る.

(cons 'b (cons 'c empty)))では，リスト(list 'c)に記号’b
を付け加えて，’bと’cからなるリスト(list 'b 'c)を作る．

(cons 'a (cons 'b (cons 'c empty)))では，リスト(list ‘b
‘c)に記号’cを付け加えて，’aと’bと’cから成るリスト(list
'a 'b 'c)を作る．
(append (cons 'a empty) (cons 'b (cons 'c empty)))

記号’bと ‘cからなるリスト(cons ’b (cons ‘c empty))
に，記号’aからなるリストを連結して，
記号’a, ‘b, ‘cからなるリスト
(cons 'a (cons 'b (cons 'c empty)))を作る．

上の式を評価すると
 言語：beginning students


(cons ‘a (cons ’b (cons ‘c empty)))となる．
言語：beginning students with list abbreviations

(list 'a 'b 'c)となる
appendの定義
(define (append x y)
(cond [(empty? x) y]
[else (cons (first x) (append (rest x) y))]))
システムに関数appendは定義されているので，自分の
appendには違う名前をつけること．
リストの長さ
(define (list-length x)
(cond [(empty? x) 0]
[else
(+ 1 (list-length (rest x)))]))
数のリストの比較
(define (num-list=? x y)
(cond [(empty? x) (empty? y)]
[(empty? y) (empty? x)]
[else
(and (= (first x) (first y))
(num-list=? (rest x) (rest y)))]))
実行例
> (num-list=? (list 1 2) (list 1 2))
#t
> (num-list=? (list 1 2) (list 1 3))
#f
リストの中にリスト
> (define cities (list (list 'Ibaraki 'Tsukuba 'Tsuchiura 'Mito)
(list 'Chiba 'Kashiwa 'Matsudo)))
> cities
((Ibaraki Tsukuba Tsuchiura Mito) (Chiba Kashiwa Matsudo))
> (first cities)
(Ibaraki Tsukuba Tsuchiura Mito)
> (first (first cities))
Ibaraki
> (rest (first cities))
(Tsukuba Tsuchiura Mito)

Download Report