StandardMLでxに対して関数fをn回実行した値を求めたい

質問

StandardMLでxに対して関数fをn回実行した値f^n(x)=f(f(f(..(f(x)))))を求める関数ofuncを作りたい。
('a->'a)*int*'a->'a。ofunc(fn x=>x+1,10,0)ならば１０を返す関数。

自分で途中までアルゴリズムなどを考えてみました。
基底：ｎが０であればnulを返す
それ以外であればFの関数をn回実行する

fun ofunc(F,n,x)=
| if n=0 then nil else ofunc(F,n,x)
|

n=0回以外の場合のプログラムが分かりません。ご指導をよろしくお願いします。

回答No.3

salsberry · ベストアンサー

MLに限らず、再帰的なプログラミングは初めてということでしょうか？
ofunc() の定義の中で「n回繰り返す」とは考えない方がいいですよ。
リンク先も参照してください。

ofunc(f, n, x) が f^n(x) を表すなら、f^(n-1)(x) の値は ofunc(f, n-1, x) で得られますよね。これでもう答えの7割方書いています。

> nが0であればnilを返すというのは0を返すでよろしいでしょうか。

例えば f(x) = x+0.1 だとして、
n=2: ofunc(f, 2, 5.0) -> 5.2
n=1: ofunc(f, 1, 5.0) -> 5.1
n=0: ofunc(f, 0, 5.0) -> 0
という結果になったら不自然だと思いませんか？

参考URL：

http://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0

お礼

回答して頂きありがとうございました。
なんとかプログラムを書くことができました。
本当に何度もお世話になりました。

回答No.2

salsberry

う～ん、この問題はあまりML固有の知識は要らないんですが…

f^1(x) = f(x)
f^2(x) = f( f(x) )
f^3(x) = f( f( f(x) ) ) = f( f^2(x) )
f^4(x) = f( f^3(x) )

f^n(x) = f( f^(n-1)(x) )

ところで、xにfを0回適用したらnilというのはおかしくありませんか？

補足

度々すいません。このような問題を解くのが初めてなので、n回繰り返し実行するというところのやり方がいまいち分かりません。
ご指摘いただいた、nが0であればnilを返すというのは0を返すでよろしいでしょうか。

何度も申し訳ありませんが、具体的にプログラムを書いて頂けると助かります。ご指導お願いします。

今まで考えたプログラム
fun ofunc(F,n,x)=
if n=0 then 0
else

回答No.1

salsberry

f^n(x)を求めるには、f^(n-1)(x)の結果を使うと再帰的に定義できます。

補足

ＭＬについては初心者なので具体的に教えて頂けますでしょうか。
説明されている意味はなんとなく理解できるのですが、
どのようなパターンのときに実行したらいいか分かりません。
よろしくお願いします。