2

我正在阅读 Haskell Wiki 中的Zipper 文章，但我无法理解up定义为的方法：

data Tree a = Fork (Tree a) (Tree a) | Leaf a

data Cxt a = Top | L (Cxt a) (Tree a) | R (Tree a) (Cxt a)

type Loc a = (Tree a, Cxt a)

up :: Loc a -> Loc a
up (t, L c r) = (Fork t r, c)
up (t, R l c) = (Fork l t, c)

在模式up (t, L c r)中，t是有焦点的子树，c是当前焦点处有洞的上下文，向上移动时，为什么c不向上移动但仍然引用旧上下文？焦点不应该也上去吗？

4

1 回答 1

2

在

up (t, L c r) = (Fork t r, c)

不是c当前上下文，而是L c r。上下文描述了从当前树到根的路径。形式的上下文L c r起源于下降到左子树，因此为了向上一层，我们必须将它与相应的右子树结合起来r。这c是到根的剩余路径，因此成为新的上下文。

让我们看一个小例子：假设你有一棵看起来像这样的树：

   *
  / \
 /   \
/ \ / \
1 2 3 4

它将使用Tree类型表示为

tree = Fork (Fork (Leaf 1) (Leaf 2))
            (Fork (Leaf 3) (Leaf 4))

现在在树中选择的位置Leaf 3如下所示：

loc3 = (Leaf 3, L (R (Fork (Leaf 1) (Leaf 2)) Top) (Leaf 4))

请注意，这里的上下文是形式

L c (Leaf 4)

表示在从当前节点向上的路径上，您位于父节点的左子树中，对应的右子树为Leaf 4. 这c是剩余步骤的上下文，在这种情况下，树Fork (Leaf 3) (Leaf 4)实际上是完整树的右子树。

于 2014-03-19T16:03:10.303 回答