The King's Museum

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

Scheme 手習い(2)

第3章:偉大なる cons

rember

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

rember は remove member の略。 ラット(すべての要素がアトムのリスト)内で一致した最初のアトムを削除する関数。

第2の戒律

【第2の戒律】

リストを作るには cons を用いるべし

そのまんまなんだけど、リストを作りたいときは cons を利用する。

firsts

(define (firsts l)
  (cond [(null? l) '()]
        [else (cons (car (car l)) (firsts (cdr l)))]))

firsts はリストを含むリストの最初の要素を集めて再びリストにする関数。

第3の戒律

【第3の戒律】

リストを作らんとせしときは、最初の要素になるものを記述し、しかる後にそれを自然なる再帰に cons すべし。

cons は第一引数は要素、の第二引数は再帰、の形にする。

insertR/insertL

(deifne (insertR new old lat)
  (cond [(null? lat) '()]
        [(eq? (car lat) old) (cons (car lat) (cons new (cdr lat)))]
        [else (cons (car lat) (insertR new old (cdr lat)))]))

insertR は old の右側に new を挿入する関数。

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

insertL は old の左側に new を挿入する関数。

subst/subst2

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

old を new に置き換える関数。

(define (subst2 new o1 o2 lat)
  (cond [(null? lat) '()]
        [(or (eq? o1 (car lat)) (eq? o2 (car lat)))
         (cons new (cdr lat))]
        [else (cons (car lat) (subst2 new o1 o2 (cdr lat)))]))

o1 か o2 を new に置き換える関数。

multirember

(define (multirember a lat)
  (cond [(null?o lat) '()]
        [(eq? (car lat) a) (multirember a (cdr lat))]
        [else (cons (car lat) (multirember a (cdr lat)))]))

ラット内のすべての要素 a を削除して新しいリストを作る関数。 rember の複数要素対応ってところ。

multiinsertR/multiinsertL

(define (multiinsertR new old lat)
  (cond [(null? lat) '()]
        [(eq? (car lat) old)
         (cons old (cons new (multiinsertR new old (cdr lat))))]
        [else (cons (car lat) (multiinsertR new old (cdr lat)))]))
(define (multiinsertL new old lat)
  (cond [(null? lat) '()]
        [(eq? old (car lat))
         (cons new (cons old (multiinsertL new old (cdr lat))))]
        [else (cons (car lat) (multiinsertL new old (cdr lat)))]))

insertL と insertR の複数要素対応版。

感想

第3章は再帰の基本的な構造を学んだ。

ここら辺は SICP でやったことがあるところなので、特に難しくなかった。 でも、SICP よりパターン化してあるからこちらの方がより定着率は高いかな。

(c) The King's Museum