algorithm - 解释遍历树的Haskell广度优先编号代码

Question

我正在阅读 this paper by Chris Okasaki ;标题为“广度优先编号:算法设计中的小练习的教训”。

问题是 - 算法中的魔法是如何发生的？有一些数字(例如标题为“threading the output of one level into input of next level”的图 7)不幸的是，也许只有我一个人，但那个数字让我完全莫名其妙。我根本不明白线程是如何发生的？

Answer 1

广度优先遍历意味着逐层遍历树。因此，让我们假设我们已经知道每个级别开始时的数字是多少——到目前为止在每个级别之前遍历的元素的数量。对于论文中的简单例子

import Data.Monoid

data Tree a = Tree (Tree a) a (Tree a)
            | Empty
  deriving (Show)

example :: Tree Char
example = Tree (Tree Empty 'b' (Tree Empty 'c' Empty)) 'a' (Tree Empty 'd' Empty)

大小将是 0、1、3、4。知道这一点，我们可以将这样的大小列表从左到右穿过给定树(子树):我们将列表的第一个元素推进一个用于节点，首先将列表的尾部穿过左子树，然后穿过右子树(参见下面的 thread)。

这样做之后，我们将再次获得相同的尺寸列表，只是移动了一个 - 现在我们有了每个级别之后的元素总数。所以诀窍是:假设我们有这样一个列表，用它来计算，然后将输出作为输入 - tie the knot .

示例实现:

tagBfs :: (Monoid m) => (a -> m) -> Tree a -> Tree m
tagBfs f t = let (ms, r) = thread (mempty : ms) t
              in r
  where
    thread ms Empty = (ms, Empty)
    thread (m : ms) (Tree l x r) =
        let (ms1, l') = thread ms l
            (ms2, r') = thread ms1 r
         in ((m <> f x) : ms2, Tree l' m r')

泛化为 Monoid(对于编号，您可以将 const $ Sum 1 作为函数)。