Zipper (структура података)

Затварач (en. zipper) је техника која представља јединствену структуру података, тако да је погодан за писање програма који произвољно пролазе кроз структуру и ажурирајu своје садржаје, нарочито у чисто функционалним програмским језицима. Затварач је описао Жерар Хует 1997. године^[1]. То укључује и генерализује геп бафер технику која се понекад користи са низовима.

Техника затварача се у потпуности може прилагођавати листама, стаблима и другим рекурзивно дефинисаним структурама података. Такве модификоване структуре података се обично називају "дрво са затварачем" или "листе са затварачем" да би се нагласило да је концептуално структура стабло или листа, док је затварач начин имплементације.

Објашњење лаик за "стабло са затварачем" би био обичан рачунарски систем датотека са операцијама врат се на родителја (најчешће cd ..), и могућност да се пређе на потфолдер (cd subdirectory). Затварач је показивач тренутног пута. Иза сцене, патент затварачи су ефикасни у доношењу функционалних промена у структури података.

Пример: Обилазак листе у оба смера

Многи познате структуре података у компјутерским наукама могу се изразити као структура генерисане од стране неколико примитивних конструкторских или обсерверских операција. Оне укључују структуру коначних листи које могу бити генерисане од стране следеће две операције:

• Empty - Конструише празну листу
• Insert(x, L) - Конструише листу убацујући вредност х на почетак листе L

Тако би листа [1, 2, 3] била конструисана командом Insert(1, Insert(2, Insert(3, Empty))). Могуће је пронаћи локацију неке вредности као број корака од формирања фронталне вредности листе до формирања те вредности. Формалније, локација представља број додатих Insert операција које конструишу целу листу након што је дата вредност додата у листу.

Концепт локације на листи је имплементиран снимањем не само броја пута искоришћених Insert опција, већ и чуванјем осталих информација - као нпр. вредности која је унета. Оне су сачуване у одвојеној листи чији редослед је обрнут од редоследа оригиналне структуре података. Наиме, члан "3" на листи [1, 2, 3] је представљен као [2, 1]. Листа са затварачем представља читаву структуру и локације унутар структуре.

Са листом представљеном на овај начин, лако је дефинисати ефикасне операције које се крећу напред или назад по листи и манипулишу листом на тој локацији, на пример убацивања или избацивањем чланова листе. Слично томе, примена трансформација затварача на стабло олакшава уметања или брисањ вредности на одређеној локацији у стаблу.

Употреба

Затварач се често користи када постоји неки концепт "фокуса" или кретања кроз неки скуп података. Затварач се користи у:

• Xmonad, управља фокусом и позиционирањем прозора
• Рачунарски систем датотека (ZipperFS) написан у Haskell-y нуди "... трансакциону семантику; поништавање операција над датотекама и директоријумима; механизам snapshot-a; гарантовано најјачи статички режим изолације клијента, са способностима понављања читања; правилно понашање референци цикличних директоријума."^[2]
• Clojure има проширену подршку за затварач^[3]

Контекст затварача и његова диференцијација

Показало се да је тип сваког члана листе произведене од стране затварача "дериват" оригиналне структуре у смислу да је декатегоризацијом повезан са диференцијацијом у инфинитезималном рачуну. Многи типови су направљени од прпизвода и збирова других типова; многе структуре изгледају као полином или Тејлоров развој, а репрезентација члана листе изгледа као дериват полинома или развоја.^[4][5]

Размотримо рекурзивни тип података попут стабла чији су чворови типа А:

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

Ово стабло се састоји од троструке вредности типа А и два подстабла типа R, тако да добијамо:

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

У суштини, затварач типа Т параметризован неким другим типом А и рекурзивном константом R, састоји се из два дела: листе типа ${\displaystyle {\frac {dT(A,R)}{dR}}|_{R=T(A,R)}}$ и копије силазне листе ${\displaystyle T(A,R)|_{R=T(A,R)}.}$.

Алтернативе и екстензије

Директне моификације

У не-чисто-функционални програмским језицима, можда би било згодније да се једноставно пролазе кроз оригиналну структуру података и да се она модификује директно (вероватно после копирања објекта, како би се избегли сукоби са остатком кода који би имали референцу на тај објекат).

Генерички затварач

Генерички затварач је техника која има исти циљ као обичан затварач, да забележи стање чворова током обиласка свих чворова. Генерички затварач укључујр и контролу инверза, тако да се при неким употребама захтевају информације о стању машине како би се предвидео следећи корак.

Референце

1. Huet 1997
2. Generic Zipper: the context of a traversal
3. jafingerhut (22. 10. 2010). „clojure.zip/zipper”. ClojureDocs. Приступљено 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 . 

Литература

• 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 . CS1 одржавање: Експлицитна употреба et al. (веза). 23 July 2003

Спољашње везе

• Zipper
• Theseus and the Zipper
• "Roll Your Own Window Manager: Tracking Focus with a Zipper"
• Definition
• "An Applicative Control-Flow Graph Based on Huet's Zipper"
• Infinitesimal Types