在非整数键上有效地实现记忆

我是 Haskell 的新手，并且一直在通过做一些简单的编程挑战来练习。最近两天，我一直在尝试在这里实现无界背包问题。维基百科页面上描述了我使用的算法，但对于这个问题，“重量”一词被替换为“长度”一词。无论如何，我开始编写没有记忆的代码：

maxValue :: [(Int,Int)] -> Int -> Int
maxValue [] len = 0
maxValue ((l, val): other) len =
    if l > len then 
        skipValue
    else 
        max skipValue takeValue
    where skipValue = maxValue other len
          takeValue = (val + maxValue ([(l, val)] ++ other) (len - l)

我曾希望 haskell 会很好，并且有一些很好的语法#pragma memoize来帮助我，但是四处寻找示例，解决方案是用这个斐波那契问题代码解释的。

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

在掌握了这个例子背后的概念后，我感到非常失望——所使用的方法是超级hacky，只有在 1) 函数的输入是单个整数时才有效，并且 2) 函数需要按顺序递归计算值f(0), f(1), f(2), ... 但是如果我的参数是向量或集合怎么办？如果我想记住一个像 的函数，当我不需要大多数这些值时f(n) = f(n/2) + f(n/3)，我需要计算f(i)所有小于 n 的值。（其他人指出这种说法是错误的）

我尝试通过传递一个我们慢慢填充为额外参数的备忘录表来实现我想要的：

maxValue :: (Map.Map (Int, Int) Int) -> [(Int,Int)] -> Int -> (Map.Map (Int, Int) Int, Int)
maxValue m [] len = (m, 0)
maxValue m ((l, val) : other) len =
    if l > len then
        (mapWithSkip, skipValue)
    else
        (mapUnion, max skipValue (takeValue+val))
    where (skipMap, skipValue) = maxValue m other len
          mapWithSkip = Map.insertWith' max (1 + length other, len) skipValue skipMap
          (takeMap, takeValue) = maxValue m ([(l, val)] ++ other) (len - l)
          mapWithTake = Map.insertWith' max (1 + length other, len) (takeValue+val) mapWithSkip
          mapUnion = Map.union mapWithSkip mapWithTake

但这太慢了，我相信是因为Map.union 花费的时间太长，O(n+m)而不是O(min(n,m)). 此外，对于像 memoizaton 这样简单的东西，这段代码似乎很混乱。对于这个特定问题，您可能可以将 hacky 方法推广到 2 维，并进行一些额外的计算，但我想知道如何在更一般的意义上进行记忆。如何在保持与命令式语言中代码相同的复杂性的同时，以这种更通用的形式实现记忆化？

回答