高階関数クイズをやった
これ。
unlambdaとかlazy k(というかコンビネータ論理)を思い出した。
以下は答えそのものじゃないけど、思考手順が書いてあるので見たくない人はみない事。
とりあえず「twice twice twice add1 0 => 16」までは手で展開してみたものの、次のでどうも手ではやってられなさそうな気配になったので、ちゃんと変換ルールを考える事に。
自分はLisperなので、まずひたすら括弧をつけた。
(f x) ; twice0 ((twice f) x) ; twice1 (((twice twice) f) x) ; twice2 ((((twice twice) twice) f) x) ; twice3 (((((twice twice) twice) twice) f) x) ; twice4
それから、手でtwice3まで展開してみて、その結果を眺めた。
展開
(f x) ; twice0 (f (f x)) ; twice1 (f (f (f (f x)))) ; twice2 (f (f ... (f (f x))))...)) ; twice3(fは16個)
「twiceが一個増える毎に、展開結果のfがたくさん増える」というルールのようだ。
ここでtwiceというコンビネータは実際にはどういう意味なのかを類推した結果、答えに辿りついた。
答えがあっているか、Gaucheで検算した。
(define ((twice f) x) (f (f x))) (define (add1 x) (+ 1 x)) ;; 上の式を流用できるように定義する (define f add1) (define x 0) ;; 上の式をコピペした (f x) ; twice0 ((twice f) x) ; twice1 (((twice twice) f) x) ; twice2 ((((twice twice) twice) f) x) ; twice3 (((((twice twice) twice) twice) f) x) ; twice4
あってた。
