什么是伤疤有用？

Question

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

所以我不得不问,它们根本没有用,或者它们是否有用,但大多数人只是不了解它们？

Answer 1

它只是对树类型的一个小调整,以使某些操作更有效.

本文重点关注(哈哈)玫瑰树 - 树木的节点有任意数量的孩子.该论文的代码在OCaml中,但将其转换为Haskell并不需要太多调整:

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

简而言之,拉链的概念是通过其上下文来表示数据结构中的位置.玫瑰树中节点的上下文包括从树中获取到达节点父节点的路径,以及沿着兄弟节点列表到达节点本身的路径.

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- 当前关注的节点及其兄弟姐妹 - 并将它们一起粉碎成一个单独的孩子列表.它会忘记您正在查看的节点.因此,请down关注当前焦点的最左侧孩子.如果您需要先up返回到先前关注的节点,则必须right沿着列表返回到您所在的位置,这是一个O(n)操作.

Huet关于在树中留下"伤疤"的想法是让回到以前专注的孩子更方便.他为Rose构造函数配备了自己的焦点,用列表拉链替换了子列表.

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)