haskell - 为什么我的子函数调用次数呈指数级增长？

问题描述

我对以下 Haskell 函数有疑问：

evalPol :: Float
        -> Float
        -> Integer
        -> Integer
        -> (s -> a -> [(s, [(Float, Float)])])
        -> (s -> a)
        -> [s]
        -> [((s -> Float), Float)]
        -> [((s -> Float), Float)]
evalPol eps gamma maxIter nIter gen pol ss vofss =
  if nIter >= maxIter || delta < eps
    then reverse ((vofs', delta) : vofss)
    else evalPol eps gamma maxIter (nIter + 1) gen pol ss ((vofs', delta) : vofss)
 where delta   = maximum [abs (vofs s - vofs' s) | s <- ss]
       vofs' s = actVal gamma gen vofs s (pol s)
       vofs    = (fst . P.head) vofss

如果我使用分析调用此函数maxIter = 1并运行分析，那么我会看到函数条目计数，这对我来说很有意义：

evalPol..............2
  evalPol.delta......1
    evalPol.vofs'..441

上面的函数条目计数对我来说很有意义，如下所示：

evalPol输入两次：
1. 一次，当从外面打电话时，和
2. 一次，递归。（只允许一次递归调用，原因是：maxIter = 1.）
evalPol.delta只调用一次，因为当evalPol第二次（递归）调用时 test:nIter >= maxIter成功，并且不需要评估delta.
我得到 441 个条目是有道理的evalPol.vofs'，因为我将该函数映射到列表中ss，并且该列表中有 441 个项目。

现在，如果我只进行一项更改：调用evalPolwith maxIter = 2，我发现我的程序不会在合理的时间内终止。让它在中断之前运行几个小时，我得到以下信息：

evalPol................2
  evalPol.delta........2
    evalPol.vofs'..60366

将条目数evalPol.delta从 1 更改为 2（参见上面的 #2。）对我来说很有意义，因为我已经设置了maxIter = 2. 但是，我没想到evalPol.vofs'. （我期待看到 882 个条目，每个允许的递归有441个。）看起来条目evalPol.vofs'数在. （我不知道，因为我没有让程序完成。）maxIter

如果我“展开”这 2 个递归案例，寻找对的指数依赖maxIter，我得到：

-- This is how I call it from outside:
evalPol eps gamma 2 0 gen pol ss [((const 0), 0)] =                  -- Assume delta >= eps and recurse.
evalPol eps gamma 2 1 gen pol ss [(vofs', delta), ((const 0), 0)]

-- Now, expand delta
delta = maximum $ map (abs . uncurry (-) . (vofs &&& vofs')) ss      -- Substitute for vofs, vofs', and pol, using previous iteration's definitions.
      = maximum $ map ( abs
                      . uncurry (-)
                      . ( vofs' &&&
                          \s -> actVal gamma gen vofs' s 0
                        )
                      ) ss
      = maximum $ map ( abs
                      . uncurry (-)
                      . ( \s -> actVal gamma gen (const 0) s 0 &&&
                          \s -> actVal gamma gen (\s' -> actVal gamma gen (const 0) s' 0) s 0
                        )
                      ) ss

正如预期的那样，我看到递归正在发展，但我没有看到任何嵌套调用 into ，这可能解释了我观察到evalPol.vofs'的（假设）指数依赖性。maxIter此外，我已经查看了actVal函数gen和函数，并且没有evalPol.vofs'隐藏在其中任何一个中的调用。evalPol.vofs'因此，我无法解释我在maxIter = 2此案中观察到的大量条目。

标签： haskellrecursionlambdaexponential

haskell - 为什么我的子函数调用次数呈指数级增长？

问题描述

解决方案

推荐阅读