在 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

这里你可能需要的是某种累加器：一个你通过递归调用传递的变量，每次你递增"assign"下一个id.

因此，我们根据辅助函数 go 来定义我们的函数。 go 将 return 一个 2 元组："labeled" 树，以及我们将 "dispatch" 的下一个 ID。这将在以后使用，因为我们定义了一个递归调用：

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

所以 go 的类型是 Int -> Tree a -> (Int, Tree (a, Int))。如果我们看到 Leaf，我们因此 "dispatch" 那个 id，然后 return 那片叶子，连同 n + 1 作为元组的第二部分，比如：

go (Leaf x) n = (Leaf (x, n), n+1)

对于一个节点，我们会先将ids派发到左子树，然后以该元组的第二项为开始，将元素派发到右子树，如：

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标记的左子树，n1新号码稍后发送。我们调用 go r n1，因此我们将数字分派到以 n1 开头的右子树。因此，我们的 go 函数 return 是一个带有标记子树的新 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 2

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

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 使用当前状态并更新下一个叶子的状态。

（请注意，这与非常相似。鉴于 State s a 实际上是 s -> (a, s) 类型函数的包装器，labelTree' :: Tree a -> State Int (Tree (a, Int), Int) 的类型可以是哄成与 go:

相同的类型

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

)

Answer 3

我和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 4

这是快速粗略的版本：

{-# language DeriveTraversable #-}

import Data.Traversable (mapAccumL)

data Tree a
  = Leaf a
  | Node (Tree a) (Tree a)
  deriving (Functor, Foldable, Traversable)

labelTree :: Tree a -> Tree (a, Int)
labelTree = snd .
  mapAccumL (\k a -> (k+1, (a, k))) 1

不幸的是，这可能有点太懒了，一般来说效率不高。我仍在努力弄清楚如何在这里达到懒惰的最佳状态。

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

Number all occurring leaves in a tree from left to right in Haskell

tree

binary-tree

haskell

traversal

tree-traversal