Recursive Data Types

wiki

Difference (from revision 10 to current revision) (minor diff, author diff)

Changed: 7c7,8

To build such a data structure, you need a constructor for each variant of node: InteriorNode and LeafNode. And when traversing the data structure, you need a switch statement to do different things with the different data. The function deftype[1] or [2] creates a named class to help you do just that.

To build such a data structure, you need a constructor for each variant of node: InteriorNode and LeafNode. And when traversing the data structure, you need a switch statement to do different things with the different data. The function deftype[1] creates the constructors from a simple specification. The function cases returns a
switching function that can be used to traverse the data structure.

Changed: 9,11c10,11

Here are the constructors[1] or [2]:
{{{
require'DefType?.lua'

{{{!Lua
require'DefType?'

Changed: 13c13,20

deftype'bintree'

deftype 'bintree' {
'number';
Node = {
name ='string',
left ='bintree',
right='bintree',
};
}

Changed: 15,17c22,23

function bintree:LeafNode?( datum )
check( datum, 'number' )
return { datum }

local function node(name, left, right)
return Node{name=name, left=left, right=right}

Changed: 20,28c26,30

function bintree:InteriorNode?( t )
local name, left, right = unpack(t)
check( name, 'string' )
check( left, 'bintree' )
check( right, 'bintree' )
return t
end
}}}
They are just member functions of the bintree class that return a table. The settable event for bintree is used to "fix" the member functions to set the variant field of the table so that you can use the check function for type checking. The variant field is also used by the switch statement.

local tree = node(
'cow',
node('rat', 1, 2),
node('pig', node('dog', 3, 4), 5)
)

Changed: 30,32c32

The tree in the diagram can now be defined as follows:
{{{
local b = bintree

------------------------------------------------------------------------------

Removed: 34,53d33

local t = b:InteriorNode?{
'cow',
b:InteriorNode?{
'rat',
b:LeafNode?( 1 ),
b:LeafNode?( 2 ),
},
b:InteriorNode?{
'pig',
b:InteriorNode?{
'dog',
b:LeafNode?( 3 ),
b:LeafNode?( 4 ),
},
b:LeafNode?( 5 ),
},
}
}}}
Making functions that traverse the tree is just as easy. The cases method is used to make the switch statement, which is just a table with a call event that calls the right function for each variant. Here is how you would sum the values of all the leaves in the tree.
{{{

Changed: 55,63c35,41

leafsum = bintree:cases{
LeafNode? = function( obj )
local datum = unpack(obj)
return datum
end,
InteriorNode? = function( obj )
local name, left, right = unpack(obj)
return leafsum( left ) + leafsum( right )
end,

leafsum = cases 'bintree' {

number = function(n) return n end;

Node = function(node)
return leafsum(node.left) + leafsum(node.right)
end;

Changed: 66,71c44,46

io.write( 'leaf sum = ', leafsum(t), '\n' )
}}}
The following will print out the tree in a format suitable for Lout[1] to generate a diagram of it.
{{{
local write = io.write
local strrep = string.rep

io.write('leaf sum = ', leafsum(tree), '\n\n')

------------------------------------------------------------------------------

Changed: 73,74c48,49

function indented( level, ... )
write( strrep( ' ', level ), unpack(arg) )

local function indented(level, ...)
io.write(string.rep(' ', level), unpack(arg))

Changed: 78,94c53,68

treewalki = bintree:cases{
LeafNode? = function( obj, level )
local datum = unpack(obj)
write( ' @', obj.name, ' ', datum, '\n' )
end,
InteriorNode? = function( obj, level )
local name, left, right = unpack(obj)
local lp1 = level+1
write( ' {\n' )
indented( lp1, '@', obj.name, ' ', name, '\n' )
indented( lp1, '@left' )
treewalki( left, lp1 )
indented( lp1, '@right' )
treewalki( right, lp1 )
indented( level, '}\n' )
end,
default = error,

treewalki = cases 'bintree' {

number = function(n)
io.write(' @LeafNode? ', n, '\n')
end;

Node = function(node, level)
local plus1 = level+1
io.write(' {\n')
indented(plus1, '@InteriorNode? ', node.name, '\n')
indented(plus1, '@left')
treewalki(node.left, plus1)
indented(plus1, '@right')
treewalki(node.right, plus1)
indented(level, '}\n')
end;

Changed: 97,99c71,73

function treewalk( tree )
write( '@Tree' )
treewalki(tree,0)

local function treewalk(t)
io.write('@Tree')
treewalki(t, 0)

Changed: 102c76

treewalk(t)

treewalk(tree)

Changed: 104c78,79

This is what treewalk outputs:

This example produces the following output:

Added: 105a81,82

leaf sum = 15

Removed: 123,124d99

}}}
[Here] is the complete Lout file and its encapsulated postscript [output]. Ghostscript was used to convert from eps to jpg.

Changed: 126,127c101

The DefType module make use of the Class module which can be found here
[1] or [2]

}}}

Added: 128a103,105

The tree diagram was generated by Lout[1] from
[fig1.lt].
Ghostscript was used to convert from EPS to JPG.

Functional programming languages make recursion really easy by providing product and sum data types. These are built into languages like Haskell and ML, and can be added to Scheme with clever macros as in EOPL[1]. If Scheme can do it, so can Lua :-)

Say you want to represent a tree that has labelled nodes and numbered leaves.

To build such a data structure, you need a constructor for each variant of node: InteriorNode and LeafNode. And when traversing the data structure, you need a switch statement to do different things with the different data. The function deftype[3] creates the constructors from a simple specification. The function cases returns a switching function that can be used to traverse the data structure.

require'DefType'

deftype 'bintree' {
  'number';
  Node = {
    name ='string',
    left ='bintree',
    right='bintree',
  };
}

local function node(name, left, right)
  return Node{name=name, left=left, right=right}
end

local tree = node(
  'cow',
  node('rat', 1, 2),
  node('pig', node('dog', 3, 4), 5)
)

------------------------------------------------------------------------------

local leafsum
leafsum = cases 'bintree' {

  number = function(n) return n end;

  Node = function(node)
    return leafsum(node.left) + leafsum(node.right)
  end;
}

io.write('leaf sum = ', leafsum(tree), '\n\n')

------------------------------------------------------------------------------

local function indented(level, ...)
  io.write(string.rep('  ', level), unpack(arg))
end

local treewalki
treewalki = cases 'bintree' {

  number = function(n)
    io.write(' @LeafNode ', n, '\n')
  end;

  Node = function(node, level)
    local plus1 = level+1
    io.write(' {\n')
    indented(plus1, '@InteriorNode ', node.name, '\n')
    indented(plus1, '@left')
    treewalki(node.left, plus1)
    indented(plus1, '@right')
    treewalki(node.right, plus1)
    indented(level, '}\n')
  end;
}

local function treewalk(t)
  io.write('@Tree')
  treewalki(t, 0)
end

treewalk(tree)

This example produces the following output:

leaf sum = 15

@Tree {
  @InteriorNode cow
  @left {
    @InteriorNode rat
    @left @LeafNode 1
    @right @LeafNode 2
  }
  @right {
    @InteriorNode pig
    @left {
      @InteriorNode dog
      @left @LeafNode 3
      @right @LeafNode 4
    }
    @right @LeafNode 5
  }
}

The tree diagram was generated by Lout[2] from [fig1.lt]. Ghostscript was used to convert from EPS to JPG.

RecentChanges · preferences
edit · history
Last edited July 10, 2013 6:50 pm GMT (diff)