在Haskell中,从左到右对树中出现的所有叶子进行编号 [英] Number all occurring leaves in a tree from left to right in Haskell
本文介绍了在Haskell中,从左到右对树中出现的所有叶子进行编号的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
函数类型为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
这篇关于在Haskell中,从左到右对树中出现的所有叶子进行编号的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文