In the paper titled "The Zipper" by Huet, he also mentions scars as a variation of zippers. Compared to zippers, which became pretty well known in the Haskell community, scars are pretty much unheard of. There is very little information about them in the paper itself and anywhere on the internet from what I could find.
So I have to ask, are they just not useful at all or is there something they are useful for, but most people just don't know about them?
It's just a minor adjustment to the tree type to make certain operations more efficient.
The paper focuses (ha ha) on rose trees - trees whose nodes have an arbitrary number of children. The code from the paper is in OCaml but translating it to Haskell doesn't require much adjustment:
data Rose a = Leaf a | Rose [Rose a]
To briefly recap, the idea of zippers is to represent a position in a data structure by its context. The context of a node in a rose tree consists of the path you took down the tree to reach the node's parent, and the path you took along the list of siblings to reach the node itself.
data Path a = Top | Node (Path a) [Rose a] [Rose a]
data Pos a = Pos { focus :: Rose a, path :: Path a }
This allows you to zoom in on a position in a tree without forgetting where you've been by walking right and down, and then rebuild the tree by retreating left and zooming out 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
Look at the definition of up. It takes t, l, and r - the currently focused node and its siblings - and smashes them together into a single list of children. It forgets which node you were looking at. Accordingly, down focuses you on the left-most child of the current focus. If you need to go up and then back down to the previously focused node you have to walk right along the list back to where you were, which is an O(n) operation.
Huet's idea of leaving 'scars' in the tree is about making it more convenient to return to a previously focused child. He equips the Rose constructor with a focus of its own, replacing the list of children with a list zipper.
data SRose a = -- for "scarred rose"
SLeaf a
| SEmpty -- replaces (Rose [])
| SRose [SRose a] (SRose a) [SRose a]
The Path and Pos types remain unchanged:
data SPath a = STop | SNode (SPath a) [SRose a] [SRose a]
data SPos a = SPos { sfocus :: Rose a, spath :: SPath a }
Now, when you go up and then back down, you don't forget what you were previously looking at.
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)
© 2022 - 2024 — McMap. All rights reserved.