月: 2014年1月

さあ、今日は3章の残りをやっつけるぞ。まずは insertR から。

insertR

insertR はアトム2つ new、old とラット（アトムのリスト）lat を引数に取り、lat の中の old と同じアトムの右側に new を挿入したラットを返す。
もうこのくらいは答えを見ないでも書ける。

(define insertR
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old) (cons old (cons new (cdr lat))))
      (else (cons old (insertR new old (cdr lat)))))))

実行例：

gosh> (insertR 'topping 'fudge '(ice cream with fudge for dessert))
(fudge fudge fudge fudge topping for dessert)

あれ、期待したのと違う。
わかった。間違いは最後の行だ。old を cons してどうする。cons するのは (car lat) だ。

(define insertR
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old) (cons old (cons new (cdr lat))))
      (else (cons (car lat) (insertR new old (cdr lat)))))))

実行例：

gosh> (insertR 'topping 'fudge '(ice cream with fudge for dessert))
(ice cream with fudge topping for dessert)
gosh> (insertR 'jalapeno 'and '(tacos tamales and salsa))
(tacos tamales and jalapeno salsa)

今度はOKだ。jalapeno はハラペーニョかな。

insertL

insertL は insertR と違って new を old の左側に挿入する。これは簡単、new と old の cons する順を入れ替えればいいだけだ。

(define insertL
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old) (cons new (cons old (cdr lat))))
      (else (cons (car lat) (insertL new old (cdr lat)))))))

実行例：

gosh> (insertL 'topping 'fudge '(ice cream with fudge for dessert))
(ice cream with topping fudge for dessert)
gosh> (insertL 'jalapeno 'and '(tacos tamales and salsa))
(tacos tamales jalapeno and salsa)

うまくいった（註：英語の意味は考えないこと）。
と思ったら、5行目の ((eq? (car lat) old) (cons new (cons old (cdr lat)))) は ((eq? (car lat) old) (cons new lat)) とも書けるとのこと。なるほど、そのとおりだ。

書いてみたっていうか、内側のリストが空でないのが保証されているのなら、map （と car ）を使うほうが素直に感じる。まあ、本（「Scheme手習い」）では順を追って説明していくのだろうけど。

(define first
  (lambda (l)
    (map car l)))

実行例：

gosh> (first '((a b) (c d) (e f)))
(a c e)
gosh> (first '())
()
gosh> (first '((five plums) (four) (eleven green oranges)))
(five four eleven)

もし、内側のリストに空リストが混じっているとうまく動かないはずだ。

gosh> (first '((a b) () (c d) (e f)))
*** ERROR: pair required, but got ()
Stack Trace:
_______________________________________

やっぱり。これは car が空リストにはエラーを起こすからだ。

関数 first は空のリストまたはリストのリスト（ただし内側のリストは空ではない）を引数に取り、内側の書くリストの最初のS式からなる新しいリストを返す。
これは答えを見ないで書いてみよう。

(define first
  (lambda (l)
    (cond
      ((null? l) (quote ()))
      (else (cons (car (car l)) (first (cdr l)))))))

さて、うまくいくかな？

gosh> (first '((a b) (c d) (e f)))
(a c e)
gosh> (first '())
()
gosh> (first '((five plums) (four) (eleven green oranges)))
(five four eleven)

うまくいった。

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

[追記]
よく読み返したら、関数名が first じゃなくて firsts だった。ま、内容は変わらないからいいか。

rember は remove member の略だそうだ。関数 rember はアトム a とリスト lat を引数に取って、lat の中の一番最初に現れる a と同じアトムを取り除いたリストを返す。
本文 p.35 には次のような定義が載っている。

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      (else (cond
              ((eq? (car lat) a) (cdr lat))
              (else (rember a (cdr lat))))))))

試してみよう。

gosh> (rember 'bacon '(bacon lettuce and tomato))
(lettuce and tomato)

うまく動いたようだ。
だけど、次の例では期待どおりにはいかない。

gosh> (rember 'and '(bacon lettuce and tomato))
(tomato)

期待した結果は (bacon lettuce tomato) のはず。おかしいのは7行目の再帰の部分だ。再帰を使ってリスト lat の要素をひとつずつ見ていっていきながら a と同じアトムを探しているんだけど、7行目の (rember a (cdr lat)) は再帰するさいに a と同じでないアトム、つまり取り除くべきでないアトムを捨ててしまっている。
ということは、捨てるべきでないアトムを先頭にくっつけてやればいい。どうやるかっていうと、cons を使えばいい。修正したのがこれ。

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      (else (cond
              ((eq? (car lat) a) (cdr lat))
              (else (cons (car lat) (rember a (cdr lat)))))))))

試してみよう。

gosh> (rember 'and '(bacon lettuce and tomato))
(bacon lettuce tomato)

今度は期待どおりに動いた。

第2の戒律
リストを作るには cons を用いるべし。

おまけ。cond は質問とそれに対応する値の組をいくつでもとれるので、それを使って次のように簡単化した定義が載っている（p.41）。

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) a) (cdr lat))
      (else (cons (car lat) (rember a (cdr lat)))))))

実行例：

gosh> (rember 'sauce '(soy sauce and tomato sauce))
(soy and tomato sauce)

「Scheme手習い」本文からは脱線するけど、関数 lat? の定義を見たとき、高階関数 map が使えるんじゃないかと思った。もちろん Gauche にも map は用意されている。
試しに書いてみたのがこれ。

(define all?
  (lambda (l)
    (cond
      ((null? l) #t)
      ((car l) (all? (cdr l)))
      (else #f))))

(define lat?
  (lambda (l)
    (all? (map atom? l))))

lat? を定義する前に補助関数として all? を定義している（探したけど見つからなかったので自分で定義した）。all? はリストを引数に取って、その要素すべてが真なら #t を返す。
さて、試してみよう。

gosh> (lat? '(bacon and eggs))
#t
gosh> (lat? '(bacon (and eggs)))
#f

うまくいったようだ。
ただ、この定義だと必ずリストの最後まで要素を見ていくのに対して、もとの再帰による定義だと場合によっては最後まで見る必要がないから、再帰のほうが効率はいいのかもしれない。

member? も map でできるかな？

lat?

関数 lat? は、引数にリストを取り、そのリストがラット（要素すべてがアトムであるか空であるリスト）のとき #t を返し、そうでないときには #f を返す。
「Scheme手習い」本文（p.16）では次のように定義されている（関数 atom? は定義済みとして）。

(define lat?
  (lambda (l)
    (cond
      ((null? l) #t)
      ((atom? (car l)) (lat? (cdr l)))
      (else #f))))

再帰が出てきた。関数 cond は複数の質問とその質問に対応する値をとり、結果として真となる質問に対応する値を返す。ここではふたつ目の質問 (atom? (car l)) に対応する値 (lat? (cdr l)) の部分が再帰になっている。
いくつか試してみよう。

gosh> (lat? '(Jack Sprat could eat no chicken fat))
#t
gosh> (lat? '((Jack) Sprat could eat no chicken fat))
#f
gosh> (lat? '(Jack (Sprat could) eat no chicken fat))
#f
gosh> (lat? '())
#t

ところで、このラットという用語は Scheme の用語なのか、この本の中でそう呼んでいるだけなのか、ググってみてもよくわからなかった。まあいいか。

member?

関数 member? はアトムとリストを引数に取り、アトムがリストのメンバーであるとき #t を返す。member? の定義は次のようになる（p.23）。

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

ここで誤植発見。本文では4行目が ((null? lat) nil) となっているけど、nil じゃなくて #f の間違いだろう。たぶん。
さて、新しい関数 or が出てきた。or は引数をふたつ取り、どちらかが真であれば #t を返す。このとき、ひとつ目の引数が真であれば、ふたつ目の引数は評価されない。
それから6行目ではまたも再帰が出てきている。それじゃ、いくつか試してみよう。

gosh> (member? 'tea '(coffee tea or milk))
#t
gosh> (member? 'poached '(fried eggs and scrambled eggs))
#f

関係ないけど poached eggs ってのは落とし卵のことのようだ。うちじゃよく味噌汁に入ってる。

再帰とnull?

lat? と member? に共通するのは、リストの要素をひとつずつ、（必要であれば）最後まで見て返す答えを決定することだ。cond のひとつ目の質問には両方の関数で (null? l) が使われている。これでリストの最後に到達したかどうかを判定している。

第1の戒律
（仮）いかなる関数を表現するときも最初の質問はすべて null? にすべし。

関数 eq? は2つの引数を取り、同じものならば真（#t）を返す。

gosh> (eq? 'Harry 'Harry)
#t
gosh> (eq? 'margarine 'butter)
#f

本文には、2つの引数について「両方とも数でないアトムです。」とあるけど、脚注には「実際、eq? の引数にリストがきてもかまいません。」、「実際、eq? の引数に数がきてもかまいません。」とある。なんか、こういう例外というか本文と違うのが多いな。何なんだろ。

gosh> (eq? '(a b c) '(a b c))
#f

ふむ、引数がリストの場合は、同じリストでも偽（#f）になるな。
数ではどうだろう。

gosh> (eq? 7 7)
#t
gosh> (eq? 1 4)
#f

引数が数の場合は、同じ数なら真（#t）になった。

Eq? の掟
関数 eq? は2つの引数を取る。
どちらも数でないアトムでなければならない。

関数 atom? は任意のS式を引数に取り、それがアトムであるとき真（#t）を返す。といっても Gauche に atom? は用意されていないので、まずは脚注にある定義を写経。

gosh> (define atom?
  (lambda (x)
    (and (not (pair? x)) (not (null? x)))))
atom?

関数の定義の仕方は、本文で触れていないのでここでも触れない。そのうち出てくるだろう。

さあ、試してみよう。

gosh> (atom? 'Harry)
#t
gosh> (atom? '(Harry had a heap of apples))
#f
gosh> (atom? (car '(Harry had a heap of apples)))
#t
gosh> (atom? (cdr '(Harry had a heap of apples)))
#f
gosh> (atom? (cdr '(Harry)))
#f

最後の例では、(cdr '(Harry)) が 空リストなので偽（#f）なのだな。

関数 null? は引数が空リストのとき真（#t）を返す。

gosh> (null? '())
#t
gosh> (null? (quote ()))
#t
gosh> (null? '(a b c))
#f

(quote ()) は '() の別の書き方。最後の例では、引数が空リストでないので偽（#f）が返ってきている。

本文には「アトムの null? をたずねることはできません」とあるけど、脚注には「実際、(null? α) は空リスト以外はすべて偽になります。」とある。

gosh> (null? 'spaghetti)
#f

Null? の掟
関数 null? はリストに対してのみ定義される。

関数 cons は任意のS式をリストの先頭に付け加える。

gosh> (cons 'peanut '(butter and jelly))
(peanut butter and jelly)
gosh> (cons '(banana and) '(peanut butter and jelly))
((banana and) peanut butter and jelly)

cons は2つの引数をとり、ひとつ目は任意のS式、ふたつ目はリストでなければならない。

gosh> (cons 'a 'b)
(a . b)

あれ、エラーにならないな。リストともちょっと違う。なんだかわからないけど、そのうち出てくるだろう。それまでは保留。
脚注には、「実際、(cons α β) はすべての値αとβにうまく働いて、(car (cons α β))=α、(cdr (cons α β))=β となります。」とある。

gosh> (car (cons 'a 'b))
a
gosh> (cdr (cons 'a 'b))
b

Cons の掟
関数 cons は2つの引数を取る。
cons の第2引数はリストでなければならない。
結果はリストとなる。