1 Introduction
This article describes ways to define and use Lua recursive functions to walk and process recursively nested data structures.
We explore several different approaches:
- A functional approach -- Definition/implementation of a data structure or data type along with a set of functions to create and process it.
- An object oriented approach -- Definition of a class that implements a data type and a set of functions associated with that data type.
And, in the above approaches we will focus on recursive and nested data structures.
In the discussion below, I've included snippets of code. The complete file that demonstrates both approaches (functional and object oriented) and that demonstrates processing two different data structures (single linked lists and trees) is available here: recursion_demo.lua
And, here is a test function that exercises both the functional and object oriented code given below:
--
-- Test harness
--
function M.test()
print('-- single link function --')
M.walk_and_show_single_link(M.sample_single_link)
print('sum single link:', M.sum_single_link(M.sample_single_link, 0))
print('-- tree function --')
M.walk_and_show_tree(M.sample_tree)
print('sum tree:', M.sum_tree(M.sample_tree))
print('-- OO -- object oriented --')
M.sample_single_link_oo:walk_and_show_singlelink_oo(M.sample_single_link_oo)
print('oo sum:', M.sample_single_link_oo:sum_single_link_oo(0))
M.sample_tree_oo:walk_and_show_tree_oo('')
print('oo tree sum:', M.sample_tree_oo:sum_tree_oo())
end
2 The functional approach
The functional code:
--
-- Processing with functions
--
-- Single linked nodes/lists
--
function M.new_single_link(data, next)
node = {data=data, next=next}
return node
end
function M.walk_and_show_single_link(node)
if node == nil then
return nil
else
print('node:', node.data)
return M.walk_and_show_single_link(node.next)
end
end
function M.sum_single_link(node, sum)
if node == nil then
return sum
else
local new_sum = sum + node.data
return M.sum_single_link(node.next, new_sum)
end
end
local a = M.new_single_link(333, nil)
local b = M.new_single_link(222, a)
local c = M.new_single_link(111, b)
M.sample_single_link = c
--
-- Processing with functions
--
-- Trees
--
function M.new_tree(data, children)
node = {data=data, children=children}
return node
end
function M.walk_and_show_tree(node, indent)
indent = indent or ''
print(string.format('%snode: %s', indent, node.data))
local new_indent = indent .. ' '
for _, child in ipairs(node.children) do
M.walk_and_show_tree(child, new_indent)
end
end
function M.sum_tree(node)
local sumA = 0
for _, child in ipairs(node.children) do
sumA = sumA + M.sum_tree(child)
end
return sumA + node.data
end
local a1a = M.new_tree(111, {})
local a1b = M.new_tree(222, {})
local a2a = M.new_tree(333, {})
local a2b = M.new_tree(444, {})
local b1 = M.new_tree(555, {a1a, a1b})
local b2 = M.new_tree(666, {a2a, a2b})
local c = M.new_tree(777, {b1, b2})
M.sample_tree = c
Notes:
With respect to recursive function calls and tail calls, note this comment copied from section "3.4.10 – Function Calls" of the Lua reference manual section "3.4.10 – Function Calls":
A call of the form "return functioncall" not in the scope of a
to-be-closed variable is called a tail call. Lua implements proper
tail calls (or proper tail recursion): in a tail call, the called
function reuses the stack entry of the calling function. Therefore,
there is no limit on the number of nested tail calls that a program
can execute. However, a tail call erases any debug information
about the calling function. Note that a tail call only happens with
a particular syntax, where the return has one single function call
as argument, and it is outside the scope of any to-be-closed
variable. This syntax makes the calling function return exactly the
returns of the called function, without any intervening action. So,
none of the following examples are tail calls:
return (f(x)) -- results adjusted to 1
return 2 * f(x) -- result multiplied by 2
return x, f(x) -- additional results
f(x); return -- results discarded
return x or f(x) -- results adjusted to 1
So, I believe, our recursive function call in walk_and_show_single_link is a recursive tail call and does not use up increasingly more call stack space. However, our recursive call in sum_tree is not a proper tail call, and so it does use increasingly more stack space as it processes each nested level of the tree data structure. That seems alright to me, because any tree will have some maximum depth, unless the tree is pathological and has a branch that goes on and on and on ...
3 The object oriented approach
The object oriented code:
--
-- Processing with an object oriented approach
--
-- ClassSingleLinkedList -----------------------------------------------
--
M.ClassSingleLinkedList = {}
M.ClassSingleLinkedList.__index = M.ClassSingleLinkedList
-- Enable call to `.new` without ".new".
-- Failed table lookups on instances fallback to the class table to get methods.
-- See http://lua-users.org/wiki/ObjectOrientationTutorial
setmetatable(M.ClassSingleLinkedList, {
__call = function (cls, ...)
return cls.new(...)
end,
})
function M.ClassSingleLinkedList.new(data, next)
local self = setmetatable({}, M.ClassSingleLinkedList)
self.data = data
self.next = next
return self
end
function M.ClassSingleLinkedList.walk_and_show_singlelink_oo(self)
print('walk oo self:', self.data)
if self.next ~= nil then
return M.ClassSingleLinkedList.walk_and_show_singlelink_oo(self.next)
end
end
function M.ClassSingleLinkedList.sum_single_link_oo(self, sum)
local new_sum = sum + self.data
if self.next == nil then
return new_sum
else
--return self.next:sum_tree(new_sum)
return M.ClassSingleLinkedList.sum_single_link_oo(self.next, new_sum)
end
end
local a = M.ClassSingleLinkedList(333, nil)
local b = M.ClassSingleLinkedList(222, a)
local c = M.ClassSingleLinkedList(111, b)
M.sample_single_link_oo = c
--
-- Processing with an object oriented approach
--
-- ClassTree -----------------------------------------------
--
M.ClassTree = {}
M.ClassTree.__index = M.ClassTree
-- Enable call to `.new` without ".new".
-- Failed table lookups on instances fallback to the class table to get methods.
-- See http://lua-users.org/wiki/ObjectOrientationTutorial
setmetatable(M.ClassTree, {
__call = function (cls, ...)
return cls.new(...)
end,
})
function M.ClassTree.new(data, children)
local self = setmetatable({}, M.ClassTree)
self.data = data
self.children = children
return self
end
function M.ClassTree.walk_and_show_tree_oo(self, indent)
--indent = indent or ' '
print(string.format('%swalk oo self: %s', indent, self.data))
local indentA = indent .. ' '
for _, child in ipairs(self.children) do
child:walk_and_show_tree_oo(indentA)
end
end
function M.ClassTree.sum_tree_oo(node)
local sumA = 0
for _, child in ipairs(node.children) do
sumA = sumA + child:sum_tree_oo()
end
return sumA + node.data
end
local a1a = M.ClassTree(111, {})
local a1b = M.ClassTree(222, {})
local a2a = M.ClassTree(333, {})
local a2b = M.ClassTree(444, {})
local b1 = M.ClassTree(555, {a1a, a1b})
local b2 = M.ClassTree(666, {a2a, a2b})
local c = M.ClassTree(777, {b1, b2})
M.sample_tree_oo = c
Notes:
Considering tail recursive calls -- Again, as with the functional approach, it appears that the single list example uses proper tail recursive calls and enables Lua to process a long list without consuming increasing amounts of stack space. That is a big win, because lists, one can imagine, can be very long.
In contrast, the example code for the tree data structure is not tail recursive. In the case of sum_tree_oo, we need to do an operation after the recursive call and in the cases of both sum_tree_oo and walk_and_show_tree_oo, the recursive call is not in a return statement. As specified in the Lua reference manual, tail recursive calls must be of the form return functioncall. But, since we have more children of the node of our tree that must be processed, we cannot do a return. However, this seems like a reasonable limitation, at least in all cases except those that require processing a pathological tree containing one or more branches that have extremely long length.
Organization of the code -- In the case of both the single linked list and the tree data structures:
- We define a method (in our class) that is used to construct a new node: it's the constructor in our class and it creates an instance.
- Then we define our processing methods: walk_and_show_tree_oo and sum_tree_oo.
- And we construct a sample data structure to be used for testing our code.