「式 xs ++ ys を評価するための簡約の回数が、リスト xs と ys が完全に評価されていると仮定できるなら、xs の長さよりも一つ大きい数であることを示すことは簡単である。そのため、演算子 ++ の効率は、一番目の引数の長さに比例する。このため、長さが ｎ のリスト xs に対し、式 reverse xs にかかる簡約の回数は、1 から n + 1 までの整数の和、すなわち (n + 1)(n + 2) / 2 である」
という説明がよく理解できません。なぜ reverse xs の簡約の回数が 1 から n + 1 までの整数の和になるのでしょうか？
ちなみに reverse の定義は
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
を使っています。
2
コメント（1件)
Ａ．xs ++ ys を評価するための簡約の回数が、xsの長さよりも一つ大きい数であることを示す．
【定義】++ : 二つのリストを連結する [B.9 関数 P285 より]
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
【検証】例として，[1,2,3] ++ [4,5] の簡約が 3+1(回) であることを確認する．
[1,2,3] ++ [4,5]
= { ++を適用 }
1 : ([2,3] ++ [4,5])
= { ++を適用 }
1 : 2 : ([3] ++ [4,5])
= { ++を適用 }
1 : 2 : 3 : ([] ++ [4,5])
= { ++を適用 }
1 : 2 : 3 : [4,5]
= { リスト表記 }
[1,2,3,4,5]
Ｂ．reverse xs にかかる簡約の回数は、1からn+1までの整数の和、すなわち (n+1)(n+2)/2 です.
【定義】
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
【検証】例として，reverse [1,2,3] の簡約が 10 (=(3+1)(3+2)/2) (回) であることを確認する．
reverse [1,2,3] = reverse [2,3] ++ [1] = reverse [2,3] ++ 1:[] ･･･ ①
↓↑
reverse [2,3] = reverse [3] ++ [2] = reverse [3] ++ 2:[] ･･･ ②
↓↑
reverse [3] = reverse [] ++ [3] = [] ++ 3:[] ･･･ ③
↓↑
reverse [] = [] ･･･ ④
① ここでは，reverse [2,3] の評価後だけを考える．それを Ａ．の xs と見れば，簡約数は
2+1 となるが，Ａ．の ys に該当するリスト [1] が新規のリストであるから 1:[] の適用
を考慮して，結果，簡約数は 2+1+1 = 4 となる．
② ここでは，reverse [3] の評価後だけを考える．それを Ａ．の xs と見れば，簡約数は
1+1 となるが，Ａ．の ys に該当するリスト [2] が新規のリストであるから 2:[] の適用
を考慮して，結果，簡約数は 1+1+1 = 3 となる．
③ ここでは，reverse [] の評価後だけを考える．それを Ａ．の xs とすれば簡約数は
0+1となるが，Ａ．の ys に該当するリスト [3] が新規のリストであるから 3:[] の適用
を考慮して，結果，簡約数は 0+1+1 = 2 となる．
④ ここでは，reverse [] の評価を考える．簡約数は 1．