Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 439
mariosangiorgio Avatar asked Dec 29 '12 20:12

mariosangiorgio


2 Answers

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
like image 102
Petr Avatar answered Nov 15 '22 06:11

Petr


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

like image 24
Dmitry Bespalov Avatar answered Nov 15 '22 08:11

Dmitry Bespalov