如何用Haskell中的列表作爲參數或返回值來記憶函數？

我正在實現一個具有以下簽名的函數來解決Haskell中的0-1揹包問題。如何用Haskell中的列表作爲參數或返回值來記憶函數？

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

凡Item和Capacity文件被定義爲：

type Value = Int 
type Weight = Int 

type Capacity = Int 

type Item = (Value, Weight)

我想memoize的它有更好的性能。我試圖使用Data.MemoCombinators，但我不知道如何讓它工作。

你能給我一些提示？

來源

2012-12-29 mariosangiorgio

你可以發佈你的'Item'和'Capacity'類型嗎？這是爲他們定義記憶功能所必需的。 –

當然，我只是編輯了我的問題。它們只是一對整數和一個整數 – mariosangiorgio

我成功的使用了MemoTrie這樣的任務。您要用作記憶索引的每種類型必須實現HasTrie。在你的情況下，你不需要執行任何操作，因爲程序包已經爲基本數據類型以及對和列表提供了實例。

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

來源

2012-12-29 21:25:44

如果你正在尋找一個列表上的操作的性能優化，我建議你去看看在嚴格的迭代功能，例如Data.List.foldl'：

與foldl」 ::（甲 - >乙 - > a） - > a - > [b] - > a

來源

2012-12-29 21:11:22

如何用Haskell中的列表作爲參數或返回值來記憶函數？

回答

相關問題