Memoize function passes function and returns function JavaScript

Question

I am having multiple problems with this function. It's part of a bonus question for a Data Structures and Algorithms class and I've invested so much time in this one problem, that I'd really like to get it to work and understand what's going on.

There is one main problem, which has caused several little ones...this problem's name is JavaScript. We've never programmed in JavaScript before, but for some reason we have to use it.

The function has to pass tests (this one and fibonacci), which are structured like this:

var fn = (n) => 2 * n
var m_fn = memoize(fn)
expect(m_fn(18)).to.equal(fn(18))

So I have to pass the function I want to memoize as a parameter of the memoize function and the memoize function has to return a function. I am not allowed to do it any other way.

I did all of the reading and researched the memoize function, but all of the implementations take a different approach.

Basically, I understand what I have to do, but I don't quite understand HOW. I know what the memoize function should do, but I don't understand how to adjust the original function using my memoize function. This is what I have so far/what I don't have:

I know it's wrong. But I think I'm missing something major. I am supposed to return a function, but I am returning values...

In the test, it's writen var m_fn = memoize(fn), so the memoize function passes fn, then returns a new function, but in my memoize, I am returning values for fn(n), so I AM doing something wrong...

/**
* Creates a memoized version of the function fn. It is assumed that fn is a referentially transparent
* function.
* @param {function} fn Some referentially transparent function that takes a basic datatype (i.e. number / string)
* @returns {function} A new function that is the memoized version of fn. It never calculates the result of
* a function twice.
*/
memoize: (fn) => { //here we enter the function that we want to memoize
 var memory = []; //we need to create an array to hold the previously calculated values, length n (parameter of fn)

 if(this.n > memory.length){ //Check to see if this particular value is in the array already.  
   return memory[this.n]; //How do I access the integer parameter that was passed through fn though? Is this correct?
 } else{ // if not, we want to save it and return it
   var result = fn(this.n);
   memory.push(result);
   return result;
 } 

}

Answer 1

You could use a Map as memory.

var memoize = f => 
        (map => v => (!map.has(v) && map.set(v, f(v)), map.get(v)))(new Map),
    fn = (n) => 2 * n,
    m_fn = memoize(fn);

console.log(m_fn(18), fn(18));

Answer 2

Looking at your code and in-code comments and assuming I'm interpreting correctly, you're really close to the solution. As you've said in the question, you need to return a function that returns the values rather than returning the values.

See comments for explanation:

function memoize(f) {
  // An array in which to remember objects with the input arg and result 
  var memory = [];
  
  // This is the function that will use that array; this is the
  // return value of memoize
  return function(arg) {
    // This code runs when the function returned by memoize is called
    // It's *here* that we want to process the argument, check the `memory`
    // array, call `f` if necessary, etc.
    var entry;
    
    // See if we have a previously-saved result for `arg`
    var entry = memory.find(entry => entry.arg === arg);
    if (!entry) {
      // No -- call `fn`, remember the `arg` and result in an object
      // we store in memory``
      entry = {arg, result: f(arg)};
      memory.push(entry);
    }
    
    // We have it (now), return the result
    return entry.result;
  };
}
function fn(arg) {
  console.log("fn called with " + arg);
  return 2 * arg;
}
var m_fn = memoize(fn);
console.log(m_fn(18));
console.log(m_fn(18));
console.log(m_fn(20));
console.log(m_fn(20));

Note: There was an arrow function in your code, so I've assumed it's okay to use ES2015 features above. There's not actually very much of it, though, just the arrow function passed to memory.find, the assumption that Array#find will be available, and the syntax used to create the entry object (in ES5 we' need entry = {arg: arg, result: f(arg)} instead).

Note that if we can assume that arg will be a string or number or other value that can reliably be converted to string, we can use an object to store the data rather than an array.

And actually, given this is ES2015, we can use a Map:

function memoize(f) {
  // An Map in which to remember objects with the input arg and result 
  const memory = new Map();
  
  // This is the function that will use that array; this is the
  // return value of memoize
  return function(arg) {
    // This code runs when the function returned by memoize is called
    // It's *here* that we want to process the argument, check the `memory`
    // array, call `f` if necessary, etc.
    let result;
    
    // See if we have a previously-saved result for `arg`
    if (!memory.has(arg)) {
      // No -- call `fn`, remember the `arg` and result in an object
      // we store in memory``
      result = f(arg);
      memory.set(arg, result);
    } else {
      // Yes, get it
      result = memory.get(arg);
    }
    
    // We have it (now), return the result
    return result;
  };
}
function fn(arg) {
  console.log("fn called with " + arg);
  return 2 * arg;
}
var m_fn = memoize(fn);
console.log(m_fn(18));
console.log(m_fn(18));
console.log(m_fn(20));
console.log(m_fn(20));

Note that in both cases, I've written the code verbosely to allow for comments and easy comprehension. The ES2015 version with Map, in particular, can be quite a lot shorter.

Answer 3

Indeed, you need to return a function.

Secondly, an array is not the ideal structure for memory, because it takes linear time to find an argument value in it. I would suggest to use a Map for this, which is ideal for such purposes. It has has(), get() and set() methods which run in near-constant time:

function memoize(fn) {
    var memory = new Map();
    return function(arg) {
        if (memory.has(arg)) {
            console.log('using memory');
            return memory.get(arg);
        } else {
            var result = fn(arg);
            memory.set(arg, result);
            return result;
        }
    };
}

var fn = (n) => 2 * n
var m_fn = memoize(fn)

console.log(fn(18));
console.log(m_fn(18));
console.log(m_fn(18)); // outputs also "using memory"