Data.Tree.Zipper中拉链数据类型中的冗余信息？

Question

在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字段中。(节点的兄弟姐妹是其父母的子女。)

为什么会这样呢？为了方便？

Answer 1

没有多余的信息。_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
                 , []
                 )
               ]
  }

你可以看到：

• _contents按预期在标签6处包含选定的子树，
• _before包含左边的直接兄弟姐妹(按相反的顺序)，
• _after包含右边的直接兄弟姐妹，
• _parents是一个包含两个条目的列表，因为所选树上有两个级别，因此它描述了从所选子树到顶部的路径。第一个条目说，我们通过标签2下降，该标签没有左兄弟姐妹和两个右兄弟姐妹。第二个条目说根目录有标签1。

Answer 2

谢谢你的详细解释！

我感到困惑的原因是如果你把玫瑰树的数据类型

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中的最后一个元素总是包含两个空列表，因此仍然包含一些冗余信息:-)