Take the 2-minute tour ×

I'm solving a knapsack problem in Haskell using Dynamic Programing. My first attempt was to build a two-dimensional table. But the memory easily gets blown up when the input is large(e.g. a 100 * 3190802 table).

Knowing that any given row i only depends on the row (i - 1), I instead write a function in the hope to take the advantage of tail recursion:

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))
                           if w < w_i then no_i
                           else max no_i ok_i

As shown in the code, itbl calls itself recursively and no further computation is made on its return value. However, I still see memory grow relentlessly in top:

1214m  9878 root      20   0 424m 1028 S  40.8 85.6   0:16.80 ghc

Is there anything in the code that prevents the compiler to produce optimized code for tail recursion?

code data


share|improve this question
Out of curiosity, try to remove the $ operator from the itbl (i + 1) $ V.generate (k + 1) gen call so that it looks like so: itbl (i + 1) (V.generate (k + 1) gen). My guess is that the $ makes the call not be tail recursive. –  Marius Danila Jun 27 '13 at 14:57
Thanks you. But removing $ doesn't seem to help. The memory usage still keeps growing. –  cfchou Jun 27 '13 at 15:11
I'd guess this is a problem with laziness. Being tail recursive isn't enough (nor always desirable) in a lazy language. –  augustss Jun 27 '13 at 15:29
Try replacing the $ by $!. –  augustss Jun 27 '13 at 15:30
Thank you all for pointing the right way. Yes, it's about strictness. –  cfchou Jun 27 '13 at 15:47
add comment

1 Answer

up vote 20 down vote accepted

This is a strictness problem. The call to generate in


does not actually force the vector into memory.

You can either import Control.DeepSeq and replace $ by deeply strict application $!!:

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

or you can use an unboxed vector (which is probably faster) instead, by changing the import statements to

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

(and leaving everything else as in your original program).

share|improve this answer
Thank you, this indeed solves my problem! –  cfchou Jun 27 '13 at 15:46
add comment

Your Answer


