解释哈斯克尔广度优先编号code遍历树 [英] explain the Haskell breadth first numbering code to traverse trees

问题描述

我读本文由克里斯· Okasaki ;标题为广度优先编号：教训从一个小练习在算法设计

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，认识到这一点，我们就可以通过一个给树（子树）左到右螺纹尺寸的这样一个清单：我们推进列表的第一元件由一个为节点，首先通过左，然后通过右子树（见线程以下）。

这样做之后，我们又得到大小相同的列表中，只有移位一个 - 的每个水平，现在我们有元素总数的。因此，关键是：假设我们有这样一个清单，用它来计算，再喂输出作为输入 - 喜结良缘。

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')

推广到含半幺群（的编号，你想给常量$总和1 的功能）。

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

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