Re: Memoizing Functions - yet another attempt

[Dirk Laurie <dirk.laurie@...>]

2013/12/15 Petite Abeille <petite.abeille@gmail.com>:
> On Dec 14, 2013, at 11:07 PM, Andrew Starks <andrew.starks@trms.com> wrote:
>
>> The argument list is:
>>
>> function(k, ...)
>>
>> So, it only memoizes on the first argument but accepts many. There must be a general use case for this, but it isn't clear to me what that would be.

One possible general use case is in fact to wrap vararg functions.
`k` is the serialization of the others. They are still available, no need
to decode the serialization, when it's a call. See below though.

> Nah, just confusion. One parameter is all it takes. The vargs could as well not be there.

You're right. Making the cache a callable table looks neat, and fooled
me into thinking it will work, but the __index metamethod accepts only
two parameters, not vararg, so the others are never passed to the original
function.

Taking into account Steve's original notion, the issue raised by the OP,
and the comments quoted above, my personal ml.lua now contains
the following version:

~~~{.lua}
--- 'memoize' a function (cache returned value for next call).
-- This is useful if you have a function which is relatively expensive,
-- but you don't know in advance what values will be required, so
-- building a table upfront is wasteful/impossible.
-- @param func a function of at least one argument
-- @param serialize optional routine to convert arguments to a table key
--   (default: first argument to `func`)
-- @return a function that does the same as `func`
function ml.memoize(func,serialize)
   local cache = {}
   return function(...)
      local key = ...
      if serialize then key=serialize(...) end
      local val = cache[key]
      if val then return val end
      val = func(...)
      cache[key] = val
      return val
   end
end
~~~

This retains efficiency in the most common use-case and provides
flexibility for those who need it, e.g. your serializer can cope with
the occasional nil in the argument list. The other items on the OP's
wishlist are not IMHO tasks for the memoizer.

- serialiation is much too complex in general for a one-size-fits-all
approach
- if you have multiple return values, pack/unpack them yourself.
- functions expensive enough to memoize should not return nil.

Sample:

> ml=require'ml'
> sum = function(...)
   local s=0
   for k=1,select('#',...) do s=s+select(k,...) end
   return s
end
> sum = ml.memoize(sum,ml.tstring)