موضوع مقاله: زیپ (ساختار داده) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # زیپ (ساختار داده) | مقدمه: ساختار داده زیپ تکنیکی برای نمایش یک ساختار داده انبوه است به طوری که برای نوشتن برنامه‌هایی که خودسرانه ساختار را طی می‌کنند و محتویات آن را به روز می‌کنند، به خصوص در راحت باشد. | ## بخش 1: زیپ (ساختار داده) | تکنیک زیپ از این نظر کلی است که می‌توان آن را با فهرست‌ها، درخت‌ها و دیگر ساختارهای داده‌ای که به تعریف می‌شوند، تطبیق داد. چنین ساختارهای داده‌ای اصلاح شده معمولاً به عنوان «یک درخت با زیپ» یا «یک لیست با زیپ» نامیده می‌شود تا تأکید شود که ساختار از نظر مفهومی یک درخت یا لیست است، در حالی که زیپ جزئیات پیاده‌سازی است. در پشت صحنه، زیپ‌ها هنگام ایجاد تغییرات (عملکردی) در یک ساختار داده کارآمد هستند، جایی که یک ساختار داده جدید، کمی تغییر یافته از یک عملیات ویرایش بازگردانده می‌شود (به جای ایجاد تغییر در ساختار داده فعلی). مثال: پیمایش لیست دوطرفه بسیاری از ساختارهای داده رایج در علوم کامپیوتر را می‌توان به عنوان ساختاری که توسط چند عملیات سازنده اولیه یا عملیات مشاهده گر ایجاد می‌شود بیان کرد. اینها شامل ساختار لیست‌های محدود است که می‌تواند توسط دو عملیات ایجاد شود: Empty یک لیست خالی می‌سازد، Cons(x, L) یک لیست را با اضافه کردن یا الحاق مقدار x در مقابل لیست L می‌سازد. می‌توان مکان را در چنین لیستی به عنوان تعداد مراحل از جلوی لیست تا مکان مورد نظر توصیف کرد. به‌طور رسمی‌تر، یک مکان در لیست تعداد عملیات Cons مورد نیاز برای بازسازی کل لیست از آن مکان خاص است. برای روشن بودن، یک مکان در لیست فقط تعداد عملیات Cons نیست، بلکه تمام اطلاعات دیگر در مورد آن Cons است. در اینجا، این مقادیر ممکن است به راحتی در یک لیست جداگانه به ترتیب کاربرد از محل مورد نظر نشان داده شوند. | ## بخش 2: زیپ (ساختار داده) | به‌طور خاص، از متن "۳" در لیست [1, 2, 3, 4] ، یک ضبط (که معمولاً به عنوان "مسیر" نامیده می‌شود) می‌تواند به عنوان [2, 1] نشان داده شود که در آن Cons(2, L) به دنبال آن (Cons 1, L) برای بازسازی لیست اصلی با شروع از [3, 4] اعمال می‌شود. در نتیجه، یک لیست زیپ جفتی است که هم از مکان به عنوان زمینه یا نقطه شروع و هم از یک ضبط یا مسیری تشکیل شده است که امکان بازسازی از آن مکان شروع را فراهم می‌کند. سپس فهرست ممکن است به‌طور مؤثر بازسازی شود: [1, 2, 10, 4] یا مکان‌های دیگری که به آن‌ها رفته‌اند. با فهرستی که به این شکل نمایش داده می‌شود، تعریف عملیات نسبتاً کارآمد بر روی ساختارهای داده تغییرناپذیر مانند فهرست‌ها و درختان در مکان‌های دلخواه آسان است. به‌طور خاص، اعمال تبدیل زیپ به یک درخت، درج یا حذف مقادیر در هر مکان خاص در درخت را آسان می‌کند. زمینه‌ها و تمایز نوع زمینه‌های یک زیپ را می‌توان از طریق از نوع اصلی که از طریق با مشتق حساب دیفرانسیل و انتگرال مرتبط است، ساخت. انواع بازگشتی که زیپ‌ها از آنها تشکیل می‌شوند را می‌توان به عنوان یک سازنده نوع یکنواخت در نظر گرفت. به عنوان مثال، با یک سازنده نوع بالاتر که حداقل نقطه ثابت آرگومان خود را می‌سازد، یک درخت باینری بدون برچسب را می‌توان به صورت نمایش داد و یک لیست بدون برچسب ممکن است شکل بگیرد . در اینجا، نماد توان، ضرب و جمع به ترتیب با ، و مطابقت دارد، در حالی که اعداد طبیعی را برچسب گذاری می‌کنند. | ## بخش 3: زیپ (ساختار داده) | بنابراین مشتق سازنده نوع را می‌توان از طریق این قیاس نحوی تشکیل داد: برای مثال یک درخت سه تایی بدون برچسب، مشتق سازنده نوع آن معادل خواهد بود ، مشابه استفاده از قواعد دیفرانسیل‌گیری و در حساب دیفرانسیل. و خواهر و برادر گره از نوع ، زیردرختی که توسط شاخه دیگر والد گره فعلی موجود است. به‌طور کلی، یک زیپ برای یک درخت از نوع از دو بخش تشکیل شده است: فهرستی از زمینه‌های نوع از گره فعلی و هر یک از اجداد آن تا گره ریشه، و مقدار نوع که گره فعلی شامل می‌شود. استفاده زیپ اغلب در جایی استفاده می‌شود که مفهوم یا حرکت به اطراف در مجموعه‌ای از داده‌ها وجود داشته باشد، زیرا معنای آن منعکس‌کننده حرکت به اطراف است اما به شیوه‌ای کاربردی غیر مخرب. از زیپ استفاده شده است در برای مدیریت فوکوس و قرارگیری ویندوز مقالات Huet یک بر اساس زیپ‌ها و یک اثبات قضیه خودکار را پوشش می‌دهد. معناشناسی تراکنش‌ها؛ خنثی کردن هر گونه عملیات فایل و دایرکتوری؛ عکس‌های فوری؛ تضمینی استاتیکی قوی‌ترین، تکرارپذیرترین حالت خواندن و جداسازی برای کلاینت‌ها؛ کپی بر روی نوشتن فراگیر برای فایل‌ها و فهرست‌ها. جایگزین‌ها و الحاقات اصلاح مستقیم در یک زبان برنامه‌نویسی غیر کاربردی، ممکن است ساده‌تر از ساختار داده اصلی عبور کرد و مستقیماً آن را اصلاح کرد (شاید پس از ، برای جلوگیری از تأثیرگذاری روی کدهای دیگر که ممکن است به آن ارجاع دهند). زیپ عمومی زیپ عمومی تکنیکی برای دستیابی به همان هدفی است که زیپ معمولی با ثبت وضعیت پیمایش در ادامه هنگام بازدید از هر گره انجام می‌شود. (کد Haskell داده شده در مرجع از برنامه‌نویسی عمومی برای تولید تابع پیمایش برای هر ساختار داده استفاده می‌کند، اما این اختیاری است. | ## جمع‌بندی | - می‌توان از هر تابع پیمایش مناسب استفاده کرد) با این حال، زیپ عمومی شامل وارونگی کنترل است، بنابراین برخی از کاربردهای آن نیاز به یک ماشین حالات متناهی (یا معادل) برای پیگیری کارهای بعدی دارند.