خواندن 16 ، قسمت 1: انواع داده های بازگشتی

قبل از معرفی داده های بازگشتی - که ساختار بازگشتی از داده ها و محاسبات دارند - یک دقیقه برای بررسی محاسبات بازگشتی طول می کشد.

درست همانطور که یک عملکرد بازگشتی از نظر خود تعریف شده است ، یک داده بازگشتی از نظر خود تعریف می شود. ما همان نیاز به موارد پایه و بازگشتی را خواهیم دید ، که اکنون به عنوان انواع مختلفی از نوع انتزاعی ظاهر می شوند.

لیست های تغییر ناپذیر

ما با یک داده بازگشتی کلاسیک ، لیست تغییر ناپذیر شروع خواهیم کرد.

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

بیایید یک نوع داده را برای یک لیست تغییر ناپذیر ، imlist تعریف کنیم. نوع داده چهار عمل اساسی دارد:

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

قبل از طراحی کلاس های جاوا برای اجرای این داده ، اجازه دهید کمی با استفاده از لیست های اعداد صحیح به عملیات عادت کنیم. ما لیست هایی را با براکت های مربعی مانند [1 ، 2 ، 3] می نویسیم ، و عملیات ها را به گونه ای می نویسیم که گویی آنها عملکردهای ریاضی هستند. پس از رسیدن به جاوا ، نحو متفاوت به نظر می رسد اما عملیات معنای یکسانی خواهد داشت.

خالی () = [] منفی (0 ، خالی ()) = [0] منفی (0 ، منفی (1 ، منفی (2 ، خالی ()))) = [0 ، 1 ، 2] x ≡ منفی (0 ،منفی (1 ، منفی (2 ، خالی ()))) = [0 ، 1 ، 2] اول (x) = 0 استراحت (x) = [1 ، 2] اول (استراحت (x)) = 1 استراحت (استراحت(x)) = [2] اول (استراحت (استراحت (x)) = 2 استراحت (استراحت (استراحت (x))) = []

رابطه اساسی بین اول ، استراحت و منفی این است:

اول (منفی (ELT ، LST)) = ELT REST (منفی (ELT ، LST)) = LST

چه منفی در کنار هم قرار می گیرد ، ابتدا و استراحت را از هم جدا کنید.

لیست های تغییر ناپذیر در جاوا

برای پیاده سازی این داده در جاوا ، از یک رابط استفاده خواهیم کرد:

این رابط یک نوع عمومی از نوع عمومی را اعلام می کند که می تواند برای هر نوع E فوری شود: imlist ، imlist و غیره. E در این اعلامیه ها یک مکان نگهدارنده است که کامپایلر هنگام بررسی کد ما برای نوع ایمنی ، پر خواهد شد.

و ما دو کلاس خواهیم نوشت که این رابط را پیاده سازی می کنند:

• خالی نشان دهنده نتیجه عملیات خالی (یک لیست خالی) است
• منفی نتیجه یک عمل منفی را نشان می دهد (عنصری که به همراه لیست دیگری چسبانده شده است)

بنابراین ما روش هایی برای منفی ، اول و استراحت داریم ، اما عملکرد چهارم از داده های ما ، خالی است؟

یکی از راه های اجرای خالی این است که مشتری ها با سازنده کلاس خالی تماس بگیرند تا لیست های خالی را بدست آورند. این استقلال نمایندگی را فدا می کند - مشتریان باید در مورد کلاس خالی بدانند!

همانطور که در رابط ها دیدیم ، یک روش بهتر برای انجام آن به عنوان یک روش کارخانه استاتیک است که هیچ استدلالی در نظر نمی گیرد و نمونه ای از خالی را تولید می کند. ما می توانیم این روش استاتیک را در رابط IMLIST همراه با سایر عملیات قرار دهیم. این انتخاب در نسخه های قبلی جاوا امکان پذیر نبود ، به همین دلیل ما هنوز کد مانند:

شاید روزی جاوا یک روش list. empty () را برای به دست آوردن یک لیست خالی جدید همه منظوره ارائه دهد ، اما هنوز نیست.(اگر می خواهید یک لیست خالی غیرقابل تغییر داشته باشید ، مجموعه ای دارد.

ما پیش می رویم و رابط IMLIST خود را با روش خالی استاتیک به روز خواهیم کرد:

امضای خالی از بیت جدید نحو از نوع عمومی استفاده می کند. E in Imlist یک مکان نگهدارنده برای نوع عناصر در نمونه ای از Imlist است ، اما خالی یک روش استاتیک است: نمی تواند متغیرها یا روش های نمونه را مشاهده کند ، و همچنین نمی تواند پارامتر نوع نمونه را ببیند. شما می توانید اعلامیه خالی را بخوانید: "برای هر E ، خالی () یک لیست را برمی گرداند."

اکنون که همه عملیات را انجام داده ایم ، در اینجا کد جاوا واقعی وجود دارد که نمونه های انتزاعی را که قبلاً نوشتیم موازی است. برای به روزرسانی نمودار عکس فوری ، روی هر سطر در جدول حرکت کنید یا ضربه بزنید:

نکته کلیدی که در اینجا باید به آن توجه کنیم ، اشتراک ساختاری است که لیست تغییر ناپذیر ارائه می دهد. در مثال آخر ، X و Y نمایندگی خود را از Sublist به اشتراک می گذارند [1 ، 2].

دو کلاس اجرای یک رابط

توجه داشته باشید که این طرح با آنچه با لیست ، ArrayList و LinkedList دیده ایم متفاوت است. لیست یک نوع داده انتزاعی است و ArrayList و LinkedList دو نمایش بتونی جایگزین برای آن داده است.

برای IMLIST ، دو پیاده سازی خالی و Conc به منظور اجرای داده ها همکاری می کنند - شما به هر دو آنها احتیاج دارید.

تمرینات خواندن

ما پیاده سازی های IMLIST خود را بدون مستند سازی عملکرد انتزاع و بازنمایی متغیر نوشتیم ، که ما را به مردم وحشتناک تبدیل می کند.

دو روش خوب برای نوشتن عملکرد انتزاع را برای خالی انتخاب کنید:

و خطوط را انتخاب کنید تا در repiariant گنجانیده شود (بیایید حتی موارد 6. 031 را نیز در بر بگیریم):

تمام توابع انتزاع خوب را برای منفی انتخاب کنید:

یک لیست دو عنصر را نشان می دهد که عنصر اول E و عنصر دوم استراحت است (پاسخ گمشده)

و خطوط را انتخاب کنید تا در repiariant گنجانیده شود (بیایید حتی موارد 6. 031 را نیز در بر بگیریم):

با توجه به این کد:

کدام یک از موارد زیر صحیح است؟

درست یا غلط: خالی و منفی هر دو Imlist مشابه با ArrayList و LinkedList هر دو لیست اجرا در کتابخانه جاوا هستند.

تعاریف داده های بازگشتی

نوع داده انتزاعی Imlist و دو کلاس بتونی آن خالی و منفی ، یک نوع داده بازگشتی را تشکیل می دهند. منفی اجرای IMLIST است ، اما از Imlist در داخل نماینده خود (برای قسمت REST) نیز استفاده می کند ، بنابراین به صورت بازگشتی به اجرای IMLIST برای اجرای موفقیت آمیز قرارداد خود نیاز دارد.

برای اینکه این واقعیت به وضوح قابل مشاهده باشد ، ما یک تعریف DataType خواهیم نوشت:

این یک تعریف بازگشتی از Imlist به عنوان مجموعه ای از مقادیر است. آن را مانند این بخوانید: iMlist مجموعه شامل مقادیری است که به دو روش تشکیل شده است: یا توسط سازنده خالی ، یا با استفاده از سازنده Cons Contractor در یک عنصر و یک IMLIST. ماهیت بازگشتی داده وقتی به این روش نوشته می شود بسیار قابل مشاهده تر می شود.

ما همچنین می توانیم با استفاده از این تعریف ، مقادیر imlist را به عنوان اصطلاحات یا عبارات بنویسیم ، به عنوان مثال:

به طور رسمی ، یک تعریف Datatype دارای:

• یک داده انتزاعی در سمت چپ ، تعریف شده توسط بازنمایی آن (یا داده بتونی) در سمت راست
• این نمایندگی شامل انواع داده های داده شده توسط + است
• هر نوع سازنده با آرگومان های صفر یا بیشتر (و تایپ شده) است

مثال دیگر یک درخت باینری است:

نمونه های بیشتری را در زیر مشاهده خواهیم کرد.

تمرینات خواندن

تعریف Datatype را در نظر بگیرید:

فرض کنید شما به یک شیء زمین شناسی مراجعه کنید. چند عدد صحیح ممکن است در نمایندگی خود داشته باشد؟

با توجه به تعاریف آنها ، کدام یک از داده های تغییر ناپذیر زیر می تواند یک جفت عدد صحیح را نشان دهد؟

از سوال قبلی ، کدام داده ها بازگشتی هستند؟

همچنین از این سوال ، کدام مشکل با نوع V است؟

همچنین از این سؤال ، ما دیدیم که نوع X فقط Imlist ما در مبدل (و فقط برای اعداد صحیح) است. اگر بخواهیم W را به عنوان یک لیست فکر کنیم ، در مقایسه با نوع X مشکلات احتمالی در مقایسه با نوع X وجود دارد؟

توابع بیش از داده های بازگشتی

این روش تفکر در مورد داده ها - به عنوان یک تعریف بازگشتی از یک داده انتزاعی با انواع بتونی - نه تنها به این دلیل است که می تواند ساختارهای بازگشتی و بی حد و مرز مانند لیست ها و درختان را اداره کند ، بلکه به این دلیل که یک روش مناسب برای توصیف عملیات از طریق داده داده ارائه می دهد.، به عنوان عملکرد با یک مورد در هر نوع.

به عنوان مثال ، اندازه لیست را در نظر بگیرید ، که مطمئناً عملی است که ما می خواهیم در IMLIST. ما می توانیم آن را اینگونه تعریف کنیم:

اندازه: imlist → int // اندازه لیست را برمی گرداند

و سپس با تعیین اندازه برای هر نوع IMLIST ، معنی آن را کاملاً مشخص کنید:

اندازه (خالی) = 0 اندازه (منفی (اول: E ، استراحت: imlist)) = 1 + اندازه (استراحت)

این عملکرد بازگشتی است. ما می توانیم در مورد اجرای اندازه در یک لیست خاص به عنوان یک سری مراحل کاهش فکر کنیم:

اندازه (منفی (0 ، منفی (1 ، خالی))) = 1 + اندازه (منفی (1 ، خالی)) = 1 + (1 + اندازه (خالی)) = 1 + (1 + 0) = 1 + 1 =2

و موارد موجود از این تعریف می تواند به طور مستقیم به جاوا به عنوان روش های موجود در imlist ، خالی و منفی ترجمه شود:

این الگوی اجرای یک عملیات بر روی یک داده بازگشتی توسط

• اعلام عملیات در رابط داده انتزاعی
• اجرای عملیات (بازگشتی) در هر نوع بتونی

یک الگوی طراحی بسیار رایج و عملی است. گاهی اوقات با الگوی مترجم نام نامشخص می رود.

بیایید چند مثال دیگر را امتحان کنیم:

isempty: imlist → بولی

isEmpty (خالی) = isEmpty واقعی (منفی (اول: E ، استراحت: imlist)) = false

شامل: imlist × e → بولی

حاوی (خالی ، e: e) = false حاوی (منفی (اول: e ، استراحت: imlist) ، e: e) = (first = e) ∨ حاوی (استراحت ، e)

دریافت: imlist × int → e

دریافت (خالی ، n: int) = تعریف نشده (منفی (اول: e ، استراحت: imlist) ، n: int) = اگر n = 0 پس از آن اول دیگر دریافت کنید (استراحت ، n-1)

ضمیمه: imlist × imlist → imlist

ضمیمه (خالی ، لیست 2: imlist) = لیست 2 ضمیمه (اولین: E ، استراحت: imlist) ، لیست 2: imlist) = منفی (اول ، ضمیمه (استراحت ، لیست 2))

معکوس: imlist → imlist

معکوس (خالی) = خالی () معکوس (منفی (اول: E ، استراحت: imlist)) = ضمیمه (معکوس (استراحت) ، منفی (اول ، خالی ())

برای معکوس ، معلوم می شود که تعریف بازگشتی یک اجرای بسیار بد در جاوا ایجاد می کند ، با عملکردی که در طول لیستی که معکوس می کنید درجه دوم است. در صورت لزوم می توانیم آن را با استفاده از یک رویکرد تکراری بازنویسی کنیم.

تمرینات خواندن

isempty: imlist → بولی

isEmpty (خالی) = isEmpty واقعی (منفی (اول: E ، استراحت: imlist)) = false

بیایید imlist. isempty را پیاده سازی کنیم.

ضمیمه: imlist × imlist → imlist

ضمیمه (خالی ، لیست 2: imlist) = لیست 2 ضمیمه (اولین: E ، استراحت: imlist) ، لیست 2: imlist) = منفی (اول ، ضمیمه (استراحت ، لیست 2))

بیایید Imlist. Append را پیاده سازی کنیم.

این بار ، تمام پیاده سازی های صحیح را انتخاب کنید:

تنظیم نماینده

دریافت اندازه یک لیست یک عمل مشترک است. در حال حاضر اجرای ما از اندازه () زمان (n) زمان می برد ، جایی که n طول لیست است - که در تعداد موارد لیست خطی است. ما می توانیم با یک تغییر ساده در لیست لیست که اندازه آن را برای اولین بار که آن را محاسبه می کنیم ، بهتر کنیم ، به طوری که متعاقباً فقط زمان (1) زمان - زمان ثابت ، مستقل از تعداد موارد لیست - هزینه می کندگرفتن:

توجه داشته باشید که ما از مقدار ویژه 0 (که هرگز نمی تواند اندازه منفی باشد) استفاده می کنیم تا نشان دهیم که هنوز اندازه آن را محاسبه نکرده ایم. توجه داشته باشید که این تغییر بند جدیدی را به ثابت متغیر معرفی می کند ، و مربوط به قسمت اندازه به قسمت REST است.

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

استقلال Rep و نمایندگی مجدداً مورد بررسی قرار گرفت

آیا اجرای جاوا ما از Imlist هنوز استقلال نماینده دارد؟ما مشارکت خالی را در پشت روش استاتیک imlist. empty () پنهان کرده ایم ، و مشتری ها هرگز نیازی به استفاده مستقیم از سازندگان خالی یا منفی ندارند. ما می توانیم آنها را با ایجاد بسته بندی خصوصی (که با کلمه کلیدی عمومی و خصوصی اعلام نشده اند) پنهان کنیم تا کلاس های خارج از بسته Imlist نتواند آنها را ببیند یا از آنها استفاده کند.

ما آزادی زیادی برای تغییر اجرای خود داریم - در واقع ، ما فقط یک زمینه اندازه را به نمای داخلی منفی اضافه کردیم. ما حتی می توانستیم یک آرایه اضافی در آنجا داشته باشیم تا سریع () را اجرا کنیم! این ممکن است در فضا گران شود ، اما ما می توانیم این تجارت را انجام دهیم.

آیا قرار گرفتن در معرض نمایندگی وجود دارد زیرا Cons. Rest () مرجع لیست داخلی آن را برمی گرداند؟آیا یک مشتری دست و پا چلفتی می تواند عناصر را به بقیه لیست اضافه کند؟اگر چنین است ، این باعث می شود که دو متغیر منفی را تهدید کند: این تغییر ناپذیر است ، و اندازه ذخیره شده همیشه صحیح است. اما خطر قرار گرفتن در معرض تکرار وجود ندارد ، زیرا لیست داخلی تغییر ناپذیر است. هیچ کس نمی تواند متغیر منفی را تهدید کند.

تهی در مقابل خالی

خلاص شدن از شر کلاس خالی ممکن است وسوسه انگیز باشد و به جای آن فقط از تهی استفاده کنید. در برابر آن وسوسه مقاومت کنید.

استفاده از یک شیء ، به جای یک مرجع تهی ، برای سیگنال دادن مورد پایه یا نقطه پایانی یک ساختار داده نمونه ای از الگوی طراحی به نام اشیاء Sentinel است. مزیت عظیمی که یک شیء Sentinel ارائه می دهد این است که مانند یک شیء در Datatype عمل می کند ، بنابراین می توانید روش هایی را روی آن فراخوانی کنید. بنابراین می توانیم حتی در یک لیست خالی از روش اندازه () تماس بگیریم. اگر لیست های خالی توسط NULL نشان داده می شدند ، ما نمی توانیم این کار را انجام دهیم ، و در نتیجه کد ما پر از تست هایی مانند:

که کد را به هم ریخته ، معنای آن را مبهم می کند و فراموش می شود. خیلی ساده تر

که همیشه کار خواهد کرد ، از جمله هنگامی که یک LST خالی به یک شیء خالی اشاره دارد.

مقادیر تهی را از ساختار داده خود دور نگه دارید و زندگی شما شادتر خواهد بود.

نوع اعلام شده در مقابل نوع واقعی

اکنون که ما از رابط ها و کلاس ها استفاده می کنیم ، ارزش آن را دارد که یک لحظه را تقویت کنیم تا نکته مهمی را در مورد چگونگی عملکرد نوع بررسی جاوا تقویت کنیم. در حقیقت ، هر زبان شیء محور بررسی شده از این طریق کار می کند.

دو جهان در بررسی نوع وجود دارد: قبل از اجرای برنامه ، زمان کامپایل را کامپایل کنید و زمان اجرای برنامه را اجرا کنید.

در زمان کامپایل ، هر متغیر دارای یک نوع اعلام شده است که در اعلامیه خود بیان شده است. کامپایلر از انواع متغیرهای اعلام شده (و مقادیر بازگشت روش) برای استنباط انواع اعلام شده برای هر بیان در برنامه استفاده می کند.

در زمان اجرا ، هر شیء دارای یک نوع واقعی است که توسط سازنده ای که شی را ایجاد کرده است در آن قرار می گیرد. به عنوان مثال ، رشته جدید () شیئی را ایجاد می کند که نوع واقعی آن رشته است. خالی جدید () یک شیء را ایجاد می کند که نوع واقعی آن خالی است. New Imlist () توسط جاوا ممنوع است ، زیرا Imlist یک رابط است - هیچ ارزش شیء خود را ندارد و سازنده ای ندارد.

تمرینات خواندن

همان کد دوباره:

این بار ، هنگامی که می گوییم نوع اعلام شده/واقعی یک متغیر ، ما همیشه به معنای خود متغیر یا شیء است که به آن متغیر اشاره می شود ، هر کدام مناسب باشد.

نوع اعلام شده کلمات 1 چیست؟

مثال دیگر: فرمول های بولی

یکی دیگر از نوع های مفید داده های بازگشتی در علوم کامپیوتر برای فرمول های بولی است. به عنوان مثال ، در اینجا یک فرمول منطق گزاره وجود دارد:

این بدان معنی است که "یا P یا Q درست است ، و یا p نادرست است یا R درست است."

ما می توانیم یک تعریف DataType مناسب برای نشان دادن همه فرمول های منطق گزاره ارائه دهیم.

(p ∨ q) ∧ (¬p ∨ r) خواهد بود

تمرینات خواندن

آلیسا و بن در حال مطالعه داده های بازگشتی برای فرمول های بولی هستند.

بن پیشنهاد می کند که نوع Not را از NOT (فرمول: فرمول) به NOT (VAR: متغیر) تغییر دهد. آلیسا فکر نمی کند که این کار کند. کدام یک از این فرمول ها را باید به عنوان پیشخوان ارائه دهد؟

Alyssa تصمیم می گیرد که او می خواهد یک عملیات برای بازیابی همه نامهای متغیر در یک فرمول به عنوان مجموعه ، با استفاده از نوع تغییر ناپذیر مجموعه IMSET:

متغیرها: فرمول → imset

فرض کنید IMSet تغییر ناپذیر سه عمل را فراهم می کند:

set-tempy: void → imset // یک مجموعه خالی را برمی گرداند

set-add: e × imset → imset // یک مجموعه و یک عنصر می گیرد و مجموعه (بدون تکراری) را با آن عنصر اضافه می کند

Set-Union: IMSET × IMSET → IMSET // اتحادیه (بدون تکراری) دو مجموعه را برمی گرداند

برای تعریف متغیرها از این عملیات استفاده کنید. ما دو مورد را برای شما تعریف کرده ایم:

چگونه می توانیم IMSET تغییر ناپذیر را اجرا کنیم؟بیایید از Imlist استفاده کنیم!

در اینجا تعریف DataType ، برای IMSET وجود دارد:

بیایید عملیات را با استفاده از نماد عملکرد تعریف کنیم. چهار عمل اصلی IMLIST را به خاطر بسپارید:

خالی: void → imlist منفی: e × imlist → imlist اول: imlist → E استراحت: imlist → imlist

به علاوه این موارد اضافی را که تعریف کردیم:

اندازه: imlist → int شامل: imlist × e → boolean

ما برای شما خالی تعریف خواهیم کرد:

Set-خالی: void → imset

و فرض کنید ما با استفاده از اندازه اندازه تنظیم را پیاده سازی می کنیم:

اندازه تنظیم: imset → int

این تعاریف بازگشتی را کامل کنید:

set-add: e × imset → imset

Set-Union: Imset × imset → imset

Set-Union (منفی (ELT ، REST) ، SET2) =

اشاره برای Set-Union: اولین استدلال را به پرونده پایه خالی نزدیک کنید.

یک عملیات کلیدی برای فرمولهای بولی ، آزمایش این است که آیا آنها رضایت بخش هستند ، یعنی اینکه آیا برخی از تعیین مقادیر واقعی/نادرست به متغیرها ، فرمول را برای ارزیابی صحیح هدایت می کند. یک الگوریتم ساده اما کند برای بررسی رضایت وجود دارد:

مجموعه متغیرها را از فرمول استخراج کنید. ما قبلاً این کار را با عملکرد متغیرها اجرا کرده ایم.

تمام تکالیف ممکن از مقادیر واقعی/نادرست را به آن متغیرها امتحان کنید. ما می توانیم یک تکلیف با یک محیط را نشان دهیم: لیستی از متغیرها و مقادیر آنها. ما می توانیم از IMList برای اجرای محیط استفاده کنیم یا یک نوع نقشه تغییر ناپذیر را توسعه دهیم.

فرمول هر محیط را ارزیابی کنید. برای این کار ، ما ارزیابی را تعریف خواهیم کرد: فرمول × محیط → بولی.

اولین محیطی را که فرمول در آن ارزیابی می کند ، برگردانید.

تعریف این قطعات و قرار دادن آنها در یک رضایت بخش: فرمول → عملکرد بولی یک تمرین برای زمان دیگری است.

جستجوی برگشت با تغییر ناپذیری

ما این بخش از خواندن را با لیست های تغییر ناپذیر شروع کردیم ، که نمایندگی ای است که امکان اشتراک زیادی بین نمونه های مختلف لیست را فراهم می کند. به اشتراک گذاشتن یک نوع خاص ، هر چند: فقط انتهای لیست ها در واقع می توانند به اشتراک گذاشته شوند. اگر دو لیست در ابتدا یکسان باشند اما از یکدیگر جدا شوند ، آنها باید جداگانه ذخیره شوند.(چرا؟)

به نظر می رسد که جستجوی پشتی یک برنامه عالی برای این لیست ها است ، و به همین دلیل است. جستجو از طریق یک فضا (مانند فضای تکالیف به مجموعه ای از متغیرهای بولی) به طور کلی با انجام یک انتخاب بعد از دیگری پیش می رود و وقتی یک انتخاب منجر به بن بست می شود ، شما عقب می زنید.

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

اما ساختار داده های تغییر ناپذیر و بدون اشتراک نیز ایده خوبی نیست ، زیرا فضایی که برای پیگیری جایی که در آن قرار دارید (در صورت بروز مشکل رضایت بخش ، محیط) به صورت چهارگانه رشد می کند اگر مجبور شوید یک نسخه کامل تهیه کنیدهر وقت قدم جدیدی بردارید. در صورت نیاز به تهیه نسخه پشتیبان ، باید تمام محیط های قبلی را در مسیر خود نگه دارید.

لیست های تغییر ناپذیر دارای ویژگی خوبی هستند که هر مرحله در مسیر می تواند تمام اطلاعات مربوط به مراحل قبلی را به اشتراک بگذارد ، فقط با اضافه کردن به قسمت جلوی لیست. هنگامی که مجبور به عقب نشینی هستید ، استفاده از حالت مرحله فعلی را متوقف می کنید - اما هنوز به وضعیت مرحله قبلی مراجعه می کنید.

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

خلاصه

علاوه بر ایده بزرگ داده های بازگشتی ، در این مطالعه دیدیم:

• تعاریف DataType: روشی قدرتمند برای فکر کردن در مورد انواع انتزاعی ، به ویژه موارد بازگشتی
• توابع بیش از داده های بازگشتی: در مشخصات نوع اعلام شده است و با یک مورد در هر نوع بتونی اجرا می شود
• لیست های تغییر ناپذیر: یک نمونه کلاسیک و متعارف از یک داده تغییر ناپذیر

مثل همیشه ، ما می پرسیم که چگونه این ایده ها کد ما را از اشکالات ایمن تر می کنند ، درک آن آسان تر و آماده تر برای تغییر است. دوباره به تعریف و اجرای اندازه () در Imlist نگاه کنید. تعریف کمی بیشتر از تعریف ریاضی اندازه است. کد کمی بیشتر از تعریف است ، با برخی از قسمت های اصلی برای قرار دادن کامپایلر.

اگر تعاریف را برای روشهای بیشتر-isEmpty ، حاوی و غیره بررسی کنیم-در هر صورت شاهد اجرای ایمن و آسان برای خواندن هستیم که منتظر کدگذاری هستند. از آنجا که ما وقت خود را برای مشخص کردن این عملیات ها گرفته ایم ، اگر از قرار گرفتن در معرض بازپرداخت و استقلال Rep خودداری کنیم ، می دانیم که کد ما برای تغییر آماده است: مشتریان مختلف قادر به استفاده مجدد از داده های ما خواهند بود و ما قادر به به روزرسانی اجرای خواهیم بودبدون شکستن آنها

بعدی: نوشتن برنامه با ADTS

همکاری مشترک با مشارکتهای: سامان اماراسینگه ، آدام کلیپالا ، سرینی دیواداس ، مایکل ارنست ، مکس گلدمن ، جان گوتاگ ، دانیل جکسون ، راب میلر ، مارتین رینارد و آرماندو سولاری-لیزاما. این کار تحت CC BY-SA 4. 0 مجوز دارد.

بایگانی سایت دوره بهار 2017 |آخرین سایت در mit. edu/6. 031 |دسترسی