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.