پیش‌نویس:زیپ (ساختار داده)

زیپ (به انگلیسی: Zipper (data structure)) تکنیکی برای نمایش یک ساختار داده انبوه است به طوری که برای نوشتن برنامه‌هایی که خودسرانه ساختار را طی می‌کنند و محتویات آن را به روز می‌کنند، به خصوص در زبان‌های برنامه‌نویسی کاملاً کاربردی ^(en) راحت باشد. زیپ توسط جرارد هوئت ^(en) در سال ۱۹۹۷ توصیف شد.^[۱] این شامل و تعمیم تکنیک بافر شکاف ^(en) است که گاهی با آرایه‌ها استفاده می‌شود.

تکنیک زیپ از این نظر کلی است که می‌توان آن را با فهرست‌ها، درخت‌ها و دیگر ساختارهای داده‌ای که به صورت بازگشتی ^(en) تعریف می‌شوند، تطبیق داد. چنین ساختارهای داده‌ای اصلاح شده معمولاً به عنوان «یک درخت با زیپ» یا «یک لیست با زیپ» نامیده می‌شود تا تأکید شود که ساختار از نظر مفهومی یک درخت یا لیست است، در حالی که زیپ جزئیات پیاده‌سازی است.

توضیح یک فرد عادی برای درختی با زیپ یک سیستم فایل کامپیوتری معمولی با عملیاتی برای رفتن به والد (اغلب cd ..) و امکان رفتن به سمت پایین (cd subdirectory) است. زیپ نشانگر مسیر فعلی است. در پشت صحنه، زیپ‌ها هنگام ایجاد تغییرات (عملکردی) در یک ساختار داده کارآمد هستند، جایی که یک ساختار داده جدید، کمی تغییر یافته از یک عملیات ویرایش بازگردانده می‌شود (به جای ایجاد تغییر در ساختار داده فعلی).

مثال: پیمایش لیست دوطرفه

بسیاری از ساختارهای داده رایج در علوم کامپیوتر را می‌توان به عنوان ساختاری که توسط چند عملیات سازنده اولیه یا عملیات مشاهده گر ایجاد می‌شود بیان کرد. اینها شامل ساختار لیست‌های محدود است که می‌تواند توسط دو عملیات ایجاد شود:

Empty یک لیست خالی می‌سازد،
Cons(x, L) یک لیست را با اضافه کردن یا الحاق مقدار x در مقابل لیست L می‌سازد.

بنابراین فهرستی مانند [1, 2, 3] عبارت Cons(1, Cons(2, Cons(3, Empty))) است. می‌توان مکان را در چنین لیستی به عنوان تعداد مراحل از جلوی لیست تا مکان مورد نظر توصیف کرد. به‌طور رسمی‌تر، یک مکان در لیست تعداد عملیات Cons مورد نیاز برای بازسازی کل لیست از آن مکان خاص است. برای مثال، در Cons(1, Cons(2, Cons( X, Cons(4, Empty)))) یک عملیات Cons(2, L) و یک Cons(1, L) برای بازسازی لیست مورد نیاز است. موقعیت X با نام Cons( X, Cons(4, Empty)) شناخته می‌شود. این ضبط همراه با مکان، نمایش زیپ شده از لیست یا زیپ لیست نامیده می‌شود.

برای روشن بودن، یک مکان در لیست فقط تعداد عملیات Cons نیست، بلکه تمام اطلاعات دیگر در مورد آن Cons است. در این حالت، مقادیری که باید دوباره وصل شوند. در اینجا، این مقادیر ممکن است به راحتی در یک لیست جداگانه به ترتیب کاربرد از محل مورد نظر نشان داده شوند. به‌طور خاص، از متن "۳" در لیست [1, 2, 3, 4] ، یک ضبط (که معمولاً به عنوان "مسیر" نامیده می‌شود) می‌تواند به عنوان [2, 1] نشان داده شود که در آن Cons(2, L) به دنبال آن (Cons 1, L) برای بازسازی لیست اصلی با شروع از [3, 4] اعمال می‌شود.

یک لیست زیپ همیشه کل ساختار داده را نشان می‌دهد. با این حال، این اطلاعات از منظر یک مکان خاص در آن ساختار داده است. در نتیجه، یک لیست زیپ جفتی است که هم از مکان به عنوان زمینه یا نقطه شروع و هم از یک ضبط یا مسیری تشکیل شده است که امکان بازسازی از آن مکان شروع را فراهم می‌کند. به‌طور خاص، فهرست زیپ [1, 2, 3, 4] در محل "۳" ممکن است به صورت ([2, 1], [3, 4]) نمایش داده شود. حال، اگر "۳" به "۱۰" تغییر یابد، آنگاه زیپ لیست تبدیل به ([2, 1], [10, 4]) می‌شود. سپس فهرست ممکن است به‌طور مؤثر بازسازی شود: [1, 2, 10, 4] یا مکان‌های دیگری که به آن‌ها رفته‌اند.

با فهرستی که به این شکل نمایش داده می‌شود، تعریف عملیات نسبتاً کارآمد بر روی ساختارهای داده تغییرناپذیر مانند فهرست‌ها و درختان در مکان‌های دلخواه آسان است. به‌طور خاص، اعمال تبدیل زیپ به یک درخت، درج یا حذف مقادیر در هر مکان خاص در درخت را آسان می‌کند.

زمینه‌ها و تمایز

نوع زمینه‌های یک زیپ را می‌توان از طریق تبدیلی ^(en) از نوع اصلی که از طریق طبقه‌بندی کردن ^(en) با مشتق حساب دیفرانسیل و انتگرال مرتبط است، ساخت. انواع بازگشتی که زیپ‌ها از آنها تشکیل می‌شوند را می‌توان به عنوان حداقل نقطه ثابت ^(en) یک سازنده نوع یکنواخت در نظر گرفت. $*\rightarrow *$ . به عنوان مثال، با یک سازنده نوع بالاتر ${\text{lfp}}:(*\rightarrow *)\rightarrow *$ که حداقل نقطه ثابت آرگومان خود را می‌سازد، یک درخت باینری بدون برچسب را می‌توان به صورت نمایش داد ${\text{lfp}}(T\mapsto T^{2}+1)$ و یک لیست بدون برچسب ممکن است شکل بگیرد ${\text{lfp}}(T\mapsto T+1)$ . در اینجا، نماد توان، ضرب و جمع به ترتیب با انواع تابع ^(en)، انواع حاصلضرب ^(en) و انواع مجموع ^(en) مطابقت دارد، در حالی که اعداد طبیعی انواع محدود ^(en) را برچسب گذاری می‌کنند. به این ترتیب، سازنده‌های نوع شبیه توابع چند جمله‌ای هستند $\mathbb {N} \rightarrow \mathbb {N}$ .^[۲]

بنابراین مشتق سازنده نوع را می‌توان از طریق این قیاس نحوی تشکیل داد: برای مثال یک درخت سه تایی بدون برچسب، مشتق سازنده نوع آن $(T\mapsto T^{3}+1)'$ معادل خواهد بود $T\mapsto 3\times T^{2}$ ، مشابه استفاده از قواعد دیفرانسیل‌گیری و توان ^(en) در حساب دیفرانسیل. نوع زمینه‌های زیپ روی یک نوع اصلی ${\text{lfp}}(f)$ معادل مشتق سازنده نوع اعمال شده برای نوع اصلی است، $f'({\text{lfp}}(f))$ .^[۳]

برای مثال، ساختار داده بازگشتی یک درخت باینری با گره‌هایی را در نظر بگیرید که یا گره‌های نگهبان ^(en) از نوع ۱ هستند یا حاوی مقداری از نوع $A$ هستند:

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

مشتق جزئی سازنده نوع را می‌توان به صورت محاسبه کرد

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

بنابراین، نوع زمینه‌های زیپ است

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

به این ترتیب، متوجه می‌شویم که زمینه هر گره فرزند غیر نگهبان در درخت باینری برچسب‌گذاری شده، سه‌گانه است که شامل

یک نوع داده بولی از نوع ۲ که بیان می‌کند که گره فعلی فرزند چپ یا راست گره والد خود است.
یک مقدار از نوع $A$ ، برچسب والد گره فعلی. و
خواهر و برادر گره از نوع $BTree$ ، زیردرختی که توسط شاخه دیگر والد گره فعلی موجود است.

به‌طور کلی، یک زیپ برای یک درخت از نوع ${\text{lfp}}(f)$ از دو بخش تشکیل شده است: فهرستی از زمینه‌های نوع $f'({\text{lfp}}(f))$ از گره فعلی و هر یک از اجداد آن تا گره ریشه، و مقدار نوع ${\text{lfp}}(f)$ که گره فعلی شامل می‌شود.

استفاده

زیپ اغلب در جایی استفاده می‌شود که مفهوم تمرکز ^(en) یا حرکت به اطراف در مجموعه‌ای از داده‌ها وجود داشته باشد، زیرا معنای آن منعکس‌کننده حرکت به اطراف است اما به شیوه‌ای کاربردی غیر مخرب.

از زیپ استفاده شده است در

Xmonad ^(en) برای مدیریت فوکوس و قرارگیری ویندوز
مقالات Huet یک ویرایشگر ساختاری ^(en)^[۴] بر اساس زیپ‌ها و یک اثبات قضیه خودکار را پوشش می‌دهد.
یک سامانه فایل‌بندی (ZipperFS) که به زبان هسکل نوشته شده است که «... معناشناسی تراکنش‌ها؛ خنثی کردن هر گونه عملیات فایل و دایرکتوری؛ عکس‌های فوری؛ تضمینی استاتیکی قوی‌ترین، تکرارپذیرترین حالت خواندن و جداسازی برای کلاینت‌ها؛ کپی بر روی نوشتن فراگیر برای فایل‌ها و فهرست‌ها. تسهیلات پیمایش داخلی و رفتار مناسب برای مراجع دایرکتوری چرخه ای.^[۵]
کلوژر پشتیبانی گسترده‌ای از زیپ دارد.^[۶]

جایگزین‌ها و الحاقات

اصلاح مستقیم

در یک زبان برنامه‌نویسی غیر کاربردی، ممکن است ساده‌تر از ساختار داده اصلی عبور کرد و مستقیماً آن را اصلاح کرد (شاید پس از شبیه‌سازی عمیق ^(en)، برای جلوگیری از تأثیرگذاری روی کدهای دیگر که ممکن است به آن ارجاع دهند).

زیپ عمومی

زیپ عمومی^[۷]^[۸]^[۹] تکنیکی برای دستیابی به همان هدفی است که زیپ معمولی با ثبت وضعیت پیمایش در ادامه هنگام بازدید از هر گره انجام می‌شود. (کد Haskell داده شده در مرجع از برنامه‌نویسی عمومی برای تولید تابع پیمایش برای هر ساختار داده استفاده می‌کند، اما این اختیاری است. - می‌توان از هر تابع پیمایش مناسب استفاده کرد)

با این حال، زیپ عمومی شامل وارونگی کنترل است، بنابراین برخی از کاربردهای آن نیاز به یک ماشین حالات متناهی (یا معادل) برای پیگیری کارهای بعدی دارند.

منابع

↑ (Huet 1997)
↑ Joyal, André (October 1981). "Une théorie combinatoire des séries formelles". Advances in Mathematics. ۴۲ (۱): ۱–۸۲. doi:10.1016/0001-8708(81)90052-9.
↑ McBride, Conor (2001), "The Derivative of a Regular Type is its Type of One-Hole Contexts"
↑ Hinze, Ralf; Jeuring, Johan (2001). "Functional Pearl: Weaving a web". Journal of Functional Programming. 11 (6): 681–689. doi:10.1017/S0956796801004129. ISSN 0956-7968.
↑ Generic Zipper: the context of a traversal
↑ jafingerhut (2010-10-22). "clojure.zip/zipper". ClojureDocs. Retrieved 2013-06-15.
↑ Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 1". Retrieved 29 August 2011.
↑ Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 2". Retrieved 29 August 2011.
↑ Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 3". Retrieved 29 August 2011.

بیشتر خواندن

Huet, Gerard (September 1997). "The Zipper" (PDF). Journal of Functional Programming. 7 (5): 549–554. doi:10.1017/s0956796897002864.
Hinze, Ralf; Jeuring, Johan; Löh, Andres (May 2004). "Type-indexed data types". Science of Computer Programming. 51 (1–2): 117–151. doi:10.1016/j.scico.2003.07.001.

پیوند به بیرون

[1] (Huet 1997)

[2] Joyal, André (October 1981). "Une théorie combinatoire des séries formelles". Advances in Mathematics. ۴۲ (۱): ۱–۸۲. doi:10.1016/0001-8708(81)90052-9.

[3] McBride, Conor (2001), "The Derivative of a Regular Type is its Type of One-Hole Contexts"

[4] Hinze, Ralf; Jeuring, Johan (2001). "Functional Pearl: Weaving a web". Journal of Functional Programming. 11 (6): 681–689. doi:10.1017/S0956796801004129. ISSN 0956-7968.

[5] Generic Zipper: the context of a traversal

[6] rhut (2010-10-22). "clojure.zip/zipper". ClojureDocs. Retrieved 2013-06-15.

[7] Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 1". Retrieved 29 August 2011.

[8] Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 2". Retrieved 29 August 2011.

[9] Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 3". Retrieved 29 August 2011.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]