4

この関数と末尾再帰は理解できますが、厳密な評価が重要な理由がわかりません。厳密な評価がなければ、まだ末尾再帰になりますよね? では、厳密な評価なしでこの関数が失敗するのはいつでしょうか?

turboPower a b = turboPower' 1 a b
  where
    turboPower' x a 0 = x
    turboPower' x a b
        | x `seq` a `seq` b `seq` False = undefined
        | even b = turboPower' x (a*a) (b `div` 2)
        | otherwise = turboPower' (x*a) a (b-1)
4

1 に答える 1

5

失敗することはありません（指数が大きい場合を除いて、サンクがスタックをオーバーフローするのに十分な大きさになる可能性があります）、厳密な評価がないと引数がサンクになり、

turboPower' (let xN = let x(N-1) = ...; a(N-1) = ... in x(N-1)*a(N-1)) (let aN = let a(N-1) = ... in a(N-1)*a(n-1)) (let bN = ...)

ネストのレベルは指数の対数であり、したがってすべての実際の計算では小さいままであるため、ここではそれほど劇的ではないはずですが、たとえば、

foo :: Integer -> Integer
foo n = go 0 n
  where
    go acc m
      | m < 1     = acc
      | otherwise = go (acc + m^3 + m `mod` 7) (m-1)

ここで、ネストのレベルはで線形ですn。

于 2012-10-05T10:47:52.637 に答える