Re: iterating over ... ?

[Jerome Vuarand <jerome.vuarand@...>]

2011/4/4 Benoit Germain <bnt.germain@gmail.com>:
> Hello,
>
> I have some code where I have to perform some process over an already known
> set of data. For the sake of not duplicating the code process, I want to
> iterate over each item in a loop. I know a very simple way of doing this is
> to store each item in a table and iterate with ipairs(). However, as an
> exercise, I wanted to code my own iterator with a vararg function, to be
> used as follows:
>
> -- return an iterator that will pass all received arguments in sequence
> iterate_over = function( ...)
>     local items, count = {...}, select( '#', ...)
>     local iterator = function( _s, _key)
>         if _key >= count then
>             return nil
>         end
>         _key = _key + 1
>         return _key, items[_key]
>     end
>     return iterator, nil, 0
> end
>
> for _, item in iterate_over( a, b, c) do
>   do_something( item)
> end
>
> The idea was to avoid the creation of a table just for the purpose of being
> able to iterate over its contents.
> Unfortunately, it would seem that I must generate a table to enclose the
> vararg list anyway, so that I can index it. Is there something I missed that
> could help avoid
> 1. the creation of this items table?
> 2. calling select just to get the number of items, thus losing time pushing
> the full ... again on the stack?
>
> TBH, I currently have 2 such items, so I can live with these performance
> hogs :-). But I would like to know if there is a better solution, for my own
> education.

You can use coroutines, but I don't think it's a better solution. For example:

local function step(head, ...)
  if head==nil then
    return
  end
  coroutine.yield(head)
  return step(...)
end

local function init(...)
  coroutine.yield()
  return step(...)
end

local function vararg(...)
  local c = coroutine.wrap(init)
  c(...)
  return c
end

for value in vararg(1, 2, 3) do
  print(value)
end

Now without coroutines... All the state that the for loop is
preserving accross iteration is the iterator function (f), the state
value (s), and the previous "key" (p). To hold the vararg list (...)
in either s or p you would need to allocate a table. To hold the
vararg list in f, you would need to put it either in the function
environment (and allocate a table), or as upvalues. But you cannot
access the vararg list of an outer function as a single upvalue, so
you would need a variable number of upvalues, which would prevent the
solution for scaling.

However there is a very contrieved solution to hold the full vararg in
a single Lua value, without allocating table or calling select. It
consists in recursively storing the vararg elements in a linked list
of closures, with one closure per element of the list. That would
however probably be much more costly in terms of CPU and memory
(though you may want to benchmark it). For example:

local function state(head, ...)
  if head==nil then
    return function() end
  end
  local tail = state(...)
  return function()
    return head,tail
  end
end

local function vararg(...)
  local list = state(...)
  return function()
    local head,tail = list()
    list = tail
    return head
  end
end

for value in vararg(1, 2, 3) do
  print(value)
end

Note that I store the list in an upvalue of "f" because it needs to be
in a mutable object, and putting it in either "s" or "p" would require
allocating a table.