Re: Soliciting criticism of memoize function

["Patrick Donnelly" <batrick.donnelly@...>]

On Wed, May 14, 2008 at 7:40 PM, Norman Ramsey <nr@eecs.harvard.edu> wrote:
> I would be pleased if readers of this list could think of any improvements
> to the following memoize function:
>
>  function memoize (f)
>    -- f must take at most one argument and return at most one result
>      local cache = setmetatable({ }, { __mode = 'k' })
>      local function update(x, v, ...) -- f(x) returns v, ...
>        assert(select('#', ...) == 0)
>        cache[x] = v
>        return v
>      end
>
>      return function (x, ...)
>               assert(select('#', ...) == 0) -- cache works with at most one arg
>               local v = cache[x]
>               if v ~= nil then
>                 return v
>               else
>                 return update(x, f(x))
>               end
>             end
>  end
>
> I'm especially concerned whether I have the cache's __mode metamethod
> set correctly, as I always get confused about the semantics of weak
> keys and weak values.
>
>
> Norman
>


I would move the metatable construction outside memoize because it
never changes. You could also do this instead:

do
  local FUNC = {}; -- key holder
  local mt = {
    __mode = "k",
    __index = function(t, k)
      t[k] = t[FUNC](k);
      return t[k];
    end
  };
  function memoize (f)
    -- f must take at most one argument and return at most one result
    local cache = setmetatable({[FUNC] = f}, mt)
    return function (x, ...)
      assert(select('#', ...) == 0) -- cache works with at most one arg
      return cache[x];
    end
  end
end

The __mode look ok to me.

-- 
-Patrick Donnelly

"One of the lessons of history is that nothing is often a good thing
to do and always a clever thing to say."

-Will Durant