haskell - Data.Tree.Zipper 中 zipper 数据类型的冗余信息？

Question

在 Data.Tree.Zipper 中，玫瑰树的 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 字段中。 (节点的兄弟节点是其 parent 的 child 。)

这是为什么呢？出于方便？

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 作为异常(exception)，因为我确切地知道我们正在处理什么树):

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 下降，该标签没有左 sibling ，并且两个右 sibling 。第二个条目表示根具有标签 1。