首页 文章

如何编写100％纯memoize函数？

提问于
浏览 次
3

例如，说这是我的功能：

let fib = n => {
  switch (n) {
    case 0: return 0
    case 1: return 1
    default: return fib(n - 1) + fib(n - 2)
  }
}

然后我可以实现一个基本的memoize函数......

let memoize = fn => {
  let cache = new Map   // mutates!
  return _ => {
    if (!cache.has(_)) {
      cache.set(_, fn(_))
    }
    return cache.get(_)
  }
}

...并使用它来实现memoized 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？

javascript types functional-programming computer-science monads

1 回答

  • 3

    首先，即使在所有合理标准的Haskell中，在评估之后，thunk在内部被其结果覆盖 - 阅读graph reduction . 这是纯度和效率之间的权衡，但是它隐藏了用户的杂质，因此使其成为实施细节 .

    但你的问题的答案是肯定的 . 考虑一下你在纯粹的命令式设置中所做的事情：动态编程 . 您将考虑如何将函数构造为表查找，然后从下到上构建该表 . 现在，许多人应用这个是这只是 Build 一个memoized递归函数 .

    你可以改变原理，并在函数式语言中使用“自下而上的表技巧”来获得一个memoized递归函数，只需以纯粹的方式构建查找表：

    fib n = fibs !! n
  where fibs = 0:1:zipWith (+) fibs (tail fibs)

    翻译成懒惰的 pseudo -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 值本质上是一个记忆的thunk . ）

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

    回复于

相关问题