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