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?
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
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
ItemandCapacitytypes? This is necessary to define a memoization function for them.