Zipper (struktura podataka)

Zatvarač (en. zipper) je tehnika koja predstavlja jedinstvenu strukturu podataka, tako da je pogodan za pisanje programa koji proizvoljno prolaze kroz strukturu i ažuriraju svoje sadržaje, naročito u čisto funkcionalnim programskim jezicima. Zatvarač je opisao Žerar Huet 1997. godine^[1]. To uključuje i generalizuje gep bafer tehniku koja se ponekad koristi sa nizovima.

Tehnika zatvarača se u potpunosti može prilagođavati listama, stablima i drugim rekurzivno definisanim strukturama podataka. Takve modifikovane strukture podataka se obično nazivaju "drvo sa zatvaračem" ili "liste sa zatvaračem" da bi se naglasilo da je konceptualno struktura stablo ili lista, dok je zatvarač način implementacije.

Objašnjenje laik za "stablo sa zatvaračem" bi bio običan računarski sistem datoteka sa operacijama vrat se na roditelja (najčešće cd ..), i mogućnost da se pređe na potfolder (cd subdirectory). Zatvarač je pokazivač trenutnog puta. Iza scene, patent zatvarači su efikasni u donošenju funkcionalnih promena u strukturi podataka.

Primer: Obilazak liste u oba smera

Mnogi poznate strukture podataka u kompjuterskim naukama mogu se izraziti kao struktura generisane od strane nekoliko primitivnih konstruktorskih ili observerskih operacija. One uključuju strukturu konačnih listi koje mogu biti generisane od strane sledeće dve operacije:

Empty - Konstruiše praznu listu
Insert(x, L) - Konstruiše listu ubacujući vrednost h na početak liste L

Tako bi lista [1, 2, 3] bila konstruisana komandom Insert(1, Insert(2, Insert(3, Empty))). Moguće je pronaći lokaciju neke vrednosti kao broj koraka od formiranja frontalne vrednosti liste do formiranja te vrednosti. Formalnije, lokacija predstavlja broj dodatih Insert operacija koje konstruišu celu listu nakon što je data vrednost dodata u listu.

Koncept lokacije na listi je implementiran snimanjem ne samo broja puta iskorišćenih Insert opcija, već i čuvanjem ostalih informacija - kao npr. vrednosti koja je uneta. One su sačuvane u odvojenoj listi čiji redosled je obrnut od redosleda originalne strukture podataka. Naime, član "3" na listi [1, 2, 3] je predstavljen kao [2, 1]. Lista sa zatvaračem predstavlja čitavu strukturu i lokacije unutar strukture.

Sa listom predstavljenom na ovaj način, lako je definisati efikasne operacije koje se kreću napred ili nazad po listi i manipulišu listom na toj lokaciji, na primer ubacivanja ili izbacivanjem članova liste. Slično tome, primena transformacija zatvarača na stablo olakšava umetanja ili brisanj vrednosti na određenoj lokaciji u stablu.

Upotreba

Zatvarač se često koristi kada postoji neki koncept "fokusa" ili kretanja kroz neki skup podataka. Zatvarač se koristi u:

Xmonad, upravlja fokusom i pozicioniranjem prozora
Računarski sistem datoteka (ZipperFS) napisan u Haskell-y nudi "... transakcionu semantiku; poništavanje operacija nad datotekama i direktorijumima; mehanizam snapshot-a; garantovano najjači statički režim izolacije klijenta, sa sposobnostima ponavljanja čitanja; pravilno ponašanje referenci cikličnih direktorijuma."^[2]
Clojure ima proširenu podršku za zatvarač^[3]

Kontekst zatvarača i njegova diferencijacija

Pokazalo se da je tip svakog člana liste proizvedene od strane zatvarača "derivat" originalne strukture u smislu da je dekategorizacijom povezan sa diferencijacijom u infinitezimalnom računu. Mnogi tipovi su napravljeni od prpizvoda i zbirova drugih tipova; mnoge strukture izgledaju kao polinom ili Tejlorov razvoj, a reprezentacija člana liste izgleda kao derivat polinoma ili razvoja.^[4]^[5]

Razmotrimo rekurzivni tip podataka poput stabla čiji su čvorovi tipa A:

T(A,R)=1+A\cdot R^{2}

Ovo stablo se sastoji od trostruke vrednosti tipa A i dva podstabla tipa R, tako da dobijamo:

{\frac {dT(A,R)}{dR}}=A\cdot 2\cdot R.

U suštini, zatvarač tipa T parametrizovan nekim drugim tipom A i rekurzivnom konstantom R, sastoji se iz dva dela: liste tipa ${\frac {dT(A,R)}{dR}}|_{R=T(A,R)}$ i kopije silazne liste $T(A,R)|_{R=T(A,R)}.$ .

Alternative i ekstenzije

Direktne moifikacije

U ne-čisto-funkcionalni programskim jezicima, možda bi bilo zgodnije da se jednostavno prolaze kroz originalnu strukturu podataka i da se ona modifikuje direktno (verovatno posle kopiranja objekta, kako bi se izbegli sukobi sa ostatkom koda koji bi imali referencu na taj objekat).

Generički zatvarač

Generički zatvarač je tehnika koja ima isti cilj kao običan zatvarač, da zabeleži stanje čvorova tokom obilaska svih čvorova. Generički zatvarač uključujr i kontrolu inverza, tako da se pri nekim upotrebama zahtevaju informacije o stanju mašine kako bi se predvideo sledeći korak.

Reference

^ Huet 1997
^ Generic Zipper: the context of a traversal
^ jafingerhut (22. 10. 2010). „clojure.zip/zipper”. ClojureDocs. Pristupljeno 15. 6. 2013.
^ Joyal, André (1981), "Une théorie combinatoire des séries formelles", Advances in Mathematics 42:1-82.
^ McBride, Conor (2001). „The Derivative of a Regular Type is its Type of One-Hole Contexts”. CiteSeerX 10.1.1.22.8611  .

Literatura

Huet, Gerard (1997). „Functional Pearl: The Zipper” (PDF). Journal of Functional Programming. 7 (5): 549—554. S2CID 31179878. doi:10.1017/s0956796897002864.
Hinze, Ralf; et al. „"Type-indexed data types"”. CiteSeerX 10.1.1.1.6342  . . 23 July 2003

Spoljašnje veze

[1] Huet 1997

[2] Generic Zipper: the context of a traversal

[3] rhut (22. 10. 2010). „clojure.zip/zipper”. ClojureDocs. Pristupljeno 15. 6. 2013.

[4] Joyal, André (1981), "Une théorie combinatoire des séries formelles", Advances in Mathematics 42:1-82.

[5] McBride, Conor (2001). „The Derivative of a Regular Type is its Type of One-Hole Contexts”. CiteSeerX 10.1.1.22.8611  .

[1]

[2]

[3]

[4]

[5]