2

在 Data.Tree.Zipper 中，玫瑰树的拉链数据类型是

data TreePos t a  = Loc
  { _content   :: t a        -- ^ The currently selected tree.
  , _before    :: Forest a
  , _after     :: Forest a
  , _parents   :: [(Forest a, a, Forest a)]
  } deriving (Read,Show,Eq)

现在在我看来，_after 和 _before 中的信息是多余的，因为它也应该显示在 _parents 字段中。（节点的兄弟姐妹是其父节点的子节点。）

为什么是这样？不方便？

4

2 回答 2

6

没有多余的信息。该_parents字段包含从焦点树到根的路径上的左右兄弟姐妹，但不包含直接兄弟姐妹。

让我们看一个具体的例子：

                               1
                               |
                    -----------------------
                    |          |          |
                    2          10         11
                    |                     |
              -------------             -----
              |  |  |  |  |             |   |
              3  4  5  6  9             12  13
                       |
                     -----
                     |   |
                     7   8

这棵树可以表示如下：

t = Node 1 [ Node 2  [ Node 3 []
                     , Node 4 []
                     , Node 5 []
                     , Node 6 [ Node 7 []
                              , Node 8 []
                              ]
                     , Node 9 []
                     ]
           , Node 10 []
           , Node 11 [ Node 12 []
                     , Node 13 []
                     ]
           ]

现在让我们下降到带有标签的子树6（我在fromJust这里作为一个例外使用，因为我确切地知道我们正在处理的是什么树）：

l = fromJust $ do
  node1 <- return (fromTree t)
  node2 <- childAt 0 node1
  node6 <- childAt 3 node2
  return node6

现在让我们检查结果位置：

Loc
  { _content = F (Node 6 [ Node 7 []
                         , Node 8 []
                         ]
               )
  , _before  = [ Node 5 []
               , Node 4 []
               , Node 3 []
               ]
  , _after   = [ Node 9 []
               ]
  , _parents = [ ( []
                 , 2
                 , [ Node 10 [], 
                     Node 11 [ Node 12 [],
                               Node 13 []
                   ]
                 )
               , ( []
                 , 1
                 , []
                 )
               ]
  }

你可以看到：

  • _contents6按预期包含标签处的选定子树，

  • _before包含左侧的直接兄弟姐妹（以相反的顺序），

  • _after包含右侧的直接兄弟姐妹，

  • _parents是一个包含两个条目的列表，因为在选定的树之上有两个层次，所以它描述了从选定的子树到顶部的路径。第一个条目说我们通过2没有左兄弟和两个右兄弟的标签下降。第二个条目说根有标签1。

于 2014-03-17T18:53:11.910 回答
0

感谢您非常详尽的解释！

我感到困惑的原因是，如果您采用玫瑰树的数据类型

data Rose x = Rose x [Rose x]

并取导数

R = x L(R(x))
R' = L(R) + x L' R'
R' = L(R) / (1 - x L')
R' = L(R) / (1 - x L^2)
R' = L(R) * L(x L^2)

这直接转换为拉链的以下数据类型

data TreePos t a  = Loc
  { _content   :: t a        -- ^ The currently selected tree.
  , _parents'  :: [(Forest a, a, Forest a)]
  } deriving (Read,Show,Eq)

在这种情况下，第一个元素_parents'包含有关焦点节点的兄弟姐妹的信息。
显然，两个版本应该是等价的。我只是漫不经心地假设_parents并_parents'持有完全相同的信息。不过，Data.Tree.Zipper 实现的一个小“缺点”：据我所知，最后一个元素_parents总是包含两个空列表，因此仍然有一些冗余信息:-)

于 2014-03-18T09:44:41.523 回答