اگر اظهارات ، حلقه ها و بازگشت

OCAML دارای یک جمله IF با دو تغییر و معنای بارز است:

بر خلاف زبان های معمولی که از آنها استفاده خواهید شد ، اگر اظهارات واقعاً عبارات هستند. به عبارت دیگر ، آنها بسیار بیشتر شبیه Boolean-Condition هستند؟بیان: بیان دیگر در C نسبت به جمله های اگر ممکن است از آنها استفاده شود.

در اینجا یک مثال ساده از یک جمله IF آورده شده است:

به عنوان یک گذشته ، اگر این را در OCAML Interactive Toplevel (همانطور که در بالا) تایپ کنید ، متوجه می شوید که OCAML تصمیم می گیرد که این عملکرد چند شکل است ، با نوع زیر:

و در واقع OCAML به شما امکان می دهد از حداکثر در هر نوع استفاده کنید:

This is because>در واقع چند شکل است. این کار بر روی هر نوع ، حتی اشیاء (مقایسه باینری انجام می دهد) کار می کند.

[توجه داشته باشید که ماژول stdlib حداقل و حداکثر را برای شما تعریف می کند.]

بیایید کمی بیشتر به بیان IF نگاه کنیم. در اینجا عملکرد دامنه ای وجود دارد که من قبلاً بدون توضیحات زیاد به شما نشان دادم. شما باید بتوانید دانش خود را در مورد توابع بازگشتی ، لیست ها و در صورت عبارات ترکیب کنید تا ببینید چه کاری انجام می دهد:

Let's examine some typical calls to this function. Let's start with the easy case of a>ب. تماس با محدوده 11 10 بازگشت [] (لیست خالی) و این است.

What about calling range 10 10 ? Since 10>10 نادرست است ، دیگر ی-طبقه بندی ارزیابی می شود: 10 :: (محدوده 11 10) (من براکت ها را اضافه کرده ام تا ترتیب ارزیابی واضح تر شود). ما به تازگی آن محدوده 11 10 = [] را کار کرده ایم ، بنابراین این: 10 :: [] است. توضیحات رسمی ما در مورد لیست ها و اپراتور :: (منفی) را به خاطر می آورید؟10 :: [] دقیقاً همان [10] است.

بیایید محدوده 9 10 را امتحان کنیم:

باید کاملاً واضح باشد که دامنه 1 10 به [1 ؛23 ؛4 ؛5 ؛6 ؛7 ؛8 ؛9 ؛10]

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

به طور موقت ، به اظهارات. این عملکرد چه کاری انجام می دهد؟

سرنخ: براکت ها را در کل بیان IF اضافه کنید. این مانند یک دیود الکترونیکی است.

تابع ABS (مقدار مطلق) در stdlib به این صورت تعریف شده است:

همچنین در stdlib ، عملکرد String_of_float شامل یک جفت پیچیده از تو در تو در صورت عبارات است:

بیایید این عملکرد را بررسی کنیم. فرض کنید این تابع با f = 12. 34 خوانده می شود. سپس S = "12. 34" ، و L = 5. اولین بار با I = 0 حلقه می نامیم.

من از L بیشتر یا مساوی نیستم ، و s. [i] (شخصیت I در S) یک دوره یا "E" نیست. بنابراین حلقه (i + 1) نامیده می شود ، یعنی. حلقه 1.

ما برای I = 1 همان رقص را طی می کنیم و در نهایت به حلقه 2 فراخوانی می کنیم.

برای i = 2 ، با این حال ، s. [i] یک دوره است (به رشته اصلی مراجعه کنید ، S = "12. 34") r. بنابراین این بلافاصله S را برمی گرداند ، و عملکرد string_of_float "12. 34" را برمی گرداند.

حلقه چه کاری انجام می دهد؟در واقع این بررسی می کند که آیا رشته از format_float برگشته است که شامل یک دوره (یا 'E') است. فرض کنید که ما String_of_float را با 12. 0 نامیدیم. format_float رشته "12" را برمی گرداند ، اما String_of_float باید "12." را برگرداند. یا "12. 0" (زیرا ثابت های نقطه شناور در OCAML باید شامل دوره ای برای تمایز آنها از ثابت های عدد صحیح باشند). از این رو چک

استفاده عجیب از بازگشت در این عملکرد تقریباً برای کارآیی است. OCAML از حلقه ها پشتیبانی می کند ، پس چرا نویسندگان از حلقه ها استفاده نکردند؟در بخش بعدی خواهیم دید که OCAML برای حلقه ها به روشی محدود است که مانع از استفاده از آنها در string_of_float می شود. با این حال ، در اینجا ، یک روش ساده تر ، اما تقریباً دو برابر کند ، روش نوشتن string_of_float:

با استفاده از شروعپایان

در اینجا چند کد از Lablgtk آورده شده است:

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

کاملاً براکت و به درستی تورفتگی عبارت فوق:

نه آنچه اصلاً در نظر گرفته شده بود. بنابراین شروع و پایان لازم است تا چندین بیانیه را در یک بند یا بند دیگر از بیان IF به هم بپیوندید. اگر ترجیح می دهید (و من ترجیح می دهم ، می توانید از پرانتزهای معمولی ساده استفاده کنید (و من ترجیح می دهم ، زیرا من پاسکال را بدبختم :-). در اینجا دو مثال ساده وجود دارد:

برای حلقه ها و در حالی که حلقه ها

OCAML از یک شکل نسبتاً محدود از آشنا برای حلقه پشتیبانی می کند:

یک مثال ساده اما واقعی از LABLGTK:

در OCAML ، برای حلقه ها فقط برای نوشتن کوتاه است:

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

بیان داخل یک OCAML برای حلقه باید به واحد ارزیابی شود (در غیر این صورت شما یک هشدار دریافت خواهید کرد) ، و بیان برای حلقه به عنوان یک واحد کل بازگشت:

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

در حالی که حلقه های OCAML نوشته شده است:

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

اگر جلوی حلقه ها را گرفتید ، ممکن است ببینید که آنها واقعاً فایده ای ندارند ، مگر در رابطه با منابع قدیمی ما. بیایید تصور کنیم که OCAML برای لحظه ای منابع نداشت:

به یاد داشته باشید که Quit_Loop یک "متغیر" واقعی نیست - Le t-Binding فقط Quit_Loop را برای کاذب تبدیل می کند. این بدان معنی است که شرایط حلقه در حالی که به رنگ قرمز نشان داده شده است همیشه درست است ، و حلقه برای همیشه ادامه می یابد!

خوشبختانه OCAML دارای منابع است ، بنابراین اگر بخواهیم می توانیم کد بالا را بنویسیم. گیج نشوید و فکر کنید که!(علامت تعجب) به معنای "نه" مانند C/Java است. این در اینجا به معنای "نمایشگر نشانگر" است ، در واقع با FORTH. شما بهتر از خواندن هستید! به عنوان "دریافت" یا "Deref".

حلقه بیش از لیست ها

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

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

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

List. Iter در واقع همان چیزی است که شما باید در مورد استفاده اول از هر بار که مخچه شما پیشنهاد می کند از یک حلقه استفاده کنید.

اگر می خواهید هر عنصر را به طور جداگانه در لیست تغییر دهید - به عنوان مثال ، هر عنصر را در لیست دو برابر کنید - سپس از List. map استفاده کنید.

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

برای اطلاع از اینکه آیا یک لیست حاوی برخی از عناصر است ، از List. mem (کوتاه برای عضو) استفاده کنید:

list. for_all و list. exists همان اپراتورهای "forall" و "وجود" در منطق محمول هستند.

برای کار کردن بیش از دو لیست به طور همزمان ، انواع "-2" از برخی از این توابع وجود دارد ، یعنی iter2 ، map2 ، for_all2 ، 2.

توابع نقشه و فیلتر بر روی عناصر لیست فردی در انزوا کار می کنند. Fold یک عمل غیرمعمول تر است که به بهترین وجه در مورد "قرار دادن یک اپراتور بین هر عنصر لیست" فکر می شود. فرض کنید می خواستم تمام شماره های موجود در لیست خود را با هم اضافه کنم. به صورت دست و پا زدن به آنچه من می خواهم انجام دهم این است که یک علامت به علاوه بین عناصر موجود در لیست من وارد کنید:

عملیات برابر این کار را انجام می دهد ، اگرچه جزئیات دقیق کمی مشکل تر است. اول از همه ، اگر سعی کنم یک لیست خالی را جمع کنم چه اتفاقی می افتد؟در صورت جمع بندی لیست ، اگر جواب صفر باشد ، به جای خطا ، خوب خواهد بود. با این حال اگر من سعی می کردم محصول لیست را پیدا کنم ، می خواهم به جای آن پاسخ یکی باشد. بنابراین من بدیهی است که من باید نوعی استدلال "پیش فرض" را برای برابر خود ارائه دهم. مسئله دوم با اپراتورهای ساده مانند + و * بوجود نمی آید: اگر اپراتور من از آن استفاده می کنم ، چه اتفاقی می افتد ، یعنی.(A Op B) OP C برابر با OP (B OP C) نیست؟در این حالت مهم است که آیا من از انتهای سمت چپ لیست شروع کردم و به درستی کار کردم ، در مقابل اگر من از سمت راست شروع کردم و به سمت چپ کار کردم. به همین دلیل دو نسخه از Fold وجود دارد ، به نام List. Fold_Left (کار از چپ به راست) و List. fold_right (درست به چپ کار می کند ، و همچنین کارآمدتر است).

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

آن آسان بود! توجه کنید که من به طور تصادفی راهی برای انجام فاکتورهای ریاضی ارائه داده ام:

(توجه کنید که این عملکرد فاکتوریل بسیار مفید نیست زیرا این عدد صحیح را سرریز می کند و حتی برای مقادیر بسیار کمی از n پاسخ های اشتباه می دهد.)

حلقه زدن بر روی رشته ها

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

string. copy یک رشته را مانند strdup کپی می کند. همچنین یک تابع string. iter وجود دارد که مانند List. iter کار می کند ، به جز شخصیت های رشته.

بازگشت

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

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

در مثال اول می خواهیم کل یک پرونده را در حافظه بخوانیم (به یک رشته طولانی). اساساً سه رویکرد ممکن در این مورد وجود دارد:

رویکرد 1

طول پرونده را دریافت کنید و با استفاده از روش واقعاً_Input همه آن را با یک حرکت بخوانید. این ساده ترین است ، اما ممکن است در کانال هایی که واقعاً پرونده نیستند کار نکند (به عنوان مثال خواندن ورودی صفحه کلید) به همین دلیل ما به دو رویکرد دیگر نگاه می کنیم.

رویکرد 2

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

نزدیک شدن 3

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

ما قصد داریم چند مفهوم جدید را در اینجا معرفی کنیم. دو رویکرد دوم ما از ماژول بافر استفاده می کنند - یک بافر قابل ارتقا که می توانید مانند یک رشته فکر کنید که می توانید در انتها متن بیشتری را اضافه کنید. ما همچنین می خواهیم استثناء end_of_file را که توابع ورودی هنگام رسیدن به انتهای ورودی پرتاب می کنند ، بدست آوریم. همچنین می خواهیم از Sys. Argv استفاده کنیم. (1) برای دریافت پارامتر خط فرمان اول.

رویکرد 1 کار می کند اما بسیار رضایت بخش نیست زیرا Read_whole_chan در کانال های غیر پرونده ای مانند ورودی صفحه کلید یا سوکت کار نمی کند. رویکرد 2 شامل یک حلقه مدتی است:

نکته اصلی نزدیک شدن به 2 نگاه به حلقه مرکزی است. به یاد داشته باشید که من گفتم تنها راه برای بیرون آمدن از حلقه در اوایل اوایل با یک استثنا بود؟این دقیقاً همان کاری است که ما در اینجا انجام می دهیم. اگرچه من هنوز استثنائاتی را پوشش نداده ام ، احتمالاً شما در درک استثناء END_OF_FILE که در کد فوق توسط input_line پرتاب شده است ، هنگام برخورد به انتهای پرونده ، مشکلی نخواهید داشت. Buf Buf محتویات پرونده را جمع می کند و وقتی به انتهای پرونده رسیدیم ، آن را برمی گردانیم (Buffer. Contents BUF).

یک نکته جالب در مورد این ، بیانیه ظاهراً اضافی (ادعای نادرست) درست بعد از حلقه در حالی است. این برای چیست؟به یاد داشته باشید که در حالی که حلقه ها ، مانند حلقه ها ، فقط عبارات هستند و شیء واحد (()) را برمی گردانند. با این حال OCAML می خواهد که نوع بازگشت در داخل یک آزمایش با نوع بازگشت هر استثناء صید مطابقت داشته باشد. در این حالت به این دلیل که end_of_file منجر به یک رشته می شود ، بدنه اصلی امتحان نیز باید یک رشته را "برگردانید" - حتی اگر به دلیل نامحدود در حالی که حلقه در واقع نمی تواند برگردانده شود. ادعا False دارای یک نوع چند شکل است ، بنابراین با هر مقدار که توسط شاخه با آن بازگردانده می شود متحد می شود.

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

باز هم ما یک حلقه نامتناهی داریم - اما در این حالت با استفاده از بازگشت انجام می شود. حلقه در انتهای عملکرد خود را صدا می کند. هنگامی که input_line یک استثناء end_of_file را پرتاب می کند ، بازگشت بی نهایت شکسته می شود.

به نظر می رسد اگر یک پرونده مخصوصاً بزرگ به آن داده اید ، رویکرد 3 ممکن است پشته را سرریز کند ، اما این در واقع اینگونه نیست. به دلیل بازگشت دم (در زیر مورد بحث) ، کامپایلر عملکرد حلقه بازگشتی را به یک حلقه واقعی تبدیل می کند (!) که در فضای پشته ثابت اجرا می شود.

در مثال بعدی ما نشان خواهیم داد که چگونه بازگشت برای ساخت یا بررسی انواع خاصی از ساختارهای داده ، به ویژه درختان عالی است. بیایید یک نوع بازگشتی داشته باشیم تا پرونده ها را در یک سیستم فایل نشان دهیم:

توابع OpenDir و Readdir برای باز کردن دایرکتوری و خواندن عناصر از فهرست استفاده می شود. من قصد دارم یک تابع مفید readdir_no_ex را تعریف کنم که استثناء آزار دهنده end_of_file را که Readdir هنگام رسیدن به انتهای فهرست می اندازد پنهان می کند:

نوع readdir_no_ex این است. بحث قبلی ما در مورد نشانگرهای تهی را به یاد بیاورید.

من همچنین می خواهم یک عملکرد بازگشتی ساده را تعریف کنم که می توانم از آن برای تبدیل نوع سیستم فایل به یک رشته برای (به عنوان مثال) چاپ استفاده کنم:

توجه داشته باشید به استفاده از fold_left و نقشه. نقشه مورد استفاده قرار می گیرد (به صورت بازگشتی) هر سیستم فایل را در لیست به یک رشته تبدیل می کند. سپس fold_left (^) "" لیست را با هم در یک رشته بزرگ جمع می کند. همچنین به استفاده از تطبیق الگوی توجه کنید..

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

فراخوان OpenDir مسیر داده شده را باز می کند و یک dir_handle را باز می گرداند که از آن می توانیم نام ها را با استفاده از readdir_no_ex بعداً بخوانیم. مقدار بازگشت عملکرد یک دایرکتوری FS_LIST خواهد بود ، بنابراین تنها کاری که باید برای تکمیل عملکرد انجام دهیم نوشتن حلقه عملکرد ما است که لیستی از سیستم های فایل را برمی گرداند. نوع حلقه خواهد بود:

چگونه حلقه را تعریف کنیم؟بیایید دوباره آن را در مراحل انجام دهیم.

ابتدا نام پرونده بعدی را از دسته دایرکتوری می خوانیم. نام پرونده دارای گزینه رشته ای است ، به عبارت دیگر می تواند هیچ یک یا برخی از "foo" باشد که foo نام نام پرونده بعدی در فهرست است. ما همچنین باید "" "را نادیده بگیریم. و پرونده های ".." (یعنی فهرست فعلی و فهرست والدین). ما می توانیم همه این کارها را با یک مسابقه الگوی خوب انجام دهیم:

هیچ موردی آسان نیست. فکر کردن به صورت بازگشتی (!) اگر حلقه فراخوانده شود و ما به انتهای دایرکتوری رسیده ایم ، حلقه باید لیستی از ورودی ها را برگرداند - و هیچ ورودی وجود ندارد - بنابراین لیست خالی را برمی گرداند ([]).

برای "."و ".." ما فقط پرونده را نادیده می گیریم و دوباره حلقه تماس می گیریم.

وقتی Loop یک نام واقعی را می خواند (برخی از نام پرونده های زیر) چه کاری انجام می دهیم؟بگذارید PathName مسیر کامل پرونده باشد. ما پرونده را برای دیدن اینکه آیا واقعاً یک دایرکتوری است ، "Stat" می کنیم. اگر این یک دایرکتوری باشد ، ما این کار را با فراخوانی مجدد Read_Directory تنظیم می کنیم که دایرکتوری را به چیزی باز می گرداند. توجه کنید که نتیجه کلی Read_Directory فهرست (حلقه ()) است. اگر پرونده واقعاً یک پرونده است (نه یک دایرکتوری) ، ما اجازه می دهیم این پرونده پرونده باشد. سپس ما کاری هوشمندانه انجام می دهیم: این حلقه :: را برمی گردانیم (). این فراخوان بازگشتی برای حلقه () برای محاسبه اعضای دایرکتوری باقیمانده (لیستی) است که ما این را پیش می بریم.

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

استفاده از بازگشت برای ساخت لیست:

این را با عملکرد محدوده قبلی ما مقایسه کنید. الگوی بازگشت دقیقاً یکسان است:

استفاده از بازگشت برای ساختن درختان:

تمام آنچه اکنون برای ساختن این یک برنامه کاری باقی مانده است ، کمی کد برای تماس با read_directory و نمایش نتیجه است:

مثال بازگشت: حداکثر عنصر در یک لیست

الگوی اصلی بازگشت برای لیست ها را به خاطر بسپارید:

نکته اصلی در اینجا در واقع استفاده از الگوی موردی / موردی / حالت بازگشتی است. در این مثال - یافتن حداکثر عنصر در یک لیست - ما قصد داریم دو مورد پایه و یک مورد بازگشتی داشته باشیم. اما قبل از اینکه من به سمت کد پرش کنم ، بیایید قدم به عقب برگردیم و در مورد مشکل فکر کنیم. با فکر کردن در مورد مشکل ، راه حل "گویی توسط جادو" ظاهر می شود (من به شما قول می دهم :-)

اول از همه ، بیایید واضح باشیم که حداکثر عنصر یک لیست فقط بزرگترین است ، به عنوان مثالحداکثر عنصر لیست [1 ؛23 ؛4 ؛1] 4 است.

آیا موارد خاصی وجود دارد؟بله ، وجود داردحداکثر عنصر لیست خالی [] چیست؟یکی نیستاگر از لیست خالی عبور کنیم ، باید خطایی پرتاب کنیم.

حداکثر عنصر یک لیست عنصر واحد مانند [4] چیست؟این آسان است: این فقط خود عنصر است. بنابراین list_max [4] باید 4 را برگرداند ، یا در مورد کلی ، list_max [x] باید x را برگرداند.

حداکثر عنصر لیست عمومی x :: باقی مانده چیست (این علامت "منفی" برای لیست است ، بنابراین باقی مانده است - همچنین یک لیست)؟

Think about this for a while. Suppose you know the maximum element of remainder , which is, say, y . What's the maximum element of x :: remainder ? It depends on whether x>Y یا X

آیا این واقعاً کار می کند؟در نظر بگیرید [1 ؛23 ؛4 ؛1] دوبارهاین 1 :: [2 ؛3 ؛4 ؛1]اکنون حداکثر عنصر باقیمانده ، [2 ؛3 ؛4 ؛1] ، 4 است. بنابراین اکنون ما به x = 1 و y = 4 علاقه مند هستیم. این عنصر سر x = 1 مهم نیست زیرا y = 4 بزرگتر است ، بنابراین حداکثر کلی کل لیست y = 4 است.

بیایید اکنون آن قوانین را در بالا کدگذاری کنیم تا یک عملکرد کار را بدست آوریم:

من نظرات اضافه کردم تا بتوانید ببینید که چگونه قوانین / موارد ویژه ای که در بالا تصمیم گرفتیم واقعاً با خطوط کد مطابقت دارد.

توجه کنید که راه حل پیشنهادی هر دو (الف) بسیار متفاوت از راه حل ضروری برای حلقه است ، و (ب) بسیار نزدیکتر با مشخصات مشکل مرتبط است. برنامه نویسان عملکردی به شما خواهند گفت که دلیل این امر این است که سبک عملکردی بسیار بالاتر از سبک ضروری است و بنابراین بهتر و ساده تر است. این که آیا شما آنها را باور دارید به شما بستگی دارد. مطمئناً درست است که استدلال منطقی در مورد نسخه کاربردی بسیار ساده تر است ، که اگر می خواهید به طور رسمی ثابت کنید که لیست_مکس صحیح است ("صحیح" بودن یک روش ریاضی برای گفتن اینکه یک برنامه بدون اشکال است ، برای فضا مفید است ، مفید است. شاتل ها ، نیروگاه های هسته ای و به طور کلی نرم افزار با کیفیت بالاتر).

بازگرداندن

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

من قصد دارم آن را کمی بازنویسی کنم تا چیزی در مورد ساختار برنامه واضح تر (هنوز هم همان عملکرد) ایجاد کنم:

هومدر نگاه اول این به نظر می رسد مشکلی در برنامه نویسی بازگشتی و از این رو با کل برنامه نویسی کاربردی است! اگر کد خود را به جای تکراری به صورت بازگشتی بنویسید ، لزوماً فضای پشته را روی ورودی های بزرگ تمام می کنید ، درست است؟

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

در توابع دم بازگشتی، فراخوانی بازگشتی آخرین اتفاق می افتد. توابع حلقه () بالا را به خاطر دارید؟همه آنها این شکل را داشتند:

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

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

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

The accum argument is going to accumulate the result. It's the "result so far". We pass in the empty list ("no result so far"). The easy case is when a>ب :

If a>b (یعنی اگر به پایان بازگشت رسیده ایم)، سپس متوقف شده و نتیجه (accum) را برگردانید.

اکنون ترفند این است که عبارت else را بنویسیم و مطمئن شویم که فراخوانی range2 آخرین کاری است که انجام می دهیم، بنابراین تابع tail-recursive است:

فقط یک مشکل جزئی با این تابع وجود دارد: لیست را به عقب می سازد! با این حال، با تعریف مجدد محدوده به راحتی می توان آن را اصلاح کرد:

این بار کار می کند، اگرچه اجرای آن کمی کند است زیرا واقعاً باید یک لیست با میلیون ها عنصر در آن ایجاد کند:

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

این یک مرور مختصر از بازگشت دم بود، اما در موقعیت های دنیای واقعی، تعیین اینکه آیا یک تابع بازگشتی است یا نه، می تواند بسیار سخت باشد. واقعاً اینجا چه چیزی یاد گرفتیم؟یک چیز این است که توابع بازگشتی یک تله خطرناک برای برنامه نویسان بی تجربه دارند. به نظر می رسد که عملکرد شما برای ورودی های کوچک (در حین آزمایش) کار می کند، اما وقتی در معرض ورودی های بزرگ قرار می گیرید، به طرز فاجعه باری در میدان شکست می خورد. این یک استدلال علیه استفاده از توابع بازگشتی، و برای استفاده از حلقه های while صریح در صورت امکان است.

رکوردها، مراجع (دوباره!) و آرایه های قابل تغییر

پیش از این ما سوابق را در گذر ذکر کردیم. اینها مانند C ساختار S هستند:

یکی از ویژگی هایی که من پوشش ندادم: OCAML Records می تواند زمینه های قابل تغییر را داشته باشد. به طور معمول عبارتی مانند یک شیء تغییر ناپذیر و ثابت است. اما اگر رکورد دارای زمینه های قابل تغییر باشد ، راهی برای تغییر آن زمینه ها در رکورد وجود دارد. این یک ویژگی ضروری OCAML است ، زیرا زبانهای عملکردی معمولاً اجازه نمی دهند اشیاء قابل تغییر (یا منابع یا آرایه های قابل تغییر ، که در یک لحظه به آنها نگاه خواهیم کرد).

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

در اینجا تابعی تعریف شده بر روی نام هایی که نام نام را چاپ می کند و قسمت Access_Count قابل تغییر را افزایش می دهد:

به یک ویژگی عجیب و بسیار غیر کاربردی Print_Name توجه کنید: این پارامتر Access_Count خود را اصلاح می کند. این عملکرد "خالص" نیست. OCAML یک زبان کاربردی است ، اما به حدی نیست که برنامه نویسی عملکردی را در گلو شما مجبور کند.

به هر حال ، بیایید print_name را در عمل ببینیم:

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

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

و از نزدیک به آنچه Ocaml Toplevel برای ارزش یک مرجع چاپ می کند ، نگاه کنید:

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

مبانی آرایه ها ساده است:

به نحو برای نوشتن آرایه ها توجه کنید: [|عنصر ؛عنصر ؛واد|]

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

توابع بازگشتی متقابل

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

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

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

در OCAML هیچ "نمونه اولیه رو به جلو" (همانطور که در زبانهایی که از C از C فرود آمده اند) وجود ندارد ، اما یک نحو ویژه برای تعریف مجموعه ای از دو یا چند عملکرد بازگشتی متقابل ، مانند عجیب و حتی وجود دارد:

همچنین می توانید از نحو مشابه برای نوشتن تعاریف و ماژول های کلاس متقابل متقابل استفاده کنید.