疤痕有什么用？

Question

在 Huet 的题为 "The Zipper" 的论文中，他还提到疤痕是拉链的一种变体。与在 Haskell 社区中广为人知的拉链相比，疤痕几乎闻所未闻。在论文本身和互联网上的任何地方，我能找到的关于它们的信息很少。

所以我不得不问，它们是根本没有用，还是有什么用处，但大多数人只是不知道它们？

Answer 1

这只是对树类型的一个小调整，以提高某些操作的效率。

本文重点（哈哈）玫瑰树——节点具有任意数量children的树。论文中的代码在 OCaml 中，但将其转换为 Haskell 不需要太多调整：

data Rose a = Leaf a | Rose [Rose a]

简单回顾一下，zippers 的思想是通过 context 表示数据结构中的 position。玫瑰树中节点的上下文包括您沿着树向下到达节点 parent 的路径，以及您沿着兄弟节点列表到达节点本身的路径。

data Path a = Top | Node (Path a) [Rose a] [Rose a]

data Pos a = Pos { focus :: Rose a, path :: Path a }

这使您可以通过 right 和 down 步行放大树中的某个位置而不会忘记您去过的地方，然后通过后退 left 重建树并缩小 up.

right, down, left, up :: Pos a -> Maybe (Pos a)
right (Pos _ Top) = Nothing
right (Pos _ (Node _ _ [])) = Nothing
right (Pos t (Node p ls (r:rs))) = Just $ Pos r (Node p (t:ls) rs)

down (Pos (Leaf _) _) = Nothing
down (Pos (Rose []) _) = Nothing
down (Pos (Rose (t:ts)) p) = Just $ Pos t (Node p [] ts)

left (Pos _ Top) = Nothing
left (Pos _ (Node _ [] _)) = Nothing
left (Pos t (Node p (l:ls) rs) = Just $ Pos l (Node p ls (t:rs))

up (Pos _ Top) = Nothing
up (Pos t (Node p l r)) = Just $ Pos (Rose (l ++ t:r)) p

看up的定义。它需要 t、l 和 r - 当前聚焦的节点及其兄弟节点 - 并将它们粉碎到一个 children 的列表中。它会忘记您正在查看哪个节点。因此，down 将您聚焦在当前焦点的 left-most child 上。如果您需要转到 up 然后返回到先前聚焦的节点，您必须沿着列表 right 返回到您所在的位置，这是一个 O(n)操作。

Huet 将 'scars' 留在树中的想法是为了让 return 更方便地转到先前关注的 child。他为 Rose 构造函数配备了自己的焦点，用列表拉链替换了 children 的列表。

data SRose a =  -- for "scarred rose"
      SLeaf a
    | SEmpty  -- replaces (Rose [])
    | SRose [SRose a] (SRose a) [SRose a]

Path和Pos类型保持不变：

data SPath a = STop | SNode (SPath a) [SRose a] [SRose a]
data SPos a = SPos { sfocus :: Rose a, spath :: SPath a }

现在，当您去 up 然后返回 down 时，您不会忘记之前看过的内容。

up' (SPos _ STop) = Nothing
up' (SPos t (SNode p l r)) = Just $ SPos (SRose l t r) p

down' (SPos (SLeaf _) _) = Nothing
down' (SPos SEmpty _) = Nothing
down' (SPos (SRose l t r) p) = Just $ SPos t (SNode p l r)

疤痕有什么用？

What are scars useful for?

haskell

zipper