How can I memoize a function with lists as parameters or return values in Haskell?

Question

I am implementing a function with the following signature to solve the 0-1 knapsack problem in Haskell.

knapsack :: [Item] -> Capacity -> [Item]

Where the Item and Capacity files are defined as:

type Value = Int
type Weight = Int

type Capacity = Int

type Item = (Value, Weight)

I'd like to memoize it to have better performances. I tried to use Data.MemoCombinators but I can't get how to have it work.

Can you give me some hints?

Answer 1

I successfully used MemoTrie for tasks like this. Each type that you want to use as a memoization index must implement HasTrie. In your case, you don't have to imlement anything, because the package already provides instances for the primitive data types as well as for pairs and lists.

import Data.MemoTrie

type Value = Int
type Weight = Int

type Capacity = Int

type Item = (Value, Weight)

knapsack :: [Item] -> Capacity -> [Item]
knapsack = memo2 knapsack'
  where
    knapsack' items capacity = ... -- your computation goes here

Answer 2

If you're looking for performance optimization for operations on lists, I'd suggest to take a look at the strict iteration functions, for example Data.List.foldl':

foldl' :: (a -> b -> a) -> a -> [b] -> a