IFPH 3.1.4答え

gistfile1.txt

IFPH 3.1.4 m*nの評価に必要な評価ステップ数はいくつか．

ただし自然数及び加算，乗算は次の通り．
data Nat = Zero | Succ Nat
(+) :: Nat->Nat->Nat
m + Zero = m
m + Succ n = Succ (m+n)
(*) :: Nat->Nat->Nat
m * Zero = Zero
m * Succ n = (m*n)+m

答
m+nのコストをP(m, n)とすると
P(m, 0) = 1
P(m, n) = P(m, n-1) + 1
より関数P(m, n)はnに関する等差数列であり
P(m, n) = n+1
 
m*nのコストをM(m, n)とすると
M(m, 0) = 1
M(m, n) = M(m, n-1) + P({m*(n-1)の結果}, m) + 1
        = M(m, n-1) + m + 2
よりM(m, n)はnに関する等差数列であり
M(m, n) = (m+2)*n+1