Recursive Data Types

lua-users home
wiki

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)