haskell - 疤痕有什么用？

Question

在 Huet 题为“拉链”的论文中，他还提到疤痕是拉链的一种变体。与在 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)