不可变记忆化 - 是否可能？

Question

不可变记忆化 - 是否可能？

4

我试图尽可能让我的前端技术栈保持功能纯粹和不可变，这对于这个项目有很大的好处。

据说所有可以以可变方式实现的算法都可以以不可变方式实现，那么在javascript中，如何实现一个不可变的函数memoizer？因为为了通过函数的不同路径返回，函数内部或外部的某些状态必须更改。

使用以下函数，你如何在javascript中实现不可变的记忆化？

function once(fn){
  let returnValue;
  let canRun = true;
  return function runOnce(){
      if(canRun) {
          returnValue = fn.apply(this, arguments);
          canRun = false;
      }
      return returnValue;
  }
}
var processonce = once(process);
processonce(); //process
processonce(); //

- Shanon Jackson

2

备忘录技术本质上依赖于状态，无法移除。在最佳情况下，您可以通过显式地传递状态使其“纯函数化”。状态将成为不可变的数据结构，但每次调用后都会有一个不同的状态。 - zch

2个回答

0

我提出了一种不同的IO方法，使用生成器，我们可以说它是纯粹的吗？

function* _cache() {
    const value = yield null
    while (true) yield value
}

const cache = _cache()

const heavyComputation = i => {
        console.log(`uh oh that's some heavy computations here`)
        return i++
}

cache.next().value
cache.next(heavyComputation(1))
cache.next().value
cache.next().value

然后您可以在运行时使用它来缓存值

function* _cache() {
    const value = yield null
    while (true) yield value
}

const cache = _cache()
const loadMongo = uri => void console.log(`fully loaded ${uri}`)

function end(loadedMongo) {
    console.log('handler called')
}

function handler() {
    const mongoUri = 'salutos speculos'
    const loaded = cache.next().value
    if (loaded === null) {
        cache.next(loadMongo(mongoUri))
        end(cache.next().value)
    } else end(loaded)
}

handler()
handler()
handler()
handler()
handler()

- Sceat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Black Akula · Accepted Answer

我也对这个问题很好奇。我同意@zch的观点-传递不可变状态会起作用(初始调用将使用空状态初始化递归)。

因此，我通过实现斐波那契函数来完成我的作业：记住，我们至少需要两次斐波那契函数来计算n-1和n-2。当我们调用fib(n-2)时，它已经被记忆化了。

这是我的实现：

const resultCombination = cache => result => (getResult = true) => getResult ? result : cache
const cacheResult = ({resultCombination}) => result => n => resultCombination({...result(false), [n]: result()})(result())

const memoize = ({resultCombination, cacheResult}) => cache => f => n => cache.hasOwnProperty(n)
    ? resultCombination(cache)(cache[n])
    : cacheResult({resultCombination})(f(cache)(n))(n)

const fib2 = ({resultCombination, cacheResult, memoize}) => f1Result => f => n => resultCombination(f1Result(false))(f1Result() + memoize({resultCombination, cacheResult})(f1Result(false))(f)(n - 2)())

const fib = ({resultCombination, cacheResult, memoize, fib2}) => cache => n => n === 1 || n === 2
    ? resultCombination(cache)(1)
    : fib2({resultCombination, cacheResult, memoize})(memoize({resultCombination, cacheResult})(cache)(fib({resultCombination, cacheResult, memoize, fib2}))(n - 1))(fib({resultCombination, cacheResult, memoize, fib2}))(n)


console.log('THE RESULT: ' + fib({
    resultCombination,
    cacheResult: ({resultCombination}) => result => n => {
        console.log(`Caching result: f(${n})=${result()}`)
        return cacheResult({resultCombination})(result)(n)
    },
    memoize: ({resultCombination, cacheResult}) => cache => f => n => {
        console.log(cache.hasOwnProperty(n) ? `Cache hit for n=${n}` : `Calculating value for f(${n})`)
        return memoize({resultCombination, cacheResult})(cache)(f)(n)
    },
    fib2
})({})(8)(true))

// Calculating value for f(7)
// Calculating value for f(6)
// Calculating value for f(5)
// Calculating value for f(4)
// Calculating value for f(3)
// Calculating value for f(2)
// Caching result: f(2)=1
// Calculating value for f(1)
// Caching result: f(1)=1
// Caching result: f(3)=2
// Cache hit for n=2
// Caching result: f(4)=3
// Cache hit for n=3
// Caching result: f(5)=5
// Cache hit for n=4
// Caching result: f(6)=8
// Cache hit for n=5
// Caching result: f(7)=13
// Cache hit for n=6
// THE RESULT: 21

为了更好地理解正在发生的事情，cacheResult和memoize函数被注入了日志包装器。如您所见，所有函数都是纯函数，仅接受一个参数（除了依赖注入）。

请注意，resultCombination(cache)(result)只是替换{cache, result}数据结构。

附言：我不是Haskell迷（甚至根本不知道Haskell或Lisp语法），但我热衷于函数式编程。