Re: Soliciting criticism of memoize function

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

On Sat, May 17, 2008 at 12:12 AM, Mark Hamburg <mark_hamburg@baymoon.com> wrote:
> Some issues to deal with in getting a generic memoize to work correctly:
>
> 1. Do you need to support memoization for f( nil )? If so, you potentially
> need to handle this separately (but see below).
>
> 2. Do you handle nil results from f correctly? Efficiently?
> ...

That's a little overly complicated, you can deal with it like this
(using my previous example):

do
 local FUNC = {}; -- key holder
 local NIL = {}; -- nil key
 local NaN = {} -- NaN
 local mt = {
   __mode = "k",
   __index = function(t, k)
     if k == nil then
       if t[NIL] then return t[NIL] end
       t[NIL] = t[FUNC](k);
       return t[NIL];
     elseif k ~= k and type(k) == "number" then
       if t[NaN] then return t[NaN] end
       t[NaN] = t[FUNC](k);
       return t[NaN];
     else
       t[k] = t[FUNC](k);
       return t[k];
     end
   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


On Thu, May 15, 2008 at 6:38 PM, Norman Ramsey <nr@eecs.harvard.edu> wrote:
>  > You could also [use the __index metamethod instead of testing for nil]
>
> I like this idea; I hope my colleague will like it as well.  It makes
> the code a little cleaner and the 'fast path' (a hit in the cache)
> will be a little faster.   But notice it's even nicer if you just
> capture the function lexically:

I noticed this, but I wanted to keep the metatable outside of the
memoize function. This is of course up to you (make a new metatable
for each memoized function or not).

Cheers,

-- 
-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