星田さんの記事に対するコメント。
上の2つを参考にしてLetrec＆Lambda版を自作。だんだん書き方が分かってきたかな〜。これも高階関数版を考えようと思ったけど・・こういう一つだけ抜き出すパターンには使えない印象。FoldLやMapの畳み込みが「何回目か」を判定する関数が必要な気がする・・それがあれば (if (= （リスト要素数） （何回目の適用か）) で条件分け出来るんだけどなぁ・・
うん、これは考えすぎかな。
つまり、last-pairって事実上こういう事でしょ?
> (list (car (reverse '(a b c d e f g h))))
'(h)
>
そしてfoldlが書けるのはreverseだ。
(define (my-reverse ls)
(foldl cons '() ls))
従って、これを利用すると、
(define (last-pair4 xs)
`(,(car (foldl cons '() xs))))
あるいは
(define (last-pair4 xs)
(list (car (foldl cons '() xs))))
って事になる。
続いてlist-refの再定義。これを参考にして・・
Letrec&Lambda版。ホイホイ。これもFoldを使おうと思ったら
(if (= n（何回目の適用か）) で条件分けが必要そう・・
追記：こっちはやっぱり畳み込みの回数が分からないと駄目かなぁ。あ、いやもう一つカウンター専用の引数を作れば良いのかな？後でやってみる
追記：無理でしたｗ
さて、確かにこれは難問だ。
何でこれが難しいんだろ?どうして「カウンター専用の」何かが必要な風に追い込まれてるんだろ?
実は理由はハッキリしてる。mapやfoldなんかの高階関数は与えられたリストを最期まで走査しちまうのが原因だ。
普段はそれでいいんだけど、この問題のように「途中で脱出する」ように見えるケースはどうすればいいんだろうか?・・・・・・「途中で脱出する」?
そう、脱出しちまえばいいんだよ。つまりcall/ccの出番だ。
この問題の解はcall/ccとfoldlの合わせ技だ。
(define (list-ref4 xs n)
(call/cc
(lambda (return)
(foldl (lambda (y x)
(if (= n x)
(return y)
(+ x 1))) 0 xs))))
まず、foldlに関しては基本的な使い方だけど、初期値をカウンターとして扱おう。最初は0、そしてラムダ式内で1づつ増やしていく。
foldlの第三引数は外部から与えられたリストxsそのまま、とする。
さて、ここから若干トリッキーかもしれないが、説明していく。foldl内の第二引数(初期値)は１づつ増えて行って、いつ脱出のトリガーになるのか、と言うと外部からやってきた引数nの値に一致した時だ。その時のxsの先頭(つまりyだ)を持って計算を終わらせ脱出すれば、foldlは以降のリスト(xsの残り)については計算しない。
そして、その時のyの値が求める値、となる。つまり、リストxsのn番目の要素だ。
正直言って、この問題は初見難問だけど良問だと思う。自分で思いついたパターンとしては最高傑作の1つになるんじゃないかな?
と言うのも、高階関数の計算途中で脱出したい、ってのはしばしば起こるんだよ。高階関数を使えば短く済むのに、「計算を途中で終了させる為に」再帰を使って全体を書き直すってのもメンド臭い。
そういう場合は高階関数＋call/ccってのは良くあるんだ。
その良くあるパターンを自ら作り出した星田さんはなかなか勘がいいと思います。
