例如,假设这是我的函数:
let fib = n => {
switch (n) {
case 0: return 0
case 1: return 1
default: return fib(n - 1) + fib(n - 2)
}
}
然后我可以实现一个基本的内存功能...
let memoize = fn => {
let cache = new Map // mutates!
return _ => {
if (!cache.has(_)) {
cache.set(_, fn(_))
}
return cache.get(_)
}
}
...并用它来实现一个内存的 fib:
let fib2 = memoize(n => {
switch (n) {
case 0: return 0
case 1: return 1
default: return fib2(n - 1) + fib2(n - 2)
}
})
但是,memoize
函数在内部使用可变状态。我可以将 memoize
重新实现为一个 monad,所以每次我们调用 fib
时,它都会返回一个 [value, fib] 的元组,其中 fib
现在有一些东西在缓存中,保留原始 fib
未修改。
monad 方法的缺点是它不是惯用的 JavaScript,如果没有静态类型系统就很难使用。
有没有其他方法可以在不求助于 monad 的情况下实现避免突变的 memoize
函数?
最佳答案
首先,即使在按照所有合理标准“纯”的 Haskell 中,thunk 也会在评估后被它们的结果在内部覆盖——阅读 graph reduction .这是纯度和效率之间的权衡,但是它向用户隐藏了杂质,从而使其成为实现细节。
但是你的问题的答案是肯定的。考虑一下您在纯命令式设置中会做什么:动态编程。您会考虑如何将函数构造为表查找,然后自下而上构建该表。现在,许多人应用它的是,这只是在构建一个记忆化的递归函数。
你可以扭转这个原则,在函数式语言中使用“自下而上的表技巧”来获得内存递归函数,只需以纯粹的方式构建查找表:
fib n = fibs !! n
where fibs = 0:1:zipWith (+) fibs (tail fibs)
翻译成懒惰的伪-JS:
let fibs = [0, 1, Array.zipWith((a, b) => a + b, fibs, fibs.tail)...]
let fib = (n) => fibs[n]
在 Haskell 中这是默认工作的,因为它是惰性的。在 JavaScript 中,您可能可以通过使用惰性流来做类似的事情。比较以下 Scala 变体:
def fibonacci(n: Int): Stream[Int] = {
lazy val fib: Stream[Int] = 0 #:: fib.scan(1)(_+_)
fib.take(n)
}
(scan
类似于 reduce
,但保留中间累积;#::
是流的缺点;以及 lazy val
value 本质上是一个 memoizing thunk。)
有关图缩减情况下 fib
实现的进一步思考,请参阅 How is this fibonacci-function memoized? .
关于javascript - 如何编写 100% 纯记忆化功能?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44325234/