解释 Haskell 广度优先编号代码以遍历树 [英] explain the Haskell breadth first numbering code to traverse trees

问题描述

我正在阅读 克里斯的这篇论文冈崎;标题为广度优先编号:算法设计小练习的经验教训".

I am reading this paper by Chris Okasaki; titled "Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design".

一个问题是 - 算法中的魔法是如何发生的?有一些数字(例如，标题为将一个级别的输出线程化到下一个级别的输入"的图 7)不幸的是，也许只有我，但那个数字已经完全让我感到困惑.我根本不明白线程是如何发生的?

A question is - how is the magic happening in the algorithm? There are some figures (e.g. figure 7 titled "threading the output of one level into the input of next level") Unfortunately, maybe it's only me, but that figure has completely baffled me. I don't understand how the threading happens at all?

推荐答案

广度优先遍历意味着逐层遍历树.所以让我们假设我们已经知道每个级别开始时的数字是多少 - 在每个级别之前遍历元素的数量.对于论文中的简单例子

Breadth first traversal means traversing levels of a tree one by one. So let's assume we already know what are the numbers at the beginning of each level - the number of traversed elements so far before each level. For the simple example in the paper

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)将列表的尾部线程化.

the sizes would be 0, 1, 3, 4. Knowing this, we can thread such a list of sizes through a give tree (sub-tree) left-to-right: We advance the first element of the list by one for the node, and thread the tail of the list first through the left and then through the right subtree (see thread below).

这样做之后，我们将再次获得相同的大小列表，只是移动了一个 - 现在我们拥有每个级别之后的元素总数.所以诀窍是:假设我们有这样一个列表，将它用于计算，然后将输出作为输入提供 - 打结.

After doing so, we'll get again the same list of sizes, only shifted by one - now we have the total number of elements after each level. So the trick is: Assume we have such a list, use it for the computation, and then feed the output as the input - 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 作为函数).

generalized to Monoid (for numbering you'd give const $ Sum 1 as the function).

这篇关于解释 Haskell 广度优先编号代码以遍历树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！