multiinsertLR&coを書いてみた

これだよ、これ!
継続渡しスタイルの関数を1から自分で書けるようになるには、書く練習しなきゃね!


ということで、以下のようなmultiinsertLR関数を、継続渡しスタイルで書き直す練習です。

(define multiinsertLR
  (lambda (new oldL oldR lat)
    (cond
     ((null? lat) '())
     ((eq? (car lat) oldL) (cons new (cons oldL (multiinsertLR new oldL oldR (cdr lat)))))
     ((eq? (car lat) oldR) (cons oldR (cons new (multiinsertLR new oldL oldR (cdr lat)))))
     (else (cons (car lat) (multiinsertLR new oldL oldR (cdr lat)))))))

latはアトムからなるリスト、newとoldLとoldRはアトムです。
latの中からoldLを見つけたらoldLの左側にnewを挿入して、oldRを見つけたらoldRの右側にnewを挿入する関数です。
例えば...

gosh> (define lat '(foo bar baz bar))
lat
gosh> (define oldL 'baz)
oldL
gosh> (define oldR 'foo)
oldR
gosh> (define new 'hoge)
new
gosh> (multiinsertLR new oldL oldR lat)
(foo hoge bar hoge baz bar)

こんな感じですね。

こんなmultiinsertLR関数を、以下のような決まりを作って継続渡しスタイルの関数multiinsertLR&coに書き直します。

  • プロトタイプは(multiinsertLR&co new oldL oldR lat col)
  • new、oldL、oldR、latの意味は同じ
  • 継続としてcolを渡す
  • colのプロトタイプは(col newlat left-insertion right-insertion)
  • colの引数newlatでアトムをコレクションしていく
  • left-insertionとright-insertionはそれぞれ左右の挿入回数
(define multiinsertLR&co
  (lambda (new oldL oldR lat col)
    (cond
     ((null? lat)
      (col '() 0 0))
     ((eq? (car lat) oldL)
      (multiinsertLR&co new oldL oldR
			(cdr lat)
			(lambda (newlat L R)
			  (col

ここまできて手が動かなくなりました。
newlatに結果がたまっていくのは分かるんですが、今現在、どんなリストなのか分からん。
ためていくんだから、newlatにnewを追加するんだよなぁ。
newlatの末尾にoldLを追加するのか?先頭に追加するのか?
いや待て。
リストの末尾にアトムを追加してリストを作る構文は習ってないぞ。
consだったら(cons アトム リスト)ってやれるから先頭に追加するのかなぁ。
いったい、newlatはどんな値なんだよ!


たぶん、142ページの最後と143ページの最初に参考になることが書いてありそうだけど、意味が分からん。
英語が読めん!!


んで、ちょっと答え(143ページの3つめ)を見ました。
で、出した答えが

(define multiinsertLR&co
  (lambda (new oldL oldR lat col)
    (cond
     ; 空のリストからはいくら探してもoldLやoldRは見つかりませんよ、と
     ((null? lat)
      (col '() 0 0))
     ; oldLが見つかった
     ((eq? (car lat) oldL)
      (multiinsertLR&co new oldL oldR
			(cdr lat)
			(lambda (newlat L R)
			  (col (cons new
				     (cons oldL newlat))
			       (+ L 1) R))))
     ; oldRが見つかった
     ((eq? (car lat) oldR)
      (multiinsertLR&co new oldL oldR
			(cdr lat)
			(lambda (newlat L R)
			  (col (cons oldR
				     (cons new newlat))
			       L (+ R 1)))))
     ; oldLとoldRのどちらでもなかった
     (else
      (multiinsertLR&co new oldL oldR
			(cdr lat)
			(lambda (newlat L R)
			  (col (cons (car lat) newlat)
			       L R)))))))

143ページの3つめには(car lat)が

  • oldLだったとき
  • oldLとoldRのどちらでもなかったとき

の継続が書いてあったので、そこからoldRが見つかった時の継続を推測...。

実行結果は

gosh> (define lat '(foo bar baz bar))
lat
gosh> (define oldL 'baz)
oldL
gosh> (define oldR 'foo)
oldR
gosh> (define new 'hoge)
new
gosh> (multiinsertLR&co new oldL oldR lat (lambda (newlat L R) newlat))
(foo hoge bar hoge baz bar)

だから、まぁ...できてるっぽいけど。
まだ分かったとは絶対に言えない。

分からないこと
新しい継続作る時に、引数で受け取った継続をどう利用していいか分からない