disco-0.2: example/tree.disco

type Tree = Unit + N * Tree * Tree

leaf : Tree
leaf = left(■)

node : N * Tree * Tree -> Tree
node = right

tree1 : Tree
tree1 = node(3, node(5, node(1, leaf, leaf), leaf), node(6, node(2, leaf, leaf), node(8, leaf, leaf)))

treeFold : r * (N * r * r -> r) * Tree -> r
treeFold(x, f, left(■)) = x
treeFold(x, f, right(n,l,r)) = f(n, treeFold(x, f, l), treeFold(x, f, r))

treeSum : Tree -> N
treeSum(t) = treeFold(0, \(x,l,r). x + l + r, t)

treeSize : Tree -> N
treeSize(t) = treeFold(0, \(x,l,r). 1 + l + r, t)

treeHeight : Tree -> N
treeHeight(t) = treeFold(0, \(x,l,r). 1 + max(l,r), t)