Haskell 中的部分记忆

Question

我试图找到一种好方法，使用 Data.MemoCombinators 来记住 Haskell 中函数的部分域（非负整数）。

import Data.MemoCombinators

--approach 1

partFib n | n < 0 = undefined
          | otherwise = integral fib n where
  fib 0 = 1
  fib 1 = 1
  fib k = partFib (k-1) + partFib (k-2)

--approach 2

partFib2 n | n < 0 = undefined
           | otherwise = fib n
fib = integral fib'
  where
    fib' 0 = 1
    fib' 1 = 1
    fib' n = partFib2 (n-1) + partFib2 (n-2)

方法1是我想要的方法，但是它似乎不起作用。我认为这是因为每次调用 partFib 时都会“重新创建”fib 函数，从而丢弃了记忆。 fib 不依赖于 partFib 的输入，因此您会假设编译器可以提升它，但显然 GHC 不能那样工作。

方法2是我最终的做法。哎呀，很多丑陋的接线。

有谁知道更好的方法来做到这一点？

Answer 1

不太确定什么对你来说“丑陋”，但是通过将记忆操作从 n 的函数中提升出来，你可以在仅使用单个顶级标识符的情况下进行适当的记忆。

partFib3 = \n -> if n < 0 then undefined else fib' n
    where fib 0 = 1
          fib 1 = 1
          fib k = partFib3 (k-1) + partFib3 (k-2)
          fib' = integral fib

Answer 2

嗯，稍微分开一下怎么样：

fib 0 = 0
fib 1 = 1
fib x = doFib (x-1) + doFib (x-2)

memFib = Memo.integral fib

doFib n | n < 0 = fib n
        | otherwise memFib n

现在您需要使用 doFib。

Answer 3

库中有一个用于此目的的组合器：

switch :: (a -> Bool) ->备注一->备注一->备忘录一  

switch pa b 每当 p 给出 true 时使用备忘录表 a ，每当 p 给出 true 时使用备忘录表 b code>p 给出 false。

回想一下，id 从技术上讲是一个记忆器（它不会记忆:-)，所以你可以这样做：

partFib = Memo.switch (< 0) id Memo.integral fib'
    where
    ...