解释Haskell广度第一个编号代码来遍历树

Question

我正在阅读Chris Okasaki撰写的这篇论文 ; 标题为"广度优先编号:算法设计中小练习的教训".

问题是 - 算法中的魔法是怎么发生的？有一些数字(例如图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。知道了这一点，我们可以将这样的大小列表从左到右穿过给定的树（子树）：我们将列表的第一个元素前进 1节点，并将列表的尾部首先穿过左子树，然后穿过右子树（见thread下文）。

这样做之后，我们将再次获得相同的大小列表，仅移动一位 - 现在我们得到了每个级别之后的元素总数。所以技巧是：假设我们有这样一个列表，用它进行计算，然后将输出作为输入 -打结。

示例实现：

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作为函数给出的编号）。