haskell - 如何在 Haskell 中以列表作为参数或返回值来记忆函数？

Question

我正在实现一个具有以下签名的函数来解决 Haskell 中的 0-1 背包问题。

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

其中Item和Capacity文件定义为：

type Value = Int
type Weight = Int

type Capacity = Int

type Item = (Value, Weight)

我想记住它以获得更好的性能。我尝试使用Data.MemoCombinators但我不知道如何让它工作。

你能给我一些提示吗？

Answer 1

我成功地将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

Answer 2

如果您正在寻找列表操作的性能优化，我建议您查看严格的迭代函数，例如Data.List.foldl'：

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