[Index] [TOC]

Scheme演習 第3回


品川 嘉久, 浅井 健一, 萩谷 昌己, 西澤 弘毅, 原 謙治

ペア

cons, car, 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

> (define 1-through-4 (list 1 2 3 4))
> 1-through-4
(1 2 3 4)

ペアとしてのリスト


cons, car, cdrによるリスト操作


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

実行例

> (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

ペア, リストの判定関数

リストを操作する関数: square-list

> (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

> (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

> (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

> (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

> (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

> (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

> '(+ 1 2)  ; + と 1 と 2 からなるリスト
(+ 1 2)
> '(a b c)  ; a と b と c からなるリスト
(a b c)
> '()       ; 空リスト(これが普通のつくり方)
()
> (quote (a b c))
(a b c)

シンボルに関する述語

> (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

連想リスト

> (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) = (a . ())
(a b) = (a . (b . ()))
(a b . c) = (a . (b . c))

シンタックス形式 let

(let ((<変数> <式>) ... (<変数> <式>))
     <body> ...)
> (let ((a #f)
        (b '(1 2))
        (c 3))
    (if a b c))
3

let*

(let* ((<変数> <式>) ... (<変数> <式>))
      <body> ...)
(let ((<変数> <式>))
 ...
  (let ((<変数> <式>))
    <body> ...) ...)

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 <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 (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 の別の実装

(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

問2

(map proc list)

> (map (lambda (x) (+ x 1)) (list 1 2 3 4))
(2 3 4 5)

(add-squares list)

> (add-squares (list 1 10 100))
10101

(reverse list)

> (reverse (list 1 2 3 4))
(4 3 2 1)

(assq obj alist)

問3

> (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

問4(成績に無関係)

> (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

This page is generated by mtd2html.