日: 2014年1月22日

insertL-f と insertR-f

rember を rember-f に変形したように、insertL を insertL-f に変形してください、ときた。といってもすぐに答が書いてあるので、ここは逆らわずに写経。

(define insertL-f
  (lambda (test?)
    (lambda (new old l)
      (cond
        ((null? l) (quote ()))
        ((test? (car l) old) (cons new (cons old (cdr l))))
        (else (cons (car l) ((insertL-f test?) new old (cdr l))))))))

同様に、insertR を insertR-f に。

(define insertR-f
  (lambda (test?)
    (lambda (new old l)
      (cond
        ((null? l) (quote ()))
        ((test? (car l) old) (cons old (cons new (cdr l))))
        (else (cons (car l) ((insertR-f test?) new old (cdr l))))))))

見比べればわかるように、insertL-f と insertR-f はよく似ている。実際、関数名を別にすれば違うのは6行目の new を old を cons する順番だけだ。
というわけで、次の課題はこの部分を関数として渡してやれるようにすることだ。

insert-g

まずは、上の6行目の部分だけを行う関数、seqL と seqR を書こう。といってもほとんど自明だ。

(define seqL
  (lambda (new old l)
    (cons new (cons old l))))

(define seqR
  (lambda (new old l)
    (cons old (cons new l))))

さあ、これで insert-g が書ける。全体を示そう。

(define insert-g
  (lambda (test? seq)
    (lambda (new old l)
      (cond
        ((null? l) (quote ()))
        ((test? (car l) old) (seq new old (cdr l)))
        (else (cons (car l) ((insert-g test? seq) new old (cdr l))))))))

(define seqL
  (lambda (new old l)
    (cons new (cons old l))))

(define seqR
  (lambda (new old l)
    (cons old (cons new l))))

(define insertL (insert-g eq? seqL))

(define insertR (insert-g eq? seqR))

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

実行結果：

^o^ > gosh insert-g.scm
(ice cream with topping fudge for dessert)
(tacos tamales and jalapeno salsa)

うまくいった！
と思って答を見たら、こんな定義になってるじゃないか。

(define insert-g
  (lambda (seq)
    (lambda (new old l)
      (cond
        ((null? l) (quote ()))
        ((eq? (car l) old) (seq new old (cdr l)))
        (else (cons (car l) ((insert-g seq) new old (cdr l))))))))

test? はどこへいったんだよ！
まあいい、このままいこう。最後に、seqL を使わずに insertL を定義してください、ときた。前のエントリで書いたように、lambda で作った関数には必ずしも名前をつけなくてもかまわない。ということは、seqL という関数名じゃなくてその定義を渡してやればいいわけだ。

(define insert-g
  (lambda (test? seq)
    (lambda (new old l)
      (cond
        ((null? l) (quote ()))
        ((test? (car l) old) (seq new old (cdr l)))
        (else (cons (car l) ((insert-g test? seq) new old (cdr l))))))))

(define insertL
  (insert-g eq?
    (lambda (new old l)
      (cons new (cons old l)))))

(print (insertL 'topping 'fudge '(ice cream with fudge for dessert)))

^o^ > gosh insert-g2.scm
(ice cream with topping fudge for dessert)

OKのようだ。よかった。

関数を返す関数

前回のエントリでは関数を引数にとる関数が出てきたけど、今度は関数を返す関数（これも高階関数だ）が出てきた。

(define eq?-c
  (lambda (a)
    (lambda (x)
      (eq? x a))))

この関数 eq?-c は a を引数にとり、「x を引数にとって a と比較する関数」を返す。
「これは『カリー化』（Curry-ing）と呼ばれています。」って、カリー化の説明これだけ？
カリー化とは、本来複数の引数を取る関数を引数の一部だけとって「残りの引数を取る関数」を返す関数に変更、というか変換すること、だと理解している。そう間違ってはいないはず。この例の場合では2引数の関数 eq? をカリー化した関数が eq?-c ってわけだ。

返ってくるのが関数だから、名前をつけてやれば普通の関数として使える。

gosh> (define eq?-c
  (lambda (a)
    (lambda (x)
      (eq? x a))))
eq?-c
gosh> (define eq?-salad (eq?-c 'salad))
eq?-salad
gosh> (eq?-salad 'salad)
#t
gosh> (eq?-salad 'tuna)
#f

とはいえ、必要がなければ名前をつけてやることもない。こんなふうにも書ける。

gosh> ((eq?-c 'salad) 'salad)
#t

ふたたび rember-f

で、今度は、rember-f を比較関数 test? を引数にとって「a と l を引数にとる関数」を返す関数に書き直せ、ときた。うん、たぶん書けるだろう。

(define rember-f
  (lambda (test?)
    (lambda (a l)
      (cond
        ((null? l) (quote ()))
        ((test? (car l) a) (cdr l))
        (else (cons (car l) ((rember-f test?) a (cdr l))))))))

(print ((rember-f eq?) 'tuna '(shrimp salad and tuna salad)))

^o^ > gosh rember-f2.scm
(shrimp salad and salad)

うまくいった！