日: 2014年1月9日

firstをmapを使って書いてみた

書いてみたっていうか、内側のリストが空でないのが保証されているのなら、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

関数 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

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)