Haskell中短暂的记忆？

Question

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

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

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

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

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

只是重申 - 看到涉及IO的功能的解决方案会很高兴.

Answer 1

让我们使用Luke Palmer的memoization库: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函数和a Memoizer,我们想要结果的memoized函数.

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

使用fixpoint combinator(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我们期望成为这个函数的memoized版本,因此应该进行递归调用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.您可以根据需要简单地创建memoized函数,而不是创建一个本质上成为memoization manager的对象.问题是如果你的函数是递归的,那么它必须写成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