Table traversal

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Table traversal

Dirk Laurie-2
A possibly useful addition to the repertoire of table iterators is
"traverse", which recursively visits every non-table value in a table
and returns not that value but a key-table pair (k,s) so that s[k]
refers to the table entry.  This can be extended to allow the cloning
of table structure and the simultaneous traversal of several tables.

For example, this is a deep table copy:

   t2={}
   for k,s1,s2 in traverse(t1,t2) do s2[k]=s1[k] end

An implementation as a module (Lua 5.1/5.2) is attached.

Dirk

traverse.lua (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Table traversal

David Manura
On Sat, Nov 12, 2011 at 3:03 PM, Dirk Laurie <[hidden email]> wrote:
> A possibly useful addition to the repertoire of table iterators is
> "traverse", which recursively visits every non-table value in a table
> and returns not that value but a key-table pair (k,s) so that s[k]
> refers to the table entry.  This can be extended to allow the cloning
> of table structure and the simultaneous traversal of several tables.
> For example, this is a deep table copy:
>   t2={}
>   for k,s1,s2 in traverse(t1,t2) do s2[k]=s1[k] end

It shouldn't be necessary to create a coroutine on each node
traversal.  Here's a simpler example (for illustration):

  local function traverse(o, f)
    if type(o) == 'table' then
      for _,v in ipairs(o) do traverse(v, f) end
    else
      f(o)
    end
  end
  local function traverse2(o)
    local co = coroutine.wrap(traverse)
    return function()
      return co(o, coroutine.yield)
    end
  end
  local t = {3,4,{5,6}}
  for o in traverse2(t) do print(o) end  --> 3,4,5,6

Here `traverse` is your typical call-back based recursive tree
traversal (without any coroutines), and `traverse2` transforms it into
an iterator by inverting the control with a single coroutine.

I also question how often the behavior "t1 is cloned into
t2,t3,...,tn" would be used.

A tangential note: Fabien recently posted on the design of a tree
traversal API [1].

[1] http://metalua.blogspot.com/2011/10/treequery-dsl-for-syntax-tree.html
    http://groups.google.com/group/metalua/browse_thread/thread/36af70b007f7aa0e

Reply | Threaded
Open this post in threaded view
|

Re: Table traversal

Dirk Laurie-2
2011/11/13 David Manura <[hidden email]>:
>
> Here `traverse` is your typical call-back based recursive tree
> traversal (without any coroutines), and `traverse2` transforms
> it into an iterator by inverting the control with a single coroutine.
>
Beautiful!  I'll make sure I understand it, and change my code
accordingly, in that order.

> I also question how often the behavior "t1 is cloned into
> t2,t3,...,tn" would be used.
>
I can get away, in the intended application, with cloning the
structure into only one of them.  Problem is, I don't know in advance
which.

For example (changing the name 'traverse' of my original proposal to
'leaves'), here is matrix addition:

   a={{10,10,10},{20,20,20}}
   b={{1,2,3},{1,2,3}}
   c={}
   for k,sa,sb,sc in leaves(a,b,c) do sc[k]=sa[k]+sb[k] end

However, in that case the others must have the structure already.  The
way I do it, nothing happens then: only for c is the structure cloned.

The alternative is to separate the cloning of the structure from
visiting the leaves.  I.e. "leaves" will do no cloning, and instead
"c={}" is replaced by "c=clone(a)".  Probably neater.

Dirk

Reply | Threaded
Open this post in threaded view
|

Re: Table traversal

Patrick Rapin
In reply to this post by Dirk Laurie-2
> A possibly useful addition to the repertoire of table iterators is
> "traverse", which recursively visits every non-table value in a table
> and returns not that value but a key-table pair (k,s) so that s[k]
> refers to the table entry.  This can be extended to allow the cloning
> of table structure and the simultaneous traversal of several tables.
>
> For example, this is a deep table copy:
>
>   t2={}
>   for k,s1,s2 in traverse(t1,t2) do s2[k]=s1[k] end

This is quite an interesting function, for:
- Performing a multiple deep table copy is very easy with the
function, but I think it is rarely needed.
- Comparing two tables with the same structure can be done easily in Lua.

BTW, for both tasks, the few times I have needed that feature, I used
table serialization. [1].
- To make a deep copy, serialize the first table and evaluate the
string for cloning
- To compare, serialize both tables to files and use a file comparison
software...

But I would also like to use such a function to
- easily dump the table data to screen
- search for a particular data in a recursive table.

In both cases, we need to have *the context* of where the k,s1,s2
values can be found.
The better would be a table with a stack of keys (c in the next example).
So, one could write something like that to compare on screen two tables :

for k,c,s1,s2 in traverse(t1,t2) do
  print(  table.concat(c,"/"), s1[k], s2[k] )
end

[1] http://lua-users.org/wiki/TableSerialization