置き換えモデル

置き換えモデルとは、どうやら出てくる関数を置き換えていって、最後に計算をするモデル。遅延評価といっていいのかな。

問題1.9では、引数を1増やす手続きincと引数を1減らす手続きdecをつかって、2つの整数をたす方法を置き換えモデルを使い、4と5をたす過程を示すというもの。とりあえず、関数が2つ定義されているんだけど、まずはそれをHaskellで実装

mplus x y
        |x == 0 = y
        |otherwise = 1 + ( mplus ( x - 1 ) y)
mplus' x y
        |x == 0 = y
        |otherwise = mplus' ( x -1 ) ( y + 1)

incとdecは普通の足し算・引き算で実装。
では、mplusと定義したほうから。

mplus 4 5
1 + mplus 3 5
1 + 1 + mplus 2 5
1 + 1 + 1 +  mplus 1 5
1 + 1 + 1 + 1 + mplus 0  5
1 + 1 + 1 + 1 + 5
1 + 1 + 1 + 6
1 + 1 + 7
1 + 8
9

この方法だと、再起終了後にいっきに計算される。
本では、このように遅延演算の列の長さがスッテプ数のようにnに比例して増加するプロ セスを線形再起的プロセスとよんでいる。
では、mplus'だとどうなるだろう？

mplus' 4 5
mplus' 3 6
mplus' 2 7
mplus' 1 8
mplus' 0 9
9

この場合だと、再起呼び出しをするたびに足されていく。
このようにステップ数がnに比例して増加するプロセスを線形反復的プロセスというらし い。