问题描述
函数类型为Tree a -> Tree (a, Int)。我希望在整个树中进行计数，并相应地对每个出现的叶进行编号。
到目前为止，我已经尝试过了：
labelTree :: Tree a -> Tree (a, Int)
labelTree (Leaf a) = Leaf (a,1)
labelTree (tr) = labelTree' (tr) 0
labelTree' :: Tree a -> Int -> (Tree (a,Int))
labelTree' (Leaf a) n = Leaf (a,(n+1))
labelTree' (Node l r) n = (labelTree' (r) (snd (labelTree' (l) n)))
问题是我不确定为什么它会给我这个表达式的类型错误：labelTree' (Node l r) n = (labelTree' (r) (snd (labelTree' (l) n)))
请指出我哪里出错了！
推荐答案
这里您可能需要某种累加器：一个通过递归调用传递的变量，每次"分配"下一个ID时递增。
因此，我们根据帮助器函数go定义我们的函数。go将返回一个二元组："标签"树，以及我们将"调度"的下一个ID。这将在后面使用，因为我们定义了一个递归调用：
labelTree :: Tree a -> Tree (a, Int)
labelTree = fst . go 0
where go ...因此go具有类型Int -> Tree a -> (Int, Tree (a, Int))。如果我们看到Leaf，我们就会"分派"该id，然后返回该叶子以及作为元组第二部分：
go (Leaf x) n = (Leaf (x, n), n+1)
对于一个节点，我们首先将ID分派到左子树，然后以该元组的第二项为起点将元素分派到右子树，如：
go (Node l r) n0 = (Node ll lr, n2)
where (ll, n1) = go l n0
(lr, n2) = go r n1
go l n0来标记左子树，并获得一个包含ll标记的左子树的二元组(ll, n1)，以及n1稍后要调度的新数字。我们调用go r n1，因此我们将数字分派到以n1开始的右子树。因此，我们的go函数返回一个新的Node，其中带有标记的子树和要调度的新数字。这对于此函数的调用方很重要。
完整地说，我们可以用：
来标记树labelTree :: Tree a -> Tree (a, Int)
labelTree = fst . go 0
where go (Leaf x) n = (Leaf (x, n), n+1)
go (Node l r) n0 = (Node ll lr, n2)
where (ll, n1) = go l n0
(lr, n2) = go r n1