Dragkedja (datastruktur)

En blixtlås är en teknik för att representera en aggregerad datastruktur så att det är bekvämt att skriva program som går igenom strukturen godtyckligt och uppdaterar dess innehåll, särskilt i rent funktionella programmeringsspråk . Dragkedjan beskrevs av Gérard Huet 1997. Den inkluderar och generaliserar gapbufferttekniken som ibland används med arrayer.

Blixtlåstekniken är generell i den meningen att den kan anpassas till listor , träd och andra rekursivt definierade datastrukturer. Sådana modifierade datastrukturer hänvisas vanligtvis till som "ett träd med blixtlås" eller "en lista med blixtlås" för att betona att strukturen begreppsmässigt är ett träd eller en lista, medan blixtlåset är en detalj av implementeringen.

En lekmans förklaring till ett träd med blixtlås skulle vara ett vanligt datorfilsystem med operationer för att gå till förälder (ofta cd .. ), och möjlighet att gå nedåt ( cd underkatalog ). Blixtlåset är pekaren till den aktuella vägen. Bakom kulisserna är blixtlåsen effektiva när man gör (funktionella) ändringar i en datastruktur, där en ny, något ändrad, datastruktur returneras från en redigeringsoperation (istället för att göra en förändring i den nuvarande datastrukturen).

Exempel: Dubbelriktad listövergång

Många vanliga datastrukturer inom datavetenskap kan uttryckas som den struktur som genereras av ett fåtal primitiva konstruktoroperationer eller observatörsoperationer. Dessa inkluderar strukturen av ändliga listor, som kan genereras av två operationer:

Empty skapar en tom lista,
Cons(x, L) konstruerar en lista genom att lägga till eller sammanfoga värdet x framför lista L .

En lista som [1, 2, 3] är därför deklarationen Cons(1, Cons(2, Cons(3, Empty))) . Det är möjligt att beskriva platsen i en sådan lista som antalet steg från framsidan av listan till målplatsen. Mer formellt är en plats i listan antalet Nackdelar som krävs för att rekonstruera hela listan från den specifika platsen. Till exempel, i Cons(1, Cons(2, Cons( X, Cons(4, Empty)))) skulle en Cons(2, L) och en Cons(1, L) operation krävas för att rekonstruera listan i förhållande till position X annars känd som Cons( X, Cons(4, Empty)) . Denna inspelning tillsammans med platsen kallas en zippad representation av listan eller en list-dragkedja.

För att vara tydlig är en plats i listan inte bara antalet nackdelar , utan även all annan information om dessa nackdelar ; i detta fall de värden som måste återanslutas. Här kan dessa värden lämpligen representeras i en separat lista i appliceringsordning från målplatsen. Specifikt, från sammanhanget "3" i listan [1, 2, 3, 4] kan en inspelning (vanligen kallad "sökväg") representeras som [2, 1] där Cons(2, L) tillämpas följt av (Cons 1, L) för att återskapa den ursprungliga listan med början från [3, 4] .

En list-dragkedja representerar alltid hela datastrukturen. Denna information är dock från en specifik plats inom den datastrukturen. Följaktligen är en list-dragkedja ett par som består av både platsen som en kontext eller startpunkt, och en inspelning eller väg som tillåter rekonstruktion från den startplatsen. Speciellt kan listdragkedjan för [1, 2, 3, 4] vid platsen för "3" representeras som ([2, 1], [3, 4]) . Nu, om "3" ändras till "10", så blir listlåset ([2, 1], [10, 4]) . Listan kan sedan rekonstrueras effektivt: [1, 2, 10, 4] eller andra platser som korsas till.

Med listan representerad på detta sätt är det lätt att definiera relativt effektiva operationer på oföränderliga datastrukturer som listor och träd på godtyckliga platser. Särskilt, applicering av blixtlåstransformeringen på ett träd gör det enkelt att infoga eller ta bort värden på någon speciell plats i trädet.

Sammanhang och differentiering

Typen av ett blixtlåss sammanhang kan konstrueras via en transformation av originaltypen som är nära relaterad till derivatan av kalkyl genom dekategorisering . De rekursiva typerna som blixtlås bildas av kan ses som den minst fixerade punkten av en unär typkonstruktör $*\rightarrow *$ . Till exempel, med en högre ordningens typkonstruktor ${\text{lfp}}:(*\rightarrow *)\rightarrow *$ som konstruerar den minst fixerade punkten i dess argument, ett omärkt binärt träd kan representeras som ${\text{lfp}}(T\mapsto T^{2}+1)$ och en omärkt lista kan ha formen ${\text{lfp}}(T\mapsto T+1)$ . Här motsvarar notationen av exponentiering, multiplikation och addition funktionstyper , produkttyper respektive summatyper , medan de naturliga talen betecknar de finita typerna ; på detta sätt liknar typkonstruktörerna polynomfunktioner i $\mathbb {N} \rightarrow \mathbb {N}$ .

Derivatan av en typkonstruktor kan därför bildas genom denna syntaktiska analogi: för exemplet med ett omärkt ternärt träd, derivatan av dess typkonstruktor ( $\displaystyle (T\mapsto T^{3 }+1)'}$ skulle vara ekvivalent med $T\mapsto 3\times T^{2}$ , analogt med användningen av summa- och potensreglerna i differentialkalkyl. Typen av sammanhangen för ett blixtlås över en originaltyp ${\text{lfp}}(f)$ är ekvivalent med derivatan av typkonstruktorn som tillämpas på originaltypen, $f'({\text{lfp}}(f))$ .

Som illustration, betrakta den rekursiva datastrukturen för ett binärt träd med noder som antingen är vaktpostnoder av typ 1 eller innehåller ett värde av typ $A$ :

{\text{BTree}}:={\text{lfp}}(T\mapsto A\times T^{2}+1)

Den partiella derivatan av typkonstruktorn kan beräknas vara

(T\mapsto A\times T^{2}+1)'=T\mapsto 2\times A\times T

Därmed är typen av blixtlåsets sammanhang

(T\mapsto 2\times A\times T)({\text{BTree}})=2\times A\times { \text{BTree}}

Som sådan finner vi att sammanhanget för varje icke-sentinel barnnod i det märkta binära trädet är en trippel bestående av

ett booleskt värde av typ 2 , som uttrycker om den aktuella noden är vänster eller höger underordnad till sin föräldernod;
ett värde av typ $A$ , etiketten för den nuvarande nodens överordnade; och
nodens syskon av typen $BTree$ , underträdet som finns i den andra grenen av den aktuella nodens överordnade.

I allmänhet består ett blixtlås för ett träd av typen ${\text{lfp}}(f)$ av två delar: en lista med sammanhang av typen $f'({\text{lfp}}(f))$ för den aktuella noden och var och en av dess förfäder fram till rotnoden, och värdet av typen ${\text{lfp}}( f)$ som den aktuella noden innehåller.

Används

Dragkedjan används ofta där det finns något koncept av fokus eller att flytta runt i någon uppsättning data, eftersom dess semantik återspeglar den att flytta runt men på ett funktionellt icke-förstörande sätt.

Dragkedjan har använts i

Xmonad , för att hantera fokus och placering av fönster
Huets tidningar täcker en strukturell redaktör baserad på dragkedjor och en teoremprovare
Ett filsystem (ZipperFS) skrivet i Haskell som erbjuder "...transaktionell semantik; ångra alla fil- och katalogoperationer; ögonblicksbilder; statiskt garanterat det starkaste, repeterbara läsläget, isoleringsläget för klienter; genomgripande kopiering-på-skriv för filer och kataloger; inbyggd genomgångsfunktion; och precis rätt beteende för cykliska katalogreferenser."
Clojure har omfattande stöd för dragkedjor.

Alternativ och förlängningar

Direkt modifiering

I ett icke-rent-funktionellt programmeringsspråk kan det vara bekvämare att helt enkelt gå igenom den ursprungliga datastrukturen och modifiera den direkt (kanske efter djupkloning, för att undvika att påverka annan kod som kan innehålla en referens till den).

Generisk dragkedja

Den generiska blixtlåset är en teknik för att uppnå samma mål som den konventionella blixtlåset genom att fånga tillståndet för korsningen i en fortsättning när man besöker varje nod. (Haskell-koden som ges i referensen använder generisk programmering för att generera en genomgångsfunktion för vilken datastruktur som helst, men detta är valfritt – vilken lämplig genomgångsfunktion som helst kan användas.)

Det generiska blixtlåset innebär dock invertering av kontroll , så vissa användningar av det kräver en tillståndsmaskin (eller motsvarande) för att hålla reda på vad som ska göras härnäst.

Vidare läsning

Huet, Gerard (september 1997). "Functional Pearl: The Zipper" (PDF) . Journal of Functional Programming . 7 (5): 549–554. doi : 10.1017/s0956796897002864 .
Hinze, Ralf; Jeuring, Johan; Löh, Andres (maj 2004). "Typindexerade datatyper" . Vetenskap om datorprogrammering . 51 (1–2): 117–151. doi : 10.1016/j.scico.2003.07.001 .

externa länkar