The King's Museum

ソフトウェアエンジニアのブログ。

Scheme 手習い(4)

第5章:*すごい* 星がいっぱいだ

元ネタは『2001 年宇宙の旅』のボーマン船長のセリフらしい。 そういえばそんなセリフもあったな。

rember*

(define (rember* a l)
  (cond [(null? l) '()]
        [(atom? (car l))
         (cond [(eq? a (car l)) (rember* a (cdr l))]
               [else (cons (car l) (rember* a (cdr l)))])]
        [else (cons (rember* a (car l)) (rember* a (cdr l)))]))

アトムとリストの両者を含むリストから特定のアトムを削除する関数。 S 式のリストから、特定のアトムを削除する関数ともいえる。

最後段の cons の第一引数が、(car l) に対する rember* になっているところがポイント。 ここでは (car l) はリストであることが保障されている。

insertR*

(define (insertR* new old l)
  (cond [(null? l) '()]
        [(atom? (car l))
         (cond [(eq? old (car l))
                (cons old (cons new (insertR* new old (cdr l))))]
               [else (cons (car l) (insertR* new old (cdr l)))])]
        [else (cons (insertR* new old (car l))
                    (insertR* new old (cdr l)))]))

S 式のリスト内の任意のアトムの右側にアトムを挿入する関数。

第1の戒律

【第1の戒律(最終版)】

アトムのリスト lat を再帰せしときは、2つの質問、(null? lat) と else を行うべし。

数 n を再帰せしときは、2つの質問、(zero? n) と else を行うべし。

S 式のリスト l を再帰せしときは、3つの質問、(null? l)、(atom? (car l))、else を行うべし。

第4の戒律

【第4の戒律(最終版)】

再帰の間は少なくとも1つの引数を常に変化させるべし。

アトムのリスト lat を再帰せしときは、(cdr lat) を用いるべし。

数 n を再帰せしときは、(sub 1) を用いるべし。

S 式のリスト l を再帰せしときは、(null? l) も (atom? (car l)) も真でないならば、(car l) と (cdr l) を用いるべし。

必ず最終条件に向かって変化すべし。

変化せし引数は、必ず最終条件でテストすべし。 すなわち、cdr を用いるときは、最後に null? で、sub1 を用いるときは、最後に zero? でテストすべし。

occur*

(define (occur* a l)
  (cond [(null? l) 0]
        [(atom? (car l))
         (cond [(eq? (car l) a) (add1 (occur* a (cdr l)))]
               [else (occur* a (cdr l))])]
        [else (+ (occur* a (car l)) (occur* a (cdr l)))]))

S 式のリスト内に特定のアトムが何個現れるかを数える関数。

subst*

(define (subst* new old l)
  (cond [(null? l) '()]
        [(atom? (car l))
         (cond [(eq? old (car l)) (cons new (subst* new old (cdr l)))]
               [else (cons (car l) (subst* new old (cdr l)))])]
        [else (cons (subst* new old (car l))
                    (subst* new old (cdr l)))]))               

S 式のリスト内の任意のアトムを新しいアトムで置き換える関数。

insertL*

(define (insertL* new old l)
  (cond [(null? l) '()]
        [(atom? (car l))
         (cond [(eq? (car l) old)
                (cons new (cons old (insertL* new old (cdr l))))]
               [else (cons (car l) (insertL* new old (cdr l)))])]
        [else (cons (insertL* new old (car l)) (insertL* new old (cdr l)))]))       

S 式のリスト内の任意のアトムの左にアトムを挿入する関数。

member*

(define (member* a l)
  (cond [(null? l) #f]
        [(atom? (car l))
         (cond [(eq? (car l) a) #t]
               [else (member* a (cdr l))])]
        [else (or (member* a (car l)) (member* a (cdr l)))]))

S 式のリスト内に任意のアトムがあるかどうかを判断する関数。

leftmost

(define (leftmost l)
  (cond [(atom? (car l)) (car l)]
        [else (leftmost (car l))]))

S 式のリスト内の最も左のアトムを求める関数。 空リストは考慮しない。

eqlist?

;; 冗長バージョン
(define (eqlist? a b)
  (cond [(and (null? a) (null? b)) #t]
        [(and (null? a) (atom? (car b))) #f]
        [(null? a) #f]
        [(and (atom? (car a)) (null? (car b))) #f]
        [(and (atom? (car a)) (atom? (car b)))
         (and (eq? (car a) (car b)) (eqlist? (cdr a) (cdr b)))]
        [(atom? a) #f]
        [(null? b) #f]
        [(atom? b) #f]
        [else (and (eqlist? (car a) (car b))
                   (eqlist? (cdr a) (cdr b)))]))

;; シンプルバージョン
(define (eqlist? a b)
  (cond [(and (null? a) (null? b)) #t]
        [(or (null? a) (null? b)) #f]
        [(and (atom? (car a)) (atom? (car b)))
         (and (eq? (car a) (car b)) (eqlist? (cdr a) (cdr b)))]
        [(or (atom? (car a)) (atom? (car b))) #f]
        [else (and (eqlist? (car a) (car b))
                   (eqlist? (cdr a) (cdr b)))]))         

S 式のリストが等しいかどうかを確認する関数。 次のパターンの組み合わせで考える。

  • リストが null
  • リストの先頭(car)がアトム
  • それ以外(リストの先頭がリスト)

equal?

(define (equal? a b)
  (cond [(and (atom? a) (atom? b)) (eq? a b)]
        [(or (atom? a) (atom? b)) #f]
        [else (eqlist? a b)]))

S 式のリストだけでなく、アトムが等しいかどうかも確認できる関数。 すなわち、二つの S 式が等しいかを確認する関数。

第6の戒律

【第6の戒律(最終版)】

関数が正しいときのみ簡単化せよ

感想

S 式に対する操作を学習した。

再帰的なリスト(S 式)になるとすぐに頭が混乱していたけど、この章のおかげで自分の頭の中の見通しがよくなった気がする。

(c) The King's Museum