递归数据类型

wiki

假设你想表示一个带有标签节点和编号叶子的树。

要构建这样的数据结构，你需要为节点的每种变体（InteriorNode 和 LeafNode）提供一个构造器。在遍历数据结构时，你需要一个 switch 语句来处理不同的数据。deftype[3] 函数根据简单的规范创建构造器。cases 函数返回一个可以用来遍历数据结构的切换函数。

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

树形图是由 Lout[2] 从 [fig1.lt] 生成的。Ghostscript 用于将 EPS 转换为 JPG。