Chat (Lingr.com)
Informaiton
Daily
Column
- MySQL日本語の旅(5/1)
- アクセス向上秘伝(5/9)
- 一風変ったHaskellλ門(6/13)
- SICP Answer Book (5/31) 問題3.26追加
Zope Solution
Extra
アーカイブ
OSS案内所
Site Info
関連リンク
- 2006-06-13
1.2. 手続とその生成するプロセス
Haskellプログラミングでは計算機の「動作」については考えないが普通です． それはどのような順番で計算しても計算結果に影響がないことを前提にプログ ラムするからです．また，HaskellはLazy評価を基本としていますので，実際 にどのような順序で計算が進むかをあらかじめ予想しそれを確認するのは容易 でありません．
1.2.1. 線型再帰と反復
Schemeの場合は
Consider the first process. The substitution model reveals a shape of expansion followed by contraction, indicated by the arrow in the figure. The expansion occurs as the process builds up a chain of deferred operations (in this case, a chain of multiplications). The contraction occurs as the operations are actually performed. This type of process, characterized by a chain of deferred operations, is called a recursive process. Carrying out this process requires that the interpreter keep track of the operations to be performed later on. In the computation of n!, the length of the chain of deferred multiplications, and hence the amount of information needed to keep track of it, grows linearly with n (is proportional to n), just like the number of steps. Such a process is called a linear recursive process.
By contrast, the second process does not grow and shrink. At each step, all we need to keep track of, for any n, are the current values of the variables product, counter, and max-count. We call this an iterative process. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate. In computing n!, the number of steps required grows linearly with n. Such a process is called a linear iterative process.
さて，Haskellの場合はどうでしょう．
factorialの定義(Schemeの再帰プロセス版に対応)
factorial :: Integer -> Integer factorial 1 = 1 factorial n = n * factorial (n-1)
factorial 6 の評価プロセス
factorial 6 6 * factorial (6 - 1) 6 * factorial 5 6 * (5 * factorial (5 - 1)) 6 * (5 * factorial 4) 6 * (5 * (4 * factorial (4 - 1))) 6 * (5 * (4 * factorial 3)) 6 * (5 * (4 * (3 * factorial (3 - 1)))) 6 * (5 * (4 * (3 * factorial 2))) 6 * (5 * (4 * (3 * (2 * factorial (2 - 1))))) 6 * (5 * (4 * (3 * (2 * factorial 1)))) 6 * (5 * (4 * (3 * (2 * 1)))) 6 * (5 * (4 * (3 * 2))) 6 * (5 * (4 * 6)) 6 * (5 * 24) 6 * 120 720
これはSICPにあるものとほとんど同じです．ところが，Schemeの反復プロセス 版に対応するものを見ると，
factorialの定義(Schemeの反復プロセス版に対応)
factorial n = factIter 1 1 n
factIter :: Integer -> Integer -> Integer -> Integer
factIter prod cnt mxcnt | cnt > mxcnt = prod
| otherwise = factIter (cnt * prod) (cnt + 1) mxcnt
factorial 6 の評価プロセス
factorial 6 factIter 1 1 6 factIter (1*1) (1+1) 6 factIter (1*1) 2 6 factIter (2*(1*1)) (2+1) 6 factIter (2*(1*1)) 3 6 factIter (3*(2*(1*1))) (3+1) 6 factIter (3*(2*(1*1))) 4 6 factIter (4*(3*(2*(1*1)))) (4+1) 6 factIter (4*(3*(2*(1*1)))) 5 6 factIter (5*(4*(3*(2*(1*1))))) (5+1) 6 factIter (5*(4*(3*(2*(1*1))))) 6 6 factIter (6*(5*(4*(3*(2*(1*1)))))) (6+1) 6 factIter (6*(5*(4*(3*(2*(1*1)))))) 7 6 (6*(5*(4*(3*(2*(1*1)))))) (6*(5*(4*(3*(2*1))))) (6*(5*(4*(3*2)))) (6*(5*(4*6))) (6*(5*24)) (6*120) 720
このようにHaskellでは遅延評価されるのでSchemeのように反復プロセスとい うわけにはいかない．Haskellでは必要になった時点でいつでも計算ができる ように処理系は計算列をつねに保持します．Haskellでは「再帰的プロセス」 「反復的プロセス」という呼び方は相応しくないので，このページでは，前者 をトップダウン再帰，後者をボトムアップ再帰と呼ぶことにします．
注意：この用語はここだけで通用する「おれ様」用語です．
コメントをどうぞ！
1.2.2. 木構造再帰
Fibonacci数は典型的な木構造再帰です．Haskellではほとんど数学的な定義と 同じ表現になります．
fib n | n == 0 = 0
| n == 1 = 1
| otherwise = fib (n-1) + fib (n-2)
末尾再帰形にすると
fib' n = fibIter 0 1 n
fibIter a b c | c == 0 = a
| otherwise = fibIter b (a+b) (c-1)
もちろん fib' の方が圧倒的にはやい． n = 30 くらいで十分差がつくはず．
例: 両替の計算
countChange :: Int -> Int countChange amount = cc amount 5 type Kinds = Int cc :: Int -> Kinds -> Int cc amount kinds | amount == 0 = 1 | amount < 0 || kinds == 0 = 0 | otherwise = cc amount (kinds-1) + cc (amount - denom1 kinds) kinds denom1 :: Kinds -> Int denom1 1 = 1 denom1 2 = 5 denom1 3 = 10 denom1 4 = 25 denom1 5 = 50
実行例
*Main> countChange 100 292
これを末尾再帰形にするのは自明ではありません．
コメントをどうぞ！
何をやりたいのかよくわからなくて、一時間くらい悩んでしまいました。 両替する方法が何通りあるかを計算するプログラムなんですね。
- 練習問題 1.11
- 練習問題 1.12
- 練習問題 1.13 (SICP Answer Book参照)
1.2.3. 増加の程度
Haskell は lazy なので 前述の factorial の例では，トップダウン再帰で もボトムアップ再帰でも，ステップ数の増加，スペースの 増加は，Θ(n) です．
コメントをどうぞ！
There is no comment.
1.2.4. べき乗
トップダウン再帰
expt b n | n == 0 = 1
| otherwise = b * expt b (n-1)
ボトムアップ再帰
expt' b n = exptIter 1 b n exptIter a b c | c == 0 = a exptIter a b c | otherwise = exptIter (a*b) b (c-1)
トップダウン再帰でもボトムアップ再帰でも必要なステップとスペースは ともにΘ(n)です．
exptIterの定義は，SICPの expt-iter の定義とは引数の順番が 違うことに注意してください．SICP の定義は，
(define (expt-iter b counter product)
(if (= counter 0)
proroduct
(expt-iter b
(- counter 1)
(* b product))))
Scheme の expt-iter は第一引数が基数，第二引数がカウンタ，第三引数が 蓄積された積でしたが，Haskell の exprIter では第一引数が蓄積された積， 第二引数が基数，第三引数がカウンタです．
計算の意味自体は同じですが，Haskell では蓄積変数を第一引数にすることが よくあります．このようにしておくと，expt' の定義は，
expt' = exptIter 1
と書くことができます．
高速版
exptFast b n | n == 0 = 1
| even n = square (exptFast b (n `div` 2))
| otherwise = b * exptFast b (n-1)
where sqaure x = x * x
コメントをどうぞ！
There is no comment.
1.2.5. 最大公約数
SICPでの定義をそのままだと
gcd x y = if y == 0 then x else gcd y (rem x y)
Prelude での定義は，
gcd :: Integeral a => a -> a -> a
gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined"
gcd x y = gcd' (abs x) (abs y)
where gcd' x 0 = x
gcd' x y = gcd' y (x `rem` y)
コメントをどうぞ！
There is no comment.
There is no comment.