javascript - 如何编写 100% 纯内存功能？

例如，说这是我的功能:

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，并且在没有静态类型系统的情况下很难使用。

有没有其他方法可以实现 memoize 函数来避免突变，而无需求助于 monad？

最佳答案

首先，即使在按照所有合理标准都是“纯”的 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 值本质上是一个内存重击。)

进一步思考 fib 在存在图缩减的情况下的实现，请参阅 How is this fibonacci-function memoized? 。

关于javascript - 如何编写 100% 纯内存功能？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44325234/