haskell - Data.Memocombinators 无法捕获存在额外变量的情况

Question

考虑下面的两个函数。已包含 traceShow 以显示 DP 缓存命中或未命中。第一个是从 MemoCombinators documentation 挖来的。第二个是我自己构建的。

import Data.MemoCombinators as Memo
import Debug.Trace

fib :: Int -> Int
fib = Memo.integral fib'
    where
        fib' :: Int -> Int
        fib' 0 = traceShow 0 $ 0
        fib' 1 = traceShow 1 $ 1
        fib' n = traceShow n $ fib (n-1) + fib (n-2)    

brokenFib :: a -> Int -> Int
brokenFib a = Memo.integral brokenFib'
    where
        brokenFib' :: Int -> Int
        brokenFib' 0 = traceShow 0 $ 0
        brokenFib' 1 = traceShow 1 $ 1
        brokenFib' n = traceShow n $ brokenFib [] (n-1) + brokenFib [] (n-2)

fib 利用了 DP，但 brokenFib 没有，这意味着额外的变量一定以某种方式搞乱了它。构造一个场景并不难，您只想 DP 两个参数函数的参数之一，但如果不找出额外的变量如何与 BrokenFib 混淆，就无法完成此操作。有什么建议吗？

编辑:

@user6655594给出的第二种解决方案的实现:

brokenFib :: a -> Int -> Int
brokenFib = Memo.memoSecond Memo.integral brokenFib'
    where
        brokenFib' :: a -> Int -> Int
        brokenFib' _ 1 = traceShow 1 $ 1
        brokenFib' _ 2 = traceShow 1 $ 1
        brokenFib' _ n = traceShow n $ (brokenFib [] (n-1)) + brokenFib [] (n-2)

它也没有捕获 DP，尽管文档(“内存函数的第二个参数”)表明它应该捕获 DP。

Answer 1

不同之处在于，fib 是一个不会更改的值 - 它是一个内存函数，并且内存值在调用之间共享。

另一方面，brokenFib 是一个函数，它为每次调用 a 类型的值创建一个新的内存函数，该函数不与其他。

您有多种选择(我没有测试其中任何一个，而且我对这个包也不太熟悉):

• 使用 memoSecond 来内存第二个参数，例如

  brokenFib = memoizeSecond integral brokenFib'
    ...
  

  尽管文档似乎没有描述如何处理第一个参数。

• 如果可能的话，使用 memo2 记住两个参数。

• 如果 a 类型的第一个参数在整个调用过程中都相同，则可以使用

  brokenFib a = go
    where
      go = integral go'
      go' = ... -- and calls 'go', not 'brokenFib' for recursive calls!