有什么因素会影响优化尾递归吗？

Question

我正在使用动态规划解决Haskell中的背包问题。我的第一次尝试是构建一个二维表。但是当输入很大时（例如100 * 3190802表），内存很容易耗尽。

由于任何给定行i只依赖于行(i-1)，因此我编写了一个函数，希望利用尾递归的优势：

import Data.Vector (Vector, (!))
import qualified Data.Vector as V

-- n items, k capacity, vs values, ws weights
ans:: Int -> Int -> Vector Int -> Vector Int -> Int
ans n k vs ws =
    let row = initRow k vs ws
    in  row ! k

initRow :: Int -> Vector Int -> Vector Int -> Vector Int
initRow k vs ws = itbl 1 $ V.replicate (k + 1) 0
    where n = V.length vs
          itbl i row
             | i > n = row
             | otherwise = itbl (i + 1) $ V.generate (k + 1) gen
             where gen w =
                       let w_i = ws ! (i - 1)
                           no_i = row ! w
                           ok_i = row ! (w - w_i) + (vs ! (i - 1))
                       in
                           if w < w_i then no_i
                           else max no_i ok_i

如代码所示，itbl 递归调用自身并且在其返回值上不再进行任何计算。然而，我仍然看到 top 中内存无休止地增长：

 VIRT   PID USER      PR  NI  RES  SHR S  %CPU %MEM    TIME+  COMMAND
1214m  9878 root      20   0 424m 1028 S  40.8 85.6   0:16.80 ghc

代码中是否存在任何内容，会防止编译器为尾递归生成优化代码？

代码和数据请参考以下链接： code data

- cfchou

---

出于好奇，试着从 itbl (i + 1) $ V.generate (k + 1) gen 的调用中移除 $ 运算符，使其看起来像这样：itbl (i + 1) (V.generate (k + 1) gen)。我猜测 $ 使得该调用不是尾递归。 - Marius Danila

感谢你。但是移除 $ 似乎没有起到作用。内存使用量仍在不断增长。 - cfchou

我猜这是懒惰问题。在懒惰的语言中，仅仅具备尾递归性质是不够的（也不总是可取的）。 - augustss

尝试将“$”替换为“$！” - augustss

谢谢大家指出正确的方向。是的，这与严格性有关。 - cfchou

Answer 1

这是一个严格性问题。在generate的调用中

             | otherwise = itbl (i + 1) $ V.generate (k + 1) gen

这实际上并不强制将向量加载到内存中。

您可以导入Control.DeepSeq并用深度严格应用程序$!!替换$：

             | otherwise = itbl (i + 1) $!! V.generate (k + 1) gen

或者您可以使用未装箱的向量（可能更快），只需将导入语句更改为

import Data.Vector.Unboxed (Vector, (!))
import qualified Data.Vector.Unboxed as V

(并且保留你原始程序中的其它所有内容)。

- kosmikus