日: 2014年1月19日

関数 intersectall は、セットのリスト l-set を引数にとって、各セットすべての共通部分を返す関数。
これは答えを見なければわからなかった。というか、はじめに思いついたのは fold を使った実装。でも、fold はまだ出てきてないから使わないとするとどうしたらいいんだろう、と。
とりあえず fold を使ったコードを載せる。

(use mymodule)

(define intersect
  (lambda (s1 s2)
    (cond
      ((null? s1) (quote ()))
      ((member? (car s1) s2) (cons (car s1) (intersect (cdr s1) s2)))
      (else (intersect (cdr s1) s2)))))

(define intersectall
  (lambda (l-set)
    (fold intersect (car l-set) (cdr l-set))))

(print (intersectall '((a b c) (c a d e) (e f g h a b))))
(print (intersectall '((6 pears and)
                       (3 peaches and 6 peppers)
                       (8 pears and 6 plums)
                       (and 6 prunes with lots of apples))))

^o^ > gosh -I. intersectall2.scm
(a)
(and 6)

期待どおりに動いている。
で、こっちが fold を使わないコード。答を見ながら写経した。

(use mymodule)

(define intersect
  (lambda (s1 s2)
    (cond
      ((null? s1) (quote ()))
      ((member? (car s1) s2) (cons (car s1) (intersect (cdr s1) s2)))
      (else (intersect (cdr s1) s2)))))

(define intersectall
  (lambda (l-set)
    (cond
    ((null? (cdr l-set)) (car l-set))
    (else (intersect (car l-set) (intersectall (cdr l-set)))))))

(print (intersectall '((a b c) (c a d e) (e f g h a b))))

なるほど、最終条件は (null? (cdr l-set)) なら値は (car l-set)、つまり最後のセットはそのまま返す。で、途中は (car l-set) と (cdr l-set) で再帰したセットに intersect を適用している。これですべてのセットの共通部分が取り出せるわけだ。
結果は：

^o^ > gosh -I. intersectall.scm
(a)
(6 and)

fold を使ったものと同じになった。よかった、fold 使ったコードも間違いじゃなかった。

この関数 xxx はどんな関数か、という質問。

(use mymodule)

(define xxx
  (lambda (s1 s2)
    (cond
      ((null? s1) (quote ()))
      ((member? (car s1) s2) (xxx (cdr s1) s2))
      (else (cons (car s1) (xxx (cdr s1) s2))))))

(print (xxx '(stewed tomatoes and macaroni casserole)
            '(macaroni and cheese)))

^o^ > gosh -I. xxx.scm
(stewed tomatoes casserole)

答は s1 に含まれていて s2 に含まれていないすべてのアトムからなるセットを返す関数。
(car s1) が s2 のメンバーなら cons せずに、メンバーでないなら cons して再帰している。終了条件は (null? s1) で値は () だ。まあ、見ればわかるよね。

関数 union は、2つのセット s1 と s2 の和集合を返す関数。
(car s1) が s2 のメンバーなら cons せずに（なぜなら s2 に含まれているから）、メンバーでないなら cons して再帰すればいい。

(use mymodule)

(define union
  (lambda (s1 s2)
    (cond
      ((null? s1) s2)
      ((member? (car s1) s2) (union (cdr s1) s2))
      (else (cons (car s1) (union (cdr s1) s2))))))

(print (union '(stewed tomatoes and macaroni casserole)
              '(macaroni and cheese)))

^o^ > gosh -I. union.scm
(stewed tomatoes casserole macaroni and cheese)

今度は2つの集合の共通部分に関する関数だ。

intersect?

関数 intersect? は、セット s1 と s2 が共通部分を持てば #t を返す。

(use mymodule)

(define intersect?
  (lambda (s1 s2)
    (cond
      ((null? s1) #f)
      ((member? (car s1) s2) #t)
      (else (intersect? (cdr s1) s2)))))

(print (intersect? '(stewed tomatoes and macaroni)
                   '(macaroni and cheese)))

^o^ > gosh -I. intersect_p.scm
#t

これを or を使って書くと短くなる。

(use mymodule)

(define intersect?
  (lambda (s1 s2)
    (cond
      ((null? s1) #f)
      (else (or (member? (car s1) s2) (intersect? (cdr s1) s2))))))

(print (intersect? '(stewed tomatoes and macaroni)
                   '(macaroni and cheese)))

ここで誤植発見。cond の1つ目の質問 (null? s1) に対する値が本（「Scheme手習い」）では nil になっているけど、これは #f の間違いだろう。

^o^ > gosh -I. intersect_p2.scm
#t

intersect

関数 intersect はセット s1 と s2 の共通部分を返す。

(use mymodule)

(define intersect
  (lambda (s1 s2)
    (cond
      ((null? s1) (quote ()))
      ((member? (car s1) s2) (cons (car s1) (intersect (cdr s1) s2)))
      (else (intersect (cdr s1) s2)))))

(print (intersect '(stewed tomatoes and macaroni)
                  '(macaroni and cheese)))

^o^ > gosh -I. intersect.scm
(and macaroni)

※追記あり

subset?

s1、s2 のセット2つを引数にとり、s1 が s2 のサブセット（部分集合）のとき #t を返す関数。

(use mymodule)

(define subset?
  (lambda (s1 s2)
    (cond
      ((null? s1) #t)
      ((member? (car s1) s2) (subset? (cdr s1) s2))
      (else #f))))

(print (subset? '(5 chicken wings)
                '(5 hamburgers 2 pieces fried chicken and light duckling wings)))
(print (subset? '(4 pounds of horseradish)
                '(four pounds chicken and 5 ounces horseradish)))

^o^ > gosh -I. subset.scm
#t
#f

eqset?

2つのセット s1 と s2 が等しければ #t を返す関数。お互いがお互いのサブセットなら、等しいといえる。これをコードにするとこうなる。

(use mymodule)

(define subset?
  (lambda (s1 s2)
    (cond
      ((null? s1) #t)
      ((member? (car s1) s2) (subset? (cdr s1) s2))
      (else #f))))

(define eqset?
  (lambda (s1 s2)
    (cond
      ((subset? s1 s2) (subset? s2 s1))
      (else #f))))

(print (eqset? '(6 large chickens with wings)
               '(6 chickens with large wings)))

^o^ > gosh -I. eqset.scm
#t

and を使うともっと短くなる。eqset? だけ示すと：

(define eqset?
  (lambda (s1 s2)
    (cond
      (else (and (subset? s1 s2) (subset? s2 s1))))))

こうなると cond はいらなくなるので、もっと短くなる。

(define eqset?
  (lambda (s1 s2)
    (and (subset? s1 s2) (subset? s2 s1))))

3行になった。

追記

subset? も and を使うと短くなる。

(use mymodule)

(define subset?
  (lambda (s1 s2)
    (cond
      ((null? s1) #t)
      (else (and (member? (car s1) s2) (subset? (cdr s1) s2))))))

(print (subset? '(5 chicken wings)
                '(5 hamburgers 2 pieces fried chicken and light duckling wings)))
(print (subset? '(4 pounds of horseradish)
                '(four pounds chicken and 5 ounces horseradish)))

^o^ > gosh -I. subset2.scm
#t
#f

今日から7章。集合（セット）が出てきた。セットは、同じアトムが2回以上現れないリストのこと。
まずは、引数として与えられたリストが、セットかどうかを判定する関数 set? から。

set?

(define member?
  (lambda (a lat)
    (cond
      ((null? lat) #f)
      (else (or (eq? (car lat) a) (member? a (cdr lat)))))))

(define set?
  (lambda (lat)
    (cond
      ((null? lat) #t)
      ((member? (car lat) (cdr lat)) #f)
      (else (set? (cdr lat))))))

(print (set? '(apple peaches apple plum)))
(print (set? '(apples peaches pears plums)))
(print (set? '(apple 3 pear 4 9 apple 3 4)))

実行：

^o^ > gosh set.scm
#f
#t
#f

うまくいった。と思ったら、ページ（p.133）の下のほうのやり取りで、「これは次のデータに対してもうまく動きますか。　(apple 3 pear 4 9 apple 3 4)」「はい、member? は eq? ではなく equal? を使って書かれていますから。」とある。いつのまに書き直したんだ、と思って本を読み直したら、5章の最後のやり取りで書き直したことになっているらしい（ほかに該当するところが見当たらない）。この本では eq? は数ではないアトムを引数にとることになっている（eq? の掟）。
とはいえ、実際には eq? は引数が数でも正しく動くので、本と実際とでくい違ってしまっているわけだ。ま、いいか。一応、equal? を使った member? を載せておく。

(use mymodule)

(define member?
  (lambda (a lat)
    (cond
      ((null? lat) #f)
      (else (or (equal? (car lat) a) (member? a (cdr lat)))))))

これも mymodule.scm に追加しておこう。

makeset

次はリストからセットを作る makeset。

(use mymodule)

(define makeset
  (lambda (lat)
    (cond
      ((null? lat) (quote ()))
      ((member? (car lat) (cdr lat)) (makeset (cdr lat)))
      (else (cons (car lat) (makeset (cdr lat)))))))

(print (makeset '(apple peach pear peach plum apple lemon peach)))

実行：

^o^ > gosh -I. makeset.scm
(pear plum apple lemon peach)

OK。では次に multirember を使って makeset を書け、と。この multirember も equal? を使って書くみたいだな。

(use mymodule)

(define multirember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      ((equal? (car lat) a) (multirember a (cdr lat)))
      (else (cons (car lat) (multirember a (cdr lat)))))))

(define makeset
  (lambda (lat)
    (cond
      ((null? lat) (quote ()))
      (else (cons (car lat) (makeset (multirember (car lat) (cdr lat))))))))

(print (makeset '(apple peach pear peach plum apple lemon peach)))

^o^ > gosh -I. makeset2.scm
(apple peach pear plum lemon)

うまく動いた。けど、この実装での結果が本（p.144）と違っている。たぶん間違っているのは本のほう。だって、makeset の2つの定義では違う動作をするはずなのに、本では結果が同じになってるから。