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] 

If the Item and Capacity files are defined as:

 type Value = Int type Weight = Int type Capacity = Int type Item = (Value, Weight) 

I would like to remember it in order to have better results. I tried using Data.MemoCombinators , but I can't figure out how this works.

Can you give me some advice?

Answer 1

I have successfully used MemoTrie for such tasks. Each type that you want to use as a memoization index must implement HasTrie . In your case, you do not need to do anything, since the package already provides instances for 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 are looking for performance optimization for list operations, I would suggest Data.List.foldl' look at strict iterative functions like Data.List.foldl' :

foldl ':: (a → b → a) → a → [b] → a