function - 関数のn回目の繰り返し適用を計算するスキーム手順は?

Question

誰もこれに精通していますか？

f と正の整数 n を計算する手続きを入力として受け取り、f の n 回目の繰り返し適用を計算する手続きを返す手続きを書きなさい。この手順は、次のように使用できる必要があります。

((repeated square 2) 5)
625

関数の構成用に作成した次のコードがソリューションをより簡単にするのに役立つことはわかっていますが、ここからどこに行くべきかわかりません。

(define (compose f g) (lambda (x) (f (g x))))

Answer 1

まあ、あなたはおそらくこのようなものが欲しいですよね？

((repeated square 3) 5)
-> (square ((repeated square 2) 5))
-> (square (square ((repeated square 1) 5)))
-> (square (square (square ((repeated square 0) 5))))
-> (square (square (square (identity 5))))

(Scheme で事前定義されているかどうかはわかりませんidentity。ない場合は簡単に記述できます。)

現在、これは直接再現できません。これは、呼び出しの外側のコードrepeatedを任意のもので魔法のように囲むことができないためです。しかし、これらの削減ステップは、 を使用して書き直すとどのように見えるcomposeでしょうか? 得られたステップのリストからパターンを見つけて、それを再現できますか?

Answer 2

(define (repeated f n)
  (if (zero? n)
    identity
    (lambda (x) ((repeated f (- n 1)) (f x)))))

または、「構成」の使用を主張する場合:

(define (repeated f n)
  (if (zero? n)
    identity
    (compose (repeated f (- n 1)) f)))