Wofür sind Narben nützlich?

Question

In dem Artikel mit dem Titel "The Zipper" von Huet erwähnt er auch Narben als eine Variation von Reißverschlüssen. Verglichen mit Reißverschlüssen, die in der Haskell Community ziemlich bekannt wurden, sind Narben ziemlich unbekannt. Es gibt sehr wenig Informationen über sie in der Zeitung selbst und irgendwo im Internet von dem, was ich finden konnte.

Also muss ich fragen, sind sie überhaupt nicht nützlich oder gibt es etwas, für das sie nützlich sind, aber die meisten Leute wissen einfach nichts über sie?

Answer 1

Es ist nur eine kleine Anpassung an den Baumtyp, um bestimmte Operationen effizienter zu machen.

Das Papier konzentriert sich (ha ha) auf Rosenbäume - Bäume, deren Knoten eine beliebige Anzahl von Kindern haben. Der Code aus dem Papier ist in OCaml, aber es ist sehr einfach zu Haskell übersetzen:

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

Um kurz rekapituliert, ist die Idee der Reißverschluss durch seinen Kontext eine Position in einer Datenstruktur darzustellen. Der Kontext eines Knotens in einem Rosenbaum besteht aus dem Pfad, den Sie zum Erreichen des übergeordneten Elements des Knotens verwendet haben, und dem Pfad, den Sie entlang der Liste der Geschwister genommen haben, um den Knoten selbst zu erreichen.

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

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

Auf diese Weise können Sie in einem Baum auf eine Position, um es zu vergrößern, ohne zu vergessen, wo man zu Fuß right und down ist, und dann den Baum wieder aufbauen durch left Rückzug und up Auszoomen.

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 

Blick auf die Definition von up. Es dauert t, l und r - der aktuell fokussierte Knoten und seine Geschwister - und zerschlägt sie zusammen in einer einzigen Liste von Kindern. Es vergisst, auf welchem ​​Knoten Sie gesucht haben. Dementsprechend konzentriert sich down auf das unterste Kind des aktuellen Fokus. Wenn Sie up und dann zurück zum zuvor fokussierten Knoten gehen müssen, gehen Sie right entlang der Liste zurück zu dem, wo Sie waren, was ein O (n) Betrieb ist.

Huets Idee, Narben im Baum zu hinterlassen, besteht darin, es einfacher zu machen, zu einem zuvor fokussierten Kind zurückzukehren. Er stattet den Konstruktor Rose mit einem eigenen Fokus aus und ersetzt die Liste der Kinder mit einem Listen-Zipper.

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

Die Path und Pos Typen bleiben unverändert:

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

Wenn Sie jetzt up gehen und dann zurück down, vergessen Sie nicht, was Sie zuvor ein Blick auf.

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)