eqlist?

eqlist?

eqlist? はS式のリスト l1 と l2 が等しければ #t を返し、そうでなければ #f を返す。
今度はちょっと、いやだいぶややこしい。少しずついこう。
まず、本文で質問が9つあるといっているのは、l1、l2 とも次の3つの状態が考えられて、その組み合わせが9つある、ということだ。

  • 空リスト
  • アトムがリストに cons されたもの
  • リストが別のリストに cons されたもの

これにしたがってスクリプトを書く(というか写経する)と:

(use mymodule)

(define eqlist?
  (lambda (l1 l2)
    (cond
      ((and (null? l1) (null? l2)) #t)
      ((and (null? l1) (atom? (car l2))) #f)
      ((null? l1) #f)
      ((and (atom? (car l1)) (null? l2)) #f)
      ((and (atom? (car l1)) (atom? (car l2)))
      (and (eqan? (car l1) (car l2)) (eqlist? (cdr l1) (cdr l2))))
      ((atom? (car l1)) #f)
      ((null? l2) #f)
      ((atom? (car l2)) #f)
      (else
        (and (eqlist? (car l1) (car l2)) (eqlist? (cdr l1) (cdr l2)))))))

(print (eqlist? '(strawberry ice cream) '(strawberry cream ice)))
(print (eqlist? '(banana ((split))) '((banana) (split))))
(print (eqlist? '(beef ((sausage)) (and (soda))) '(beef ((sausage)) (and (soda)))))

ファイル名は eqlist.scm とした。
9つの条件をひとつずつ cond の質問に置き換えている。最初の3つの質問(1~3番目)は l1 が空リストの場合、次の3つの質問(4~6番目)が l1 がアトムがリストに cons されたものの場合、else を含む最後の3つの質問(7~9番目)が l1 がリストが別のリストに cons された場合だ。

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

ここまではOK、難しくない。ところがこのあとの本文のやり取りはちょっと腑に落ちない。p.94には「式 (and (null? l1) (null? l2)(or (null? l1) (null? l2)) が、最初の3つの場合にきちんと答を出すという意味ですか。」「はい。」とある。腑に落ちないのは「最初の3つの場合」の部分だ。これは質問の1~3をさしているのだろけど、この3つは l1 が空リストの場合だ。だけど、(or (null? l1) (null? l2)) は l1 が空リストじゃなくても l2 が空リストなら真となる。つまり、この部分は質問の2~3だけじゃなくて、質問4((and (atom? (car l1)) (null? l2)))と質問7((null? l2))も含んでいるわけだ。そしてそのすべての場合に #f になる。これで l1 か l2 と少なくとも一方が空リストの場合を網羅したことになる。

ここで、書き直した eqlist? が出てくる(p.94)。ファイル名は eqlist2.scm としよう。

(use mymodule)

(define eqlist?
  (lambda (l1 l2)
    (cond
      ((and (null? l1) (null? l2)) #t)
      ((or (null? l1) (null? l2)) #f)
      ((and (atom? (car l1)) (atom? (car l2)))
        (and (eqan? (car l1) (car l2)) (eqlist? (cdr l1) (cdr l2))))
      ((or (atom? (car l1)) (atom? (car l2))) #f)
      (else
        (and (eqlist? (car l1) (car l2)) (eqlist? (cdr l1) (cdr l2)))))))

(print (eqlist? '(strawberry ice cream) '(strawberry cream ice)))
(print (eqlist? '(banana ((split))) '((banana) (split))))
(print (eqlist? '(beef ((sausage)) (and (soda))) '(beef ((sausage)) (and (soda)))))

見るとわかるように最初の eqlist? では9つあった質問が5つになっている。
もう一点、or を使った質問が2つある。1つ目は上に書いたとおり、l1 と l2 のどちらか一方だけが空リストの場合、2つ目の or は (car l1) と (car l2) のどちらか一方だけがアトムの場合だ。これは最初の eqlist? の質問6と8に相当する。
1つ目の or で質問が3つ、2つ目の or で質問が1つ減って、質問は9つから5つになったわけだな。
正しく動くか試してみよう。

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

OKのようだ。

equal?

equal? はアトムかリスト(すなわちS式)2つを引数にとって、等しければ #t、そうでなければ #f を返す。

(use mymodule)

(define equal?
  (lambda (s1 s2)
    (cond
      ((and (atom? s1) (atom? s2)) (eqan? s1 s2))
      ((atom? s1) #f)
      ((atom? s2) #f)
      (else (eqlist? s1 s2)))))

ここで、2番目と3番目の質問は冗長だ。1番目の質問が真にならなければ、s1 と s2 のどちらかはアトムではないのがわかっているんだから、2つをまとめて (or …) とできる。

(use mymodule)

(define equal?
  (lambda (s1 s2)
    (cond
      ((and (atom? s1) (atom? s2)) (eqan? s1 s2))
      ((or (atom? s1) (atom? s2)) #f)
      (else (eqlist? s1 s2)))))

もう一度、eqlist?

equal? があれば eqlist? をもっと簡単にできる。equal? は引数がアトムかリストかを気にせずに比較できるのだから、eqlist2.scm の9~11行目を省略できるわけだ。equal? を使って書き直した eqlist? は次のようになる(ファイル名は eqlist3.scm)。

(use mymodule)

(define equal?
  (lambda (s1 s2)
    (cond
      ((and (atom? s1) (atom? s2)) (eqan? s1 s2))
      ((or (atom? s1) (atom? s2)) #f)
      (else (eqlist? s1 s2)))))

(define eqlist?
  (lambda (l1 l2)
    (cond
      ((and (null? l1) (null? l2)) #t)
      ((or (null? l1) (null? l2)) #f)
      (else
        (and (equal? (car l1) (car l2)) (eqlist? (cdr l1) (cdr l2)))))))

(print (eqlist? '(strawberry ice cream) '(strawberry cream ice)))
(print (eqlist? '(banana ((split))) '((banana) (split))))
(print (eqlist? '(beef ((sausage)) (and (soda))) '(beef ((sausage)) (and (soda)))))

うまく動くか試してみよう。

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

大丈夫のようだ。

第6の戒律
関数が正しいときのみ簡単化せよ。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください