関数型言語の勉強にSICPを読もう - (22) 2章 - データによる抽象の構築 - 2.3.2 (90-94ページ)

問題2.60

;; element-of-set?は変更の必要がない。
;; 重複が許される分リストが大きくなるので多少効率が下がる。
(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x set))))

;; ただ足すだけ。集合の定義的にはこれで良いと思う。効率は上がる。
(define (adjoin-set x set)
  (cons x set))

;; これもまた効率は上がる
(define (union-set set1 set2)
  (list set1 set2))

解答を見たら

(define adjoin-set cons)
(define union-set append)

よく考えたらこれで良い。

問題2.61

昨晩は全然頭が回らなくて解けなかった。今日見たら簡単だった。

(define (adjoin-set x set)
  (let ((element (car set)))
    (cond ((equal? x element) set)
          ((> element x) (cons x set))
          (else (cons element (adjoin-set x (cdr set)))))))

(adjoin-set 4 (list 1 2 3 4 5))
(adjoin-set 4 (list 1 2 3 5 6))
(adjoin-set 4 (list 1 2 3 4 5 6))
gosh> (1 2 3 4 5 6)
gosh> (1 2 3 4 5 6)
gosh> (1 2 3 4 5)

問題2.62

ノートにunionの様子を書きながら進めた。
再帰への抵抗がだんだん薄れてきて良い傾向。
動くと思ったコードがケアレスミスで一発で動かないので気を付けましょう。

(define (union-set set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          ((= (car set1) (car set2)) (cons (car set2) (union-set (cdr set1) (cdr set2))))
          ((>= (car set1) (car set2)) (cons (car set2) (union-set set1 (cdr set2))))
          (else (cons (car set1) (union-set (cdr set1) set2)))))

そういえば trace ですが組み込みの関数にも使えることに今更気づきました。
(trace cdr)とかやっておくとめっちゃ便利。

(use slib)
(require 'trace)
(trace union-set)
(trace cdr)
(union-set (list 1 2 3 4) (list 2 4 6))

ちなみに (car set1) (car set2)が良く参照されるのでletを使ってみたのだけどcondを分断するから微妙だなぁと思ってやめた。
解答では

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else (let ((x1 (car set1)) (x2 (car set2)))
                (cond ((= x1 x2) (cons x1 (union-set (cdr set1) (cdr set2))))
                      ((< x1 x2) (cons x1 (union-set (cdr set1) set2)))
                      ((< x2 x1) (cons x2 (union-set set1 (cdr set2)))))))))

となっていて、分断されていた.
ここは好みの問題だろうか。それともこれが普通？

二進木としての集合

木構造は何回か勉強したことがありますが以外と実践したことがない罠。
しかしSICPは本当にコストパフォーマンス高いです。
信じてもらえないかもしれないですが僕がいま読み終わっている90ページまでにいくつも目から鱗や、新しい概念がありました。

木構造も cons です。
木構造をCやJavaScriptで書いても全然違和感はないのですが、Schemeだとさらに違和感がないのはなんでなんだろう。
洗脳されてきた？

(define (make-tree entry left right)
  (list entry left right))
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))

element-of-set?

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= x (entry set)) #t)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        ((> x (entry set))
         (element-of-set? x (right-branch set)))))

問題2.63

ノートに書いて確かめたが、同じ結果になる気がする。
計算量はO(n log n) O(n)らしいです。

問題2.64

quotientってなんだっけ。「商」か。
正直partial-treeが何をやっているかは分かりませんでした。
答えを見たら納得。

問題2.65

partial-treeが分からなかったのでパスしたのですが、答えを見たらtree->listしてlistとして演算してからtreeに戻すというやりかたを見て納得した。

問題2.66

最近2問題が解けていないのとまとめ問題の香りがするのできっちり解こうと思います。

まずは選択子／構成子など。

(define (make-record key value)
  (cons key value))
(define (key-of-record record)
  (car data))
(define (value-of-record record)
  (cdr data))

lookupはこんなかんじ？

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) #f)
        (else
         (let ((record (car set-of-records)))
           (cond ((= given-key (key record)) (record))
                 ((> given-key (key record)) (lookup given-key (right-branch set-of-records)))
                 (else (lookup given-key (left-branch set-of-records))))))))

※「SICPを読もう」の目次はこちら