在Haskell中从左到右对树中所有发生的叶子进行编号

Question

函数类型是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)))

请说明我出错的地方!

Answer 1

我和chepner一样有同样的想法:使用State.但是,您不必自己编写递归,因为这是对树的简单遍历!相反,为您的树派生Traversable和Foldable(无论如何都是好主意),然后依靠它们为您做递归:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveTraversable #-}

import qualified Control.Monad.Trans.State.Strict as S
data Tree a = Leaf a | Node (Tree a) (Tree a)
            deriving (Show, Functor, Foldable, Traversable)

labelTree :: Tree a -> Tree (a, Int)
labelTree t = S.evalState (traverse applyLabel t) 0
  where applyLabel x = do
          n <- S.get
          S.modify' succ
          pure (x, n)

*Main> labelTree (Node (Node (Leaf 'a') (Leaf 'b')) (Leaf 'c'))
Node (Node (Leaf ('a',0)) (Leaf ('b',1))) (Leaf ('c',2))

此实现的一个很好的特性是,如果更改树的结构(例如,将数据存储在内部节点中),它仍然可以工作.不可能像交换节点的顺序那样犯错,因为你根本不在那个级别工作:Traversable为你处理它.

Answer 2

你可能需要的是某种累加器:一个你通过递归调用的变量,每次你在"分配"下一个id时递增.

因此,我们根据辅助函数定义了我们的函数go.go将返回一个2元组:"标记"树,以及我们将"发送"的下一个ID.这将在以后使用,因为我们定义了一个递归调用:

labelTree :: Tree a -> Tree (a, Int)
labelTree = fst . go 0
    where go ...

所以go有类型Int -> Tree a -> (Int, Tree (a, Int)).如果我们看到一个Leaf,我们就这样"发送"那个id,然后返回那个叶子,n + 1作为元组的第二部分,如:

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, n1)包含ll标记的左子树的2元组,以及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

Answer 3

您可以使用Statemonad跟踪要添加到节点的数字。

labelTree :: Tree a -> Tree (a, Int)
labelTree l = evalState (labelTree' l) 0
    where labelTree' :: Tree a -> State Int (Tree (a, Int))
          labelTree' (Node l r) = Node <$> labelTree' l <*> labelTree' r
          labelTree' (Leaf a) = do n <- get
                                   put $ n + 1
                                   return $ Leaf (a, n)

labelTree'建立有状态的计算，该计算将按有序遍历对叶子进行编号。evalState然后在初始状态为0的情况下运行计算，以便叶子从0开始编号。

递归的情况看起来很像普通的树函数。Node您可以使用Applicative实例，而不是简单地将其应用于每个递归调用的结果。

每个基本案例都Leaf使用当前状态进行编号，并为下一个叶​​子更新状态。

（请注意，这与Willem Van Onsem的答案非常相似。由于State s a有效地封装了type函数s -> (a, s)，因此labelTree' :: Tree a -> State Int (Tree (a, Int), Int)可以将type转换为与type相同的类型go：

labelTree' :: Tree a -> State Int (Tree (a, Int)) 
            ~ Tree a -> Int -> (Tree (a, Int), Int)
go ::         Tree a -> Int -> (Tree (a, Int), Int)

）