Haskell 中的短暂记忆？

Question

在面向对象的语言中，当我需要在已知的生命周期内缓存/记忆函数的结果时，我通常会遵循以下模式：

1. 创建一个新类
2. 向该类添加数据成员和每个函数结果的方法我想在缓存中
3. 实现方法，首先检查结果是否已存储在数据成员中。如果是，则返回该值；否则调用该函数（使用适当的参数）并将返回的结果存储在数据成员中。
4. 此类的对象将使用各种函数调用所需的值进行初始化。

这种基于对象的方法与此处描述的基于函数的记忆模式非常相似：http://www.bardiak.com/2012/01/javascript-memoization-pattern.html

这种方法的主要好处是结果仅在缓存对象的生命周期内保留。一个常见的用例是处理工作项列表。对于每个工作项，创建该项的缓存对象，使用该缓存对象处理该工作项，然后在继续下一个工作项之前丢弃该工作项和缓存对象。

在 Haskell 中实现短期记忆的好方法是什么？答案是否取决于要缓存的函数是纯函数还是涉及 IO？

重申一下 - 很高兴看到涉及 IO 的功能的解决方案。

Answer 1

让我们使用 Luke Palmer 的记忆库：Data.MemoCombinators

import qualified Data.MemoCombinators as Memo
import Data.Function (fix) -- we'll need this too

我将定义与他的库的做法略有不同的东西，但它基本上是相同的（而且是兼容的）。一个“可记忆”的事物将其自身作为输入，并产生“真实”的事物。

type Memoizable a = a -> a

“memoizer”接受一个函数并生成它的记忆版本。

type Memoizer a b = (a -> b) -> a -> b

让我们编写一个小函数将这两件事放在一起。给定一个 Memoizable 函数和一个 Memoizer，我们需要生成的记忆函数。

runMemo :: Memoizer a b -> Memoizable (a -> b) -> a -> b
runMemo memo f = fix (f . memo)

这是使用定点组合器（fix）的一个小魔法。没关系；如果你有兴趣可以google一下。

因此，让我们编写一个经典 fib 示例的可记忆化版本：

fib :: Memoizable (Integer -> Integer)
fib self = go
  where go 0 = 1
        go 1 = 1
        go n = self (n-1) + self (n-2)

使用 self 约定使代码变得简单。请记住，self 是我们期望的该函数的记忆版本，因此递归调用应该在 self 上。现在启动 ghci。

ghci> let fib' = runMemo Memo.integral fib
ghci> fib' 10000
WALL OF NUMBERS CRANKED OUT RIDICULOUSLY FAST

现在，runMemo 的一个很酷的事情是，您可以创建同一函数的多个新记忆版本，并且它们不会共享内存库。这意味着我可以编写一个在本地创建和使用 fib' 的函数，但是一旦 fib' 超出范围（或更早，取决于编译器），它可以被垃圾收集。 它不必在顶层被记住。这可能会或可能不会与依赖于 unsafePerformIO 的记忆技术很好地配合。 Data.MemoCombinators 使用纯粹的惰性 Trie，它与 runMemo 完美契合。您可以根据需要简单地创建记忆函数，而不是创建本质上成为记忆管理器的对象。问题是，如果您的函数是递归的，则必须将其编写为可记忆化的。好消息是您可以插入任何您想要的 Memoizer。你甚至可以使用：

noMemo :: Memoizer a b
noMemo f = f

ghci> let fib' = runMemo noMemo fib
ghci> fib' 30 -- wait a while; it's computing stupidly
1346269

Answer 2

从某种程度上来说，Lazy-Haskell 编程是一种极端的记忆范式。此外，无论你在命令式语言中做什么，在 Haskell 中都是可能的，使用 IO monad、ST monad、monad 转换器、箭头，或者你能想到的任何东西。

唯一的问题是这些抽象设备比您提到的命令式等价物复杂得多，并且它们需要相当深入的思维重新布线。

Answer 3

我相信上述答案都比必要的更复杂，尽管它们可能比我将要描述的更容易移植。

据我了解，ghc 中有一条规则，即每个值在输入其封闭的 lambda 表达式时只计算一次。因此，您可以如下创建您的短期记忆对象。

import qualified Data.Vector as V
indexerVector :: (t -> Int) -> V.Vector t -> Int -> [t]
indexerVector idx vec = \e -> tbl ! e
  where m = maximum $ map idx $ V.toList vec
        tbl = V.accumulate (flip (:)) (V.replicate m []) 
                 (V.map (\v -> (idx v, v)) vec)

这是做什么的？它根据第一个参数 idx 计算的整数，对作为第二个参数 vec 传递的 Data.Vector t 中的所有元素进行分组，保留它们的值分组为 Data.Vector [t]。它返回一个 Int 类型的函数 -> [t] 通过此预先计算的索引值查找此分组。

我们的编译器 ghc 已承诺，当我们调用 indexerVector 时，tbl 只会被 thunked 一次。因此，我们可以指定 lambda 表达式 \e ->长话短说！ e 由 indexVector 返回到另一个值，我们可以重复使用该值，而不必担心 tbl 被重新计算。您可以通过在 tbl 上插入 trace 来验证这一点。

简而言之，您的缓存对象就是这个 lambda 表达式。

我发现几乎任何可以用短期对象完成的事情都可以通过返回这样的 lambda 表达式来更好地完成。

Answer 4

你也可以在 haskell 中使用相同的模式。惰性求值将负责检查值是否已经被求值。它已经被多次提及，但代码示例可能很有用。在下面的示例中，memoedValue 将仅在需要时计算一次。

data Memoed = Memoed
  { value       :: Int
  , memoedValue :: Int
  }

memo :: Int -> Memoed
memo i = Memoed
  { value       = i
  , memoedValue = expensiveComputation i
  }

更好的是，您可以记住依赖于其他已记忆值的值。您应该避免依赖循环。它们可以导致不终止

data Memoed = Memoed
  { value        :: Int
  , memoedValue1 :: Int
  , memoedValue2 :: Int
  }

memo :: Int -> Memoed
memo i = r
  where
  r = Memoed
    { value        = i
    , memoedValue1 = expensiveComputation i
    , memoedValue2 = anotherComputation (memoedValue1 r)
    }