Memo'd generator function

[fabiancook]

With return types of generator functions returning an iterable (An object with Symbol.iterator or Symbol.asyncIterator) that can only be iterated through once, I am wondering how these functions would be handled for memoization.

My first instinct is to just put a big flag over the top of usage, and just mention that they probably shouldn't be used with generators unless you know what you're up to, e.g. it is actually useful if the reader copies the result somewhere else, and just uses the returned generator as a key to their own cache.

---

For any function I would expect it would work like:

let index = -1;

function id() {
    index += 1;
    return { index }; // object reference will be different every return
}

const oneId = id.memo();

const a = oneId(),
    b = oneId();

console.log({ a, b });

if (a !== b) {
   throw new Error("Expected returned values to have the same object reference");
}

Given that, I would expect the returned object from a generator function to be the same reference each time.

function *generator() {
   yield id();
    yield id();
}

const generatorMemo = generator.memo();

const generatorMemoReturnA = generatorMemo(),
  generatorMemoReturnB = generatorMemo();
  
if (generatorMemoReturnA !== generatorMemoReturnB) {
   throw new Error("Expected returned values to have the same object reference");
}

If I called the generator function twice, and spread the returned iterable into arrays, I get the same length arrays:

const aArray = [...generator()],
    bArray = [...generator()];

console.log({ aArray, bArray });

if (aArray.length !== bArray.length) {
   throw new Error("Expected arrays to have the same length");
}

But, then doing this with the memo'd version, you get a possibly unexpected (but explainable) result:

const generatorMemo = generator.memo();

const aArrayMemo = [...generatorMemo()],
    bArrayMemo = [...generatorMemo()];

console.log({ aArrayMemo, bArrayMemo });

if (aArrayMemo.length !== bArrayMemo.length) {
   throw new Error("Expected arrays to have the same length");
}

If we are aware of this, and instead use the returned object as a key to another cache, we can achieve what we are actually after:

const toArray = (function (iterable) {
   return [...iterable];
}).memo();

const aArray = toArray(generator()),
    bArray = toArray(generator());

console.log({ aArray, bArray });

if (aArray.length !== bArray.length) {
   throw new Error("Expected arrays to have the same length");
}

const generatorMemo = generator.memo();

const aArrayMemo = toArray(generatorMemo()),
    bArrayMemo = toArray(generatorMemo());

console.log({ aArrayMemo, bArrayMemo });

if (aArrayMemo.length !== bArrayMemo.length) {
   throw new Error("Expected arrays to have the same length");
}

---

Given the naive implementation:

Function.prototype.memo = function () {
   const that = this;
    const cache = new Map();

    function findKey(args) {
       for (const key of cache.keys()) {
          if (key.length !== args.length) continue;
           const match = key.every((value, index) => args[index] === value);
           if (match) return key;
       }
        return undefined;
    }
    
    return function (...args) {
      const key = findKey(args) ?? args;
        const existing = cache.get(key);
        if (existing) return existing;
        const result = that.call(this, ...args);
        cache.set(key, result);
        return result;
   }
}

---

This becomes more of a complex problem once you start to talk about async generators

Then, how does .memo() mix with https://github.com/tc39/proposal-iterator-helpers

Proposed helpers:

generator()
   .map(value => value * 2)
   .filter(value => value > 3)
   .next();

memo & call:

generator
   .memo()
   .call()
   .map(value => value * 2)
   .filter(value => value > 3)
   .next();

Or maybe it should be a helper itself in the case of all generator functions, which maybe would just answer this entire issue and push it into a helper land problem for generator functions.

generator()
   .memo()
   .map(value => value * 2)
   .filter(value => value > 3)
   .next()

[js-choi]

Thank you for opening this issue!

What we should do with generator functions and async-generator functions depends on:

1. #7: Is there any prior art in which developers of any programming language applied (generator-)function memoization to a generator function?
2. #9: What are the specific use cases of (generator-)function memoization for developers?

As you know, generator functions return new stateful objects. To my current knowledge, function memoization is almost exclusively used on pure functions, which generator functions of course are not. I predict that we will not be able to find any prior art of generator-function memoization for #7.

So—assuming that we will not be able to find any prior art of generator memoization for #7—and assuming that we will not be able to think of any compelling specific developer use cases of generator-function memoization for #9—then we might conclude that generator-function memoization is just not something we want to support.

In fact, we might consider making the memo function throw a TypeError when a generator or async-generator function is given. However, I do not think this is a good idea. TC39 has always tried to treat generator functions and functions-that-return-generator-like-objects as functionally identical.

Barring any unforeseen compelling use cases, it’s probably best to just not treat generator functions as a special case.

[zloirock]

I'd expect returning of one cached generator and the absence of any special behavior here.

[fabiancook]

I have prior art for memo of asyncIterator based objects, I'll post some more about it in this issue later on today.

The summary of it though is that the more you look into it, the more complex it gets.

The iterator objects are closer to communication tunnels rather than a static set of information.

Because the communication is two way too, it really depends how far you want to go, e.g are yielded values returned only if the values passed to next are in the exact same order, if anything is different you might want a new source, but you might not know that till half way through the iteration, so you can just say instead to just cache everything once and ignore those values completely.

Here is a link to some code that's testing that the "memo'd" async iterables are working the way I had expected.

https://github.com/virtualstate/promise/blob/755eca0dbe34e3b0e8e7e0faf985c45d9177249f/src/tests/blend.ts#L239

[fabiancook]

My immediate thoughts is just to ignore all this and just return the memod generator object though. As with earlier comments.

Anywhere where memod async generators are used, the consumer will need to be aware of this pattern and be aware that they need to decide on their own caching pattern

[fabiancook]

This implementation here is equivalent to the memo in the original description of this issue

https://github.com/virtualstate/memo/blob/3d5d259cdede930a2c9b54fda75be28fac756c96/src/memo.ts#L12-L40

It now includes though async iterable memo as well though.

It only takes into account the values that were yielded once.

Using this code I could now do

Function.prototype.memo = function() {
  return createMemoFn(this)
}