有什么阻止优化尾递归？

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

代码中是否有任何东西阻止编译器生成尾递归的优化代码？

代码 数据

-

Answer 1

这是一个严格的问题.要在通话generate中

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

实际上并没有强制向量进入内存.

您可以通过严格的应用程序import Control.DeepSeq替换:$$!!

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

或者您可以使用未装箱的矢量(可能更快),通过将导入语句更改为

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

(并保留原始程序中的所有其他内容).