How to implement memoization with "pure" Functional Programming in JavaScript

Question

In all the examples I can find on memoization / internal function cache in Functional Programming in JavaScript, the examples are either mutating or reassigning the cache.

Here's an example taken from https://scotch.io/tutorials/understanding-memoization-in-javascript#toc-a-functional-approach

function memoizer(fun){
    let cache = {}
    return function (n){
        if (cache[n] != undefined ) {
          return cache[n]
        } else {
          let result = fun(n)
          cache[n] = result
          return result
        }
    }
}

The only tiny improvement I can come up with is to use reassigning instead of mutating the cache object:

function memoizer(fun){
    let cache = {}
    return function (n){
        if (cache[n] != undefined ) {
          return cache[n]
        } else {
          let result = fun(n)
          cache = {... cache, [n]: result}
          return result
        }
    }
}

But my question is how to do this in a "pure" functional way, without mutations or reassigning a let/var?

Answer 1

With the definition of a "pure function" being:

\n

\n

In computer programming, a pure function is a function that has the\nfollowing properties:[1][2]

\n

Its return value is the same for the same arguments (no variation with\nlocal static variables, non-local variables, mutable reference\narguments or input streams from I/O devices).\nIts evaluation has no\nside effects (no mutation of local static variables, non-local\nvariables, mutable reference arguments or I/O streams).

\n

\n\n

I think we can see that what you have is a pure function, if the same values are passed to the function, you will always get the same result; there is nothing in that method that would be affected by any external state beyond it \xe2\x80\x93\xe2\x80\x93 that is unless the passed fun argument isn\'t pure, but that isn\'t an issue with your memoizer method itself.

\n

EDIT\nBecause the cache object is not a static variable, mutating it does not violate any of the rules of what makes a pure function pure.\nDefinition of "side effects" as used by Wikipedia in the explanation above:

\n

\n

在计算机科学中，如果一个操作、函数或表达式在本地环境之外修改了某些状态变量值，那么它就会产生副作用，也就是说，除了返回一个值（主要是效果）到操作的调用者。

\n

\n

Answer 2

这部分回答了如何以纯函数方式记忆所有类型函数的问题。该解决方案与您的命令式解决方案完全不同，并且代码尚未准备好用于生产，而只是概念证明。请注意，我也是这个主题的新手。

答案是部分的，因为我只想展示一个其域（参数）是整数的 memoize 函数。更高级的多态记忆函数可以处理各种参数类型以及递归函数。

基本思想是有一个对无限整数列表进行操作的函数。列表只有在不严格求值的情况下才可以是无限的，也就是说，仅在需要时才求值，并且仅在足够的情况下才求值。稍后我们会看到，非严格性对于记忆来说是不够的，我们需要适当的惰性评估。

在第一个示例中，我将使用显式的 thunk（例如，() => "do something"为了简单起见，形状的无效函数：

// INFINITE LIST

// we only mimick such a type

const iterate = f => {
  const go = x =>
    [x, () => go(f(x))];

  return go;
};

// Functor

const map = f => {
  const go = ([x, thunk]) =>
    [log(f(x)), () => go(thunk())];

  return go;
};

// element lookup

const lookup = ([x, thunk]) => i =>
  i === 0
    ? x
    : lookup(thunk()) (i - 1);

// memoization

const memoize = f =>
  lookup(
    map(f)
      (iterate(x => x + 1) (0)));

// auxiliary function

const log = x => (console.log(x), x);

const fib = n => {
  return n > 1
    ? fib(n - 1) + fib(n - 2)
    : n;
}

// MAIN

const foo = memoize(fib);

console.log("yields:", foo(6)); // logs 1, 1, 2, 3, 5, 8
console.log("yields:", foo(6)); // logs 1, 1, 2, 3, 5, 8

这适用于斐波那契数的无限序列并产生预期结果，但仍然没有记忆。目前，这只是一种从斐布那契数列计算位置的麻烦方法。

虽然这个算法是不严格的，但正如已经提到的，我们需要适当的惰性评估。惰性求值是指共享一次计算的 thunk 的非严格求值。我们可以使用ProxyJavascript 中的本机类型来模拟惰性求值。请注意，上面示例中的显式 thunk 现在已替换为隐式 thunk，即您不需要调用 ( thunk())，而只需将它们用作普通值即可。这是一个工作草图：

const NULL = "null";

const THUNK = "thunk";

const thunk = thunk =>
  new Proxy(thunk, new ThunkProxy());

class ThunkProxy {
  constructor() {
    this.memo = NULL;
  }

  apply(g, that, args) {
    if (this.memo === NULL) {
      this.memo = g();

      while (this.memo && this.memo[THUNK] === true)
        this.memo = this.memo.valueOf();
    }

    return this.memo(...args);
  }

  get(g, k) {
    if (k === THUNK)
      return true;

    else if (this.memo === NULL) {
      this.memo = g();
      
      while (this.memo && this.memo[THUNK] === true)
        this.memo = this.memo.valueOf();
    }

    if (k === "valueOf")
      return () => this.memo

    else if (k === "toString")
      return () => this.memo.toString();

    else if (k === Symbol.toStringTag)
      return Object.prototype.toString.call(this.memo).slice(8, -1);

    while (this.memo[k] && this.memo[k] [THUNK] === true)
      this.memo[k] = this.memo[k].valueOf();

    if (typeof this.memo[k] === "function")
      return this.memo[k].bind(this.memo);

    else return this.memo[k];
  }

  has(g, k) {
    if (k === THUNK)
      return true;

    else if (this.memo === NULL) {
      this.memo = g();

      while (this.memo && this.memo[THUNK] === true)
        this.memo = this.memo.valueOf();
    }

    return k in this.memo;
  }
}

const iterate = f => {
  const go = x =>
    [x, thunk(() => go(f(x)))];

  return go;
};

const lookup = ([head, tail]) => i =>
  i === 0
    ? head
    : lookup(tail) (i - 1);

const map = f => {
  const go = ([head, tail]) =>
    [log(f(head)), thunk(() => go(tail))];

  return go;
};

const memoize = f =>
  lookup(
    map(f)
      (iterate(x => x + 1) (0)));

const log = x => (console.log(x), x);

const fib = n => {
  return n > 1
    ? fib(n - 1) + fib(n - 2)
    : n;
}

const foo = memoize(fib);

console.log("yields:", foo(6)); // logs 0, 1, 1, 2, 3, 5, 8, "yields: 8"
console.log("yields:", foo(6)); // logs "yields: 8"
console.log("yields:", foo(10)); // logs 13, 21, 34, 55, "yields: 55"

最后我们达到了预期的记忆效果，但是我在 Javascript 中模仿惰性求值的方式也是不纯粹的——我只是在作弊。然而，在像 Haskell 这样的纯函数式语言中，惰性求值是该语言的实现细节，因此不是您实际使用的语法的一部分。这样语言本身就保持纯净。

请注意，这fib是一个递归函数，memoize不处理递归步骤，而仅处理中间结果和最终结果。