Recursive Data Types

wiki

Showing revision 10
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] or [4] creates a named class to help you do just that.

Here are the constructors[5] or [6]:

require'DefType.lua'

deftype'bintree'

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

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.

The tree in the diagram can now be defined as follows:

local b = bintree

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.

local leafsum
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,
}

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

The following will print out the tree in a format suitable for Lout[2] to generate a diagram of it.

local write  = io.write
local strrep = string.rep

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

local treewalki
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,
}

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

treewalk(t)

This is what treewalk outputs:

@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
  }
}

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

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

RecentChanges · preferences
edit · history · current revision
Edited September 4, 2002 6:24 am GMT (diff)