How do I make an iterator over a 2-dimensional table in Lua?

Question

I've got a lua table made of tables, so it's two-dimensional: root -> child -> grandchild.

None of the levels of this hierarchy is guaranteed to be "array-like". The first level has integers with "nil gaps", and second one is not even indexed by integers (but by tables).

The table in question is a private structure inside a lib. I want to provide a way for the library user to parse its grandchildren. I don't care much about the order in which the they are parsed, as long as all of them are.

The first thing I thought about was using a function accepting a callback:

-- this scope has access to root 
function eachGrandChild(callback)
  for _,child in pairs(root) do
    for index,grandChild in pairs(child)
      callback(index, grandChild)
    end
  end
end

Usage:

-- no access to root, only to eachGrandChild
eachGrandChild(function(index, grandChild) print(index, grandChild) end)

This much is understood.

My question is: could I provide a similar functionality using an iterator instead?

I'm talking about something that would allow me to do this:

for index,grandChild in iterator() do
  print(index, grandChild)
end

I've been thinking about this for a while but I'm not able to crack it. All the examples I've seen use numbers to easily "manage the state of the iterator" on each iteration. Since I don't have numbers, I'm a bit stuck.

Answer 1

Coroutines make it easy to write this kind of iterator. A coroutine is a function whose execution can be suspended and resumed, conceptually like a thread. A coroutine can contain deeply nested loops, yield a value from the inner most loop, then continue right where it left off when resumed. When it yields, the caller who resumed it can receive yielded values.

In your case, convert eachGrandChild into a generator function which yields grandchildren.

function eachGrandChild(root)
  for _,child in pairs(root) do
    for index,grandChild in pairs(child) do
      coroutine.yield(index, grandChild)
    end
  end
end

Then use coroutine.wrap to create a function that will create a coroutine for your generator and resume it each time the function is called.

function grandChildren(t)
    return coroutine.wrap(function() eachGrandChild(t) end)
end

Now you have your iterator:

for key, val in grandChildren(root) do
    print(key, val)
end

There's a chapter on this in Programming in Lua.