17.4.26 別の形の繰り返し - その2

少し前に見た整数の和の計算でも, やはり別の形の繰り返しの定義ができます.

整数の和の計算では

• もし「0から(n-1)までの和」が x だとしたら，「0からn」までの和は x + n である．
• もし「0から0までの和」は0に決まっている!

と考えて「0からnまでの和」を次のような関数として定義しました.

let rec sum(n) =
  if n=0 then 0
  else (sum(n-1))+n

これを「0からkまでの和がsのときの0からnまでの和」(以降では sum_from(k,s,n) と書くことにします)を求めると考え直すと,

• sum_from(k,s,n) は 「0からk+1までの和がs+k+1のときの0からnまでの和」つまりsum_from(k+1,s+k+1,n)に等しい
• sum_from(n,s,n) は s に決まっている!

と考えて

let rec sum_from(k,s,n) =
  if k=n then s
  else sum_from(k+1,s+k+1,n)

のように定義することができます. 0から10までの和や, 4567までの和を求めるには sum_from(0, 0, 10) や sum_from(0, 0, 4567) という式になります.

この形の繰り返しは一見ややこしいのですが, 次のようなことに気付けば容易に理解できるでしょう.

• sum_from(k,s,n) は(k+1からnまでの和)にsを足した数, つまり (k+1)+(k+2)+...+n+sを求めている
• 従って sum_from(k,s,n) = (k+1)+(k+2)+...+n + s = ((k+1)+1)+...+n + (s+k+1) = sum_from(k+1,s+k+1,n) という定義は正しい.
• また k=0, s=0 のときには [0+1からnまでの和]に0を足した数, つまり1からnまでの和を求めている.

sum_fromを使って, 「0からnまでの和」を定義し直すと, 次のようになります.

let sum_alt(n) = sum_from(0,0,n)