Recursive Data Types

wiki

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)

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.