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

Question

我对以下 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时测试：nIter >= maxIter成功，不需要评估 delta.
我在 evalPol.vofs' 中得到 441 个条目是有道理的，因为我将该函数映射到列表 ss 上，并且该列表中有 441 个项目.

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

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

evalPol.delta 的条目数从 1 变为 2（参见上面的 #2。）对我来说很有意义，因为我已经设置了 maxIter = 2。但是，我没有预料到 evalPol.vofs' 的条目数量会激增。（我期望看到 882 个条目，每个允许的递归 441 个条目。）看起来 evalPol.vofs' 的条目数在 maxIter 中是 指数级的 。（我不知道这个，因为我没有让程序完成。）

如果我 "unroll" 这 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

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

Answer 1

我使用 vofs' 函数的矢量表示法解决了这个问题。这样做消除了之前执行的冗余计算。对于 2 递归 情况，我现在看到 882 次调用新的 vofs'，这正是我所期望的。也就是说，我希望 evalPol 的执行时间在 maxIter 中是线性并且使用 vofs' 的矢量表示，这就是我的意思我看到了。

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

Why am I getting an exponential number of calls into my sub-function?

recursion

lambda

haskell

exponential