来访的每个节点 [英] visiting each node

问题描述

我有一个爱好项目，该项目是关于建立一个树来储存识别号码。我已经使用的数字，存储在节点，也就是节点可以是0 1 2 3 4 5 6 7 8 9

I have a hobby project which is about creating a tree to store identification numbers. I had used digit, stored at node, that is node can be 0 1 2 3 4 5 6 7 8 9.

在我创建的树，我想从树上组成名单。但是，我无法找到一个算法来管理我的目标。

After I have create tree, I want compose list from tree. But, I could not find a algorithm to manage my goal.

我想：

      "recompose tree"  will return list of numbers. For below tree it should be 

            [ 2, 21, 243, 245, 246, 78, 789 ]  


                               Root 
                           /          \         
                        2*               7
                      /      \             \                  
                   1*         4              8*    
                            / \  \            \         
                           3*  5* 6*           9*

       my data type :  data ID x = ID ( ( x, Mark ), [ ID x ] ) 
                       data Mark = Marked | Unmarked

       EDIT:

       for convenience : * shows it is marked
                         I have stored digit as char, actually not 1, 
                            it is stored as'1' 

你有建议我怎么能做到这一点？ （建议是pfferred是算法$ P $）

Do you have advice how I can do that ? ( advice is prefferred to be algorithm )

推荐答案

什么

recompose :: Num a => ID a -> [a]
recompose = go 0
  where
    go acc (ID ((n, Marked), ids)) =
      let acc' = 10 * acc + n
      in  acc' : concatMap (go acc') ids
    go acc (ID ((n, Unmarked), ids)) =
      let acc' = 10 * acc + n
      in  concatMap (go acc') ids

这就是我们遍历树，同时积累了从根的路径节点的值。在每一个节点，我们通过乘以10的路径值，并增加了对节点给它的值更新累加器。遍历产生了显着的节点，所有累加器值的列表：那么，在明显的节点，我们累加器值添加到列表中，未标记的节点，我们只是宣传，我们已经收集了节点的子节点列表

That is, we traverse the tree while accumulating a value for the path from the root to a node. At every node we update the accumulator by multiplying the value for the path by 10 and adding the value for the node to it. The traversal produces a list of all accumulator values for marked node: so, at marked node we add the accumulator value to the list, for unmarked nodes we just propagate the list that we have collected for the children of the node.

我们如何计算列表中一个节点的孩子？我们通过递归过来的孩子的名单映射调用穿越功能（去）的所有儿童。这给了我们，我们串联，以获得一个列表中列出的清单。 （ concatMap˚FXS 只是 CONCAT（映射f XS））或 CONCAT。映射f ）

How do we compute the list for the children of a node? We recursively call the traversal function (go) to all children by mapping it over the list of children. That gives us a list of lists that we concatenate to obtain a single list. (concatMap f xs is just concat (map f xs)) or concat . map f.)

在属性语法术语：累加器作为一个继承的属性，而返回的列表是一个综合属性

In attribute-grammar terminology: the accumulator serves as an inherited attribute, while the returned list is a synthesised attribute.

作为一个细化，我们可以引入一个辅助功能 ISMARKED ，

As a refinement, we can introduce an auxiliary function isMarked,

isMarked :: Mark -> Bool
isMarked Marked   = True
isMarked Unmarked = False

这样我们就可以简洁地写

so that we can concisely write

recompose :: Num a => ID a -> [a]
recompose = go 0
  where
    go acc (ID ((n, m), ids)) =
      let acc'   = 10 * acc + n
          prefix = if isMarked m then (acc' :) else id
      in  prefix (concatMap (go acc') ids)

这篇关于来访的每个节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！