haskell - Haskell 中的短暂内存？

Question

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

创建新类(class)

为我要缓存的每个函数结果添加一个数据成员和一个方法

实现该方法首先检查结果是否已存储在数据成员中。如果是，则返回该值；否则调用函数(使用适当的参数)并将返回的结果存储在数据成员中。

此类的对象将使用各种函数调用所需的值进行初始化。

这种基于对象的方法与此处描述的基于函数的内存模式非常相似: 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”接受一个函数并生成它的memoized 版本。

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) 有点神奇。不要管那个;如果你有兴趣，你可以谷歌它。

所以让我们写一个 Memoizable经典 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 完美匹配.与其创建本质上成为内存管理器的对象，不如简单地按需创建内存函数。问题是如果你的函数是递归的，它必须写成 Memoizable .好消息是您可以插入任何 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