Scheme演習 第3回

品川 嘉久, 浅井 健一, 萩谷 昌己, 西澤 弘毅, 原 謙治
[Table of Contents] [Index] [携帯版]

ペア
  • Schemeにはペアというデータ型が存在し、以下の特徴を持つ。
    • 二つの要素を持つ組を表す
    • 要素は car 部と cdr 部として区別して保持される

cons, car, cdr
  • (cons obj1 obj2)
    • obj1を car部、obj2を cdr部の要素として持つペアを作る関数。
  • (car pair)
    • pairの car部を返す関数。
  • (cdr pair)
    • pairの cdr部を返す関数。

cons, car, cdr の実行例
> (define x (cons 1 2))
> (car x)
1
> (cdr x)
2
; Schemeはペアを下のように表示する。
> x
(1 . 2)

ペアのペア
  • ペアを組み合わせてさらにペアを作ることもできる。
> (define y (cons (cons 1 2) (cons 3 4)))
> (car (cdr y))
3

リスト
  • リストは要素をいくつか並べたデータ構造である。
(1 2 3 4)

list
  • (list obj1 ...)
    • 引数obj1、... を要素として持つリストを作る関数。
> (define 1-through-4 (list 1 2 3 4))
> 1-through-4
(1 2 3 4)

ペアとしてのリスト
  • リストは右下に連続したペアによって実現されている。


  • したがって、ペアを操作する関数でリストを操作できる。

cons, car, cdrによるリスト操作
  • cons, car, cdr の意味をリスト用に解釈し直すと下のようになる。


(carの返す値の種類とcdrの返す値の種類が大きく異なる点に注意。)

    • (cons obj1 obj2)
      • obj1を、リストobj2の左に要素として付け加えたリストを返す関数。
    • (car pair)
      • リストpairの左端の要素を返す関数。
    • (cdr pair)
      • リストpairから左端の要素を除いたリストを返す関数。

実行例
> (cons 10 1-through-4)
(10 1 2 3 4)
> (car 1-through-4)
1
> (cdr 1-through-4)
(2 3 4)
> (car (cdr 1-through-4))
2

ペア, リストの判定関数
  • 下はペアやリストを判定するための述語である。
  • 空リストとは、要素が0個のリストである。
  • 普通のリストの最後にある、何も指していない部分も空リストとみなせる。
    • (pair? obj)
      • objがペア(空リストでないリストも)の場合は#tを返し、それ以外の場合は#fを返す関数。
    • (null? obj)
      • objが空リストの場合は#tを返し、それ以外の場合は#fを返す関数。

リストを操作する関数: square-list
  • これまでに説明した関数を使って、リストを操作する関数をいくつか定義できる。
  • ここでは、関数listに引数を与えず(list)とすることによって、空リストを作っている。
  • また、リストを表す変数には、listではなくlstという名前を付けた方が、関数listと混同しなくて済む。
    • square-listは、リストlstの要素をそれぞれ二乗にする関数。
> (define (square-list lst)
    (if (null? lst)
        (list)
        (cons (* (car lst) (car lst))
              (square-list (cdr lst)))))
> (trace square-list)
> (square-list (list 1 2))
| > (square-list '(1 2))      ;  'の意味は後述
| | > (square-list '(2))
| | | > (square-list '())
| | | ()
| | (4)
| (1 4)
(1 4)

リストを操作する関数: length
  • lengthは、リストlstの長さ(要素の数)を返す関数。
> (define (length lst)
    (if (null? lst)
        0
        (+ 1 (length (cdr lst)))))
> (length (list 1 3 5 7))
4
> (define (length lst)    ; 末尾再帰にしたもの
    (define (length-iter restlst count)
      (if (null? restlst)
          count
          (length-iter (cdr restlst) (+ 1 count))))
    (length-iter lst 0))

リストを操作する関数: append
  • appendは、リストlst1とlst2の要素を続けたリストを返す関数。
> (define (append lst1 lst2)
    (if (null? lst1)
        ; lst1 の空リストにあたる部分を lst2 に置き換える
        lst2
        (cons (car lst1)
              (append (cdr lst1) lst2))))
> (append (list 1 4 9 16 25) (list 1 3 5 7))
(1 4 9 16 25 1 3 5 7)

リストを操作する関数: list-ref
  • list-refは、リストlstのn番目の要素を返す関数(先頭は0番目)
  • これは末尾再帰である。
> (define (list-ref lst n)
    (cond ((null? lst) "Out of range")
          ((= 0 n)     (car lst))
          (else        (list-ref (cdr lst) (- n 1)))))
> (list-ref (list 1 3 5 7) 3)
7

リストを操作する関数: filter
  • filterは、リストlstのうち述語pの適用結果が偽になるような要素を除いたリストを返す関数。
> (define (filter lst p)
    (cond ((null? lst)   (list))
          ((p (car lst)) (cons (car lst) (filter (cdr lst) p)))
          (else          (filter (cdr lst) p))))
> (filter (list 1 -2 3 -4) positive?)
(1 3)

リストのネスト(入れ子構造)
  • リストの要素はペアやリストでも良い。
  • これは、もともとリストがペアでできていることを考えれば当然である。


> (define x (cons (list 1 2)
                  (list 3 4)))
> x
((1 2) 3 4)
> (cdr (car x)) ; (car x) は (1 2)
(2)
> (cdar x)      ; (cdr (car x))の略記
(2)
> (length x)
3
> (define (count-leaf tree)
    (cond ((null? tree) 0) ; 葉のないところは0
          ((pair? tree) (+ (count-leaf (car tree))
                           ; ↑左の部分木の葉の数
                           ; ↓右の部分木の葉の数
                           (count-leaf (cdr tree))))
          (else         1)))  ; 数字は葉
> (count-leaf x)
4


シンボルと quote
  • Schemeではシンボル(アルファベットや + などによる列)は変数として使用されているが、'(クウォート)をつけることによって、変数としての意味を持たないただの文字のようなものへと評価させることができる
> (define a 1)
> (define b 2)
> (list a b)   ; a も b も変数
(1 2)
> (list 'a 'b) ; a も b も文字
(a b)
> (list 'a b)  ; a は文字、b は変数
(a 2)

リストの quote
  • リストは関数適用として使用されているが、同様に ' をつけることによって、
    ただのリスト構造のデータへと評価させることができる
  • また、quoteというシンタックス形式に渡しても同じ意味になる
> '(+ 1 2)  ; + と 1 と 2 からなるリスト
(+ 1 2)
> '(a b c)  ; a と b と c からなるリスト
(a b c)
> '()       ; 空リスト(これが普通のつくり方)
()
> (quote (a b c))
(a b c)

シンボルに関する述語
  • シンボルに関する述語としては、下のようなものがある。
    • (symbol? obj)
      • objがシンボルの場合は#tを返し、それ以外の場合は#fを返す
    • (eq? obj1 obj2)
      • obj1とobj2が等しい場合は#tを返し、それ以外の場合は#fを返す
      • リストどうしを比較した場合はそれぞれがロケーション(ポインタ)として等しい場合か両方が空リストである場合のみ#tを返す
> (symbol? 'a)
#t
> (eq? 'a 'a)
#t
> (eq? 'a 'b)
#f
> (eq? '(a b) '(a b)) ; 別々に作られたリストなので#f
#f
> (define x '(a b))
> (eq? x x)           ; ポインタとして同じ cons セルを指しているので #t
#t
> (eq? '() '())       ; 両方が空リストなので#t
#t

連想リスト
  • (assq obj alist)
    • ペアやリストを直接の要素とするリスト(連想リストという)alistを受け取り、その要素のうちcar部がobjと等しいような最左のものを返す関数
      (ここで等しいとは、eq?による比較)
    • 見つからない場合は#fを返す。
> (define dic '((ami net) (ame rain) (ame candy)))
> (assq 'ame dic)
(ame rain)
> (assq 'amedama dic)
#f

ドット記法とリスト記法
  • リストはペアによって実現されているため、リストの表記とペアの表記には対応がある。

> (list 1 2)
(1 2)
> (cons 1 (cons 2 '()))
(1 2)
> '(1 . (2 . ()))
(1 2)
  • すなわち(a b ...) = (a . (b ...))
という関係がある。このルールを使って、すべてを (* . *) という形 で書く方法をドット記法、逆にピリオドを最も使わずに書く方法をリスト記法 という。
特に、
(a) = (a . ())
(a b) = (a . (b . ()))
(a b . c) = (a . (b . c))
    である。
    Scheme は、結果をできるだけリスト記法で出力する。

シンタックス形式 let
(let ((<変数> <式>) ... (<変数> <式>))
     <body> ...)
  • 局所的な変数を定義する。
  • 定義された変数は ... の中でのみ参照できる。
  • 実行例
> (let ((a #f)
        (b '(1 2))
        (c 3))
    (if a b c))
3

let*
(let* ((<変数> <式>) ... (<変数> <式>))
      <body> ...)
  • 変数を定義する際、前から順に定義する
(let ((<変数> <式>))
 ...
  (let ((<変数> <式>))
    <body> ...) ...)
    と同じ。

let と let* の違い
  • letとlet*の違いは下の実行例の通り
> (define x 5)
> (let ((x 1)
        (y (+ x 1)))    ; この x は外の x を指してしまう
    y)
6
> (let* ((x 1)
         (y (+ x 1)))   ; この x は局所変数の x を指している
    y)
2
> (let* ((y (+ x 1))    ; この x は外の x を指してしまう(局所変数 x はまだ未定義)
         (x 1))
    y)
6

抽象データ型
  • プログラムで何らかのデータ構造を作って操作したいとき
    • それを外から扱うための関数(インターフェース)を定義する
    • インターフェースの中でのみ実際のデータを直接操作する
  • ただし、特別な仕組みを使うわけではなく、データ構造を直接操作しないように心がける、ということ

有理数
  • 分子と分母にあたる値を受け取って有理数を作る関数をmake-rat、
    有理数の分子、分母を返す関数をnumer、denom、
    有理数を表示する関数をprint-ratとする
  • インターフェース
(make-rat <n> <d>)
(numer <x>)
(denom <x>)
(print-rat <x>)
  • 実現したい実行例
(define (+rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (denom x) (numer y)))
            (* (denom x) (denom y))))
> (define one-half (make-rat 1 2))
> (define one-third (make-rat 1 3))
> (print-rat (+rat one-half one-third))
5/6
done


ペアによる有理数の実装
  • ペアで有理数を表すことにしてインターフェースを実装している。

本当の有理数ではないので、分母が0でもエラーにならない。
(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
  • ここでもし(define numer car)と定義すると、後でcarを再定義しても影響を受けない。
(define (print-rat x)
  (write (numer x))
  (display "/")
  (write (denom x))
  (newline)         ; 改行を出力する関数( (display "\n")と同じ)
  'done)
> (print-rat (+rat one-third one-third))
6/9
done
> (print-rat (make-rat 1 0))
1/0
done

make-rat の別の実装
  • gcdは最大公約数を返す関数。これによって有理数が約分される。
(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))
> (print-rat (+rat one-third one-third))
2/3
done


区間演算
  • インターフェース
(make-interval <n> <n>)
(lower-bound <x>)
(upper-bound <x>)
(print-interval <x>)
  • 実現したい実行例
(define (intadd x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
(define (intmul x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))
(define (intdiv x y)   ; 区間 y は 0 をまたがないとする
  (intmul x
          (make-interval
            (/ 1 (upper-bound y))
            (/ 1 (lower-bound y)))))
> (define x1 (make-interval -1 1))   ; -1 <= x1 <= 1
> (define x2 (make-interval 2 3))    ;  2 <= x2 <= 3
> (print-interval (intadd x1 x2))
[1,4]                                ; 1 <= x1+x2 <= 4
done
> (print-interval (intmul x1 x2))
[-3,3]                               ; -3 <= x1*x2 <= 3
done
> (print-interval (intdiv x1 x2))
[-1/2,1/2]                           ; -1/2 <= x1/x2 <= 1/2
done


ペアによる区間の実装
(define (make-interval a b)
  (cons a b))
(define (lower-bound x) (car x))
(define (upper-bound x) (cdr x))
(define (print-interval x)
  (display "[")
  (write (lower-bound x))
  (display ",")
  (write (upper-bound x))
  (display "]\n")
  'done)

レポート課題3

問1
  • 次のリストの中の 5 を取り出す car と cdr の組合せを示せ。
    • (1 (2 3 (4 5) 6))
    • ((5))

問2
  • 次に挙げる関数を定義し実行せよ。

(map proc list)
  • リストlistの要素一つ一つに対して一引数関数procを適用し、結果をリストにして返す関数。
  • 実行例
> (map (lambda (x) (+ x 1)) (list 1 2 3 4))
(2 3 4 5)
  • ヒント
    • プログラムの構造は、関数 square-list に似たものになるはずである。

(add-squares list)
  • 数のリストlistの要素の平方の和を返す関数。
  • 実行例
> (add-squares (list 1 10 100))
10101
  • ヒント
    • プログラムの構造は、関数 length に似たものになるはずである。

(reverse list)
  • リストlistを逆順にしたリストを返す関数。
  • 実行例
> (reverse (list 1 2 3 4))
(4 3 2 1)
  • ヒント
    • プログラムの構造は、関数 append に似たものになるはずである。

(assq obj alist)
  • 定義は前述。
  • ヒント
    • プログラムの構造は、関数 list-refやfilter に似たものになるはずである。

問3
  • ふたつのリスト(ネストされていても良い)は等しい要素が同じ順で並んでいるとき等しい (equal) という
    (この定義は再帰的であることに注意)
  • シンボルからなるふたつのリストが等しいかを判定する関数 equal? を定義し実行せよ。
    (これらはいずれも eq? を使うと #f になることに注意。)
> (equal? '(this is a list) '(this is a list))
#t
> (equal? '(this is a list) '(this (is a) list))
#f
> (equal? '(this (is (a)) list) '(this (is (a)) list))
#t
> (equal? '(this (is (a)) list) '(this (is (b)) list))
#f
  • ヒント
    • プログラムの構造は、関数 count-leaf に似たものになるはずである。

問4(成績に無関係)
  • 関数を使った if と真偽値の実装として、次のようなものが考えられる。
> (define (if2 b t e) (b t e))
> (define (true x y) x)
> (define (false x y) y)
> (if2 true 1 2)
1
> (if2 false 1 2)
2
  • この if2 は call-by-value になってしまうが、その点を除けばif 、true、falseを実現できている。
  • そこで、関数を使って cons2、car2、cdr2を実装せよ。
  • ただし、他の既定義の関数や define、lambda 以外のシンタックス形式を使用してはいけない。
  • また、確かに (car2(cons2 x y)) が x になることを確認せよ。


This page is generated by mtd2html.