بازگشت

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

اگر هنوز نمی دانید بازگشت چیست ، این جمله را بخوانید. هاهافقط شوخی! بازگشت در واقع راهی برای تعریف توابع است که در آن عملکرد در تعریف خاص خود اعمال می شود. تعاریف در ریاضیات اغلب به صورت بازگشتی ارائه می شود. به عنوان مثال ، توالی فیبوناچی به صورت بازگشتی تعریف می شود. اول ، ما دو شماره فیبوناچی اول را غیر قابل تکرار تعریف می کنیم. ما می گوییم که f (0) = 0 و f (1) = 1 ، به این معنی که اعداد فیبوناچی 0 و 1 به ترتیب 0 و 1 هستند. سپس می گوییم برای هر عدد طبیعی دیگر ، این شماره فیبوناچی مجموع دو شماره فیبوناچی قبلی است. بنابراین f (n) = f (n-1) + f (n-2). به این ترتیب ، f (3) f (2) + f (1) است که (f (1) + f (0)) + f (1) است. از آنجا که اکنون ما فقط به شماره های فیبوناچی تعریف نشده تعریف شده رسیده ایم ، با اطمینان می توانیم بگوییم که F (3) 2 است. داشتن یک عنصر یا دو در یک تعریف بازگشت تعریف شده غیر مجازی (مانند F (0) و F (F ()1) در اینجا) همچنین شرایط لبه نامیده می شود و اگر می خواهید عملکرد بازگشتی شما خاتمه یابد ، مهم است. اگر ما F (0) و F (1) را غیر بازگشتی تعریف نکرده بودیم ، هرگز به هیچ وجه راه حلی دریافت نمی کنید زیرا به 0 می رسیدید و سپس به شماره های منفی می روید. ناگهان ، شما می خواهید بگویید که F (-2000) F (-2001) + F (-2002) است و هنوز هم به پایان نمی رسد!

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

حداکثر عالی

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

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

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

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

بیایید نمونه ای از شماره ها را بگیریم و بررسی کنیم که چگونه این کار روی آنها کار می کند: [2،5،1]. اگر حداکثر را در این مورد بنامیم ، دو الگوی اول مطابقت ندارند. مورد سوم و لیست به 2 و [5،1] تقسیم می شود. بند جایی که می خواهد حداکثر [5،1] را بداند ، بنابراین ما آن مسیر را دنبال می کنیم. دوباره با الگوی سوم مطابقت دارد و [5،1] به 5 و [1] تقسیم می شود. باز هم ، بند جایی که می خواهد حداکثر [1] را بداند. از آنجا که این شرایط لبه است ، 1 را برمی گرداند. سرانجام! بنابراین با یک مرحله بالا بروید ، با مقایسه 5 تا حداکثر [1] (که 1 است) ، ما بدیهی است که 5 برمی گردیم. بنابراین اکنون می دانیم که حداکثر [5،1] 5 است. ما دوباره یک قدم بالا می رویم که 2 و [5،1] داشتیم. مقایسه 2 با حداکثر [5،1] ، که 5 است ، ما 5 را انتخاب می کنیم.

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

این برای ظریف چطوره! در اصل ، حداکثر یک لیست حداکثر عنصر اول و حداکثر دم است.

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

اکنون که می دانیم چگونه به طور کلی به صورت بازگشتی فکر کنیم، اجازه دهید چند تابع را با استفاده از بازگشت پیاده سازی کنیم. ابتدا، replicate را پیاده سازی می کنیم. replicate یک Int و یک عنصر را می گیرد و لیستی را برمی گرداند که چندین تکرار از یک عنصر دارد. برای مثال، 3 5 را تکرار کنید [5،5،5]. بیایید در مورد شرایط لبه فکر کنیم. حدس من این است که شرط لبه 0 یا کمتر است. اگر سعی کنیم چیزی را صفر بار تکرار کنیم، باید یک لیست خالی برگرداند. همچنین برای اعداد منفی، زیرا واقعاً معنی ندارد.

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

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

در مرحله بعد، take را اجرا می کنیم. تعداد معینی از عناصر را از یک لیست می گیرد. به عنوان مثال، 3 [5،4،3،2،1] را انتخاب کنید [5،4،3]. اگر سعی کنیم 0 یا کمتر عنصر را از یک لیست بگیریم، یک لیست خالی دریافت می کنیم. همچنین اگر بخواهیم چیزی را از یک لیست خالی برداریم، یک لیست خالی دریافت می کنیم. توجه داشته باشید که این دو شرط لبه هستند. پس بیایید آن را بنویسیم:

الگوی اول مشخص می کند که اگر بخواهیم 0 یا تعداد منفی عناصر را بگیریم، یک لیست خالی دریافت می کنیم. توجه داشته باشید که ما از _ برای مطابقت با لیست استفاده می کنیم، زیرا واقعاً برایمان مهم نیست که در این مورد چیست. همچنین توجه داشته باشید که ما از محافظ استفاده می کنیم، اما بدون قطعه دیگری. این بدان معناست که اگر معلوم شود n بیش از 0 است، تطابق به الگوی بعدی می افتد. الگوی دوم نشان می دهد که اگر بخواهیم چیزی را از یک لیست خالی برداریم، یک لیست خالی دریافت می کنیم. الگوی سوم لیست را به یک سر و یک دم تقسیم می کند. و سپس بیان می کنیم که گرفتن n عنصر از یک لیست برابر با لیستی است که x به عنوان سر و سپس لیستی که n-1 عنصر را از دم به عنوان دنباله می گیرد. سعی کنید از یک تکه کاغذ استفاده کنید تا بنویسید اگر سعی کنیم مثلاً 3 را از [4،3،2،1] بگیریم، ارزیابی چگونه به نظر می رسد.

معکوس به سادگی یک لیست را معکوس می کند. به وضعیت لبه فکر کنید. چیه؟بیا دیگه . این لیست خالی است! یک لیست خالی معکوس با خود لیست خالی برابر است. باشه. بقیه آن چطور؟خوب ، می توانید بگویید که اگر لیستی را به یک سر و دم تقسیم کنیم ، لیست معکوس برابر با دم معکوس و سپس سر در انتها است.

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

تماس با تکرار 3 لیستی را به ما می دهد که با 3 شروع می شود و سپس مقدار نامحدود 3 را به عنوان دم دارد. بنابراین تماس با تکرار 3 مانند 3: تکرار 3 ، که 3: (3: تکرار 3) است ، که 3: (3: (3: تکرار 3)) است ، و غیره. تکرار 3 هرگز ارزیابی نمی شود ، در حالی که 5 طول می کشد(تکرار 3) لیستی از پنج 3 را به ما ارائه می دهد. بنابراین اساساً مانند انجام تکرار 5 3 است.

زیپ دو لیست می گیرد و آنها را با هم زیپ می کند. zip [1،2،3] [2،3] بازگشت [(1،2) ، (2،3)] ، زیرا لیست طولانی تر را برای مطابقت با طول کوتاه تر کوتاه می کند. اگر چیزی را با لیست خالی زیپ می کنیم چطور؟خوب ، ما در آن زمان یک لیست خالی دریافت می کنیم. بنابراین شرایط لبه ما وجود دارد. با این حال ، ZIP دو لیست را به عنوان پارامتر می گیرد ، بنابراین در واقع دو شرایط لبه وجود دارد.

دو الگوی اول می گویند اگر لیست اول یا لیست دوم خالی باشد ، ما یک لیست خالی دریافت می کنیم. مورد سوم می گوید که دو لیست فشرده مساوی با جفت کردن سرشان و سپس بر روی دمهای زیپ شده است. Zipping [1،2،3] و ['A' ، 'B'] در نهایت سعی خواهد کرد [3] را با [] زیپ کنید. الگوهای شرط لبه شروع می شود و نتیجه آن (1 ، 'a') :( 2 ، 'b'): [] ، که دقیقاً مشابه [(1 ، 'a ") ، (2 ،' b است')].

بیایید یک عملکرد استاندارد کتابخانه - Elem را پیاده سازی کنیم. این یک عنصر و یک لیست را می گیرد و می بیند که آیا این عنصر در لیست است یا خیر. وضعیت لبه ، همانطور که بیشتر اوقات با لیست ها وجود دارد ، لیست خالی است. ما می دانیم که یک لیست خالی حاوی هیچ عناصر نیست ، بنابراین مطمئناً Droids مورد نظر ما را ندارد.

بسیار ساده و انتظار می رود. اگر سر عنصر نیست ، ما دم را بررسی می کنیم. اگر به یک لیست خالی برسیم ، نتیجه نادرست است.

سریع ، مرتب سازی!

ما لیستی از مواردی داریم که می توانند مرتب شوند. نوع آنها نمونه ای از Typeclass Ord است. و اکنون ، ما می خواهیم آنها را مرتب کنیم! یک الگوریتم بسیار جالب برای مرتب سازی به نام QuickSort وجود دارد. این یک روش بسیار هوشمندانه برای مرتب سازی موارد است. در حالی که برای پیاده سازی QuickSort به زبانهای ضروری از 10 خط به بالا می رود ، اجرای آن در هاکل بسیار کوتاه تر و ظریف است. QuickSort به نوعی کودک پوستر برای هاکل تبدیل شده است. بنابراین ، بیایید آن را در اینجا پیاده سازی کنیم ، حتی اگر اجرای QuickSort در Haskell واقعاً پنیر محسوب می شود زیرا همه این کار را می کنند تا نشان دهند که چقدر ظریف هاسکل است.

So, the type signature is going to be quicksort :: (Ord a) => [a] ->[آ] . جای تعجب در آنجا نیست. وضعیت لبه؟همانطور که انتظار می رود لیست خالی. یک لیست خالی مرتب شده یک لیست خالی است. اکنون الگوریتم اصلی در اینجا آمده است: یک لیست مرتب شده لیستی است که تمام مقادیر کوچکتر از (یا مساوی) سر لیست در جلو (و آن مقادیر مرتب شده است) ، سپس سر لیست در وسط می آیدو سپس تمام مقادیر بزرگتر از سر را بیاورید (آنها نیز مرتب شده اند). توجه کنید که ما در این تعریف دو بار مرتب شده ایم ، بنابراین احتمالاً باید دو بار تماس بازگشتی برقرار کنیم! همچنین توجه داشته باشید که ما آن را با استفاده از فعل تعریف کردیم ، تعریف الگوریتم به جای گفتن این کار ، این کار را انجام دهید ، سپس این کار را انجام دهید. واداین زیبایی برنامه نویسی کاربردی است! چگونه می خواهیم لیست را فیلتر کنیم تا فقط عناصر کوچکتر از سر لیست خود و فقط عناصر بزرگتر را بدست آوریم؟درک مطلب. بنابراین ، بیایید شیرجه بزنیم و این عملکرد را تعریف کنیم.

بیایید یک آزمایش کوچک به آن بدهیم تا ببینیم آیا به نظر می رسد درست رفتار می کند یا خیر.

بوویاین همون چیزیه که من درباره اش حرف می زنم! بنابراین اگر داشته باشیم ، می گویند [5،1،9،4،6،7،7،3] و ما می خواهیم آن را مرتب کنیم ، این الگوریتم ابتدا سر را می گیرد ، که 5 است و سپس آن را در وسط دو لیست قرار می دهد کهکوچکتر و بزرگتر از آن هستند. بنابراین در یک مقطع ، [1،4،3] ++ [5] ++ [9،6،7] را خواهید داشت. ما می دانیم که پس از مرتب سازی لیست به طور کامل ، شماره 5 در مکان چهارم باقی می ماند زیرا 3 عدد کمتر از آن و 3 شماره بالاتر از آن است. حال اگر [1،4،3] و [9،6،7] را مرتب کنیم ، یک لیست مرتب داریم! ما دو لیست را با استفاده از همان عملکرد مرتب می کنیم. سرانجام ، آنقدر آن را می شکنیم که به لیست های خالی می رسیم و یک لیست خالی به دلیل خالی بودن ، به شکلی مرتب شده است. در اینجا یک تصویر وجود دارد:

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

تفکر بازگشتی

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

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

وقتی به صورت بازگشتی با شماره ها سر و کار دارید ، شبیه است. معمولاً مربوط به برخی از تعداد و عملکرد اعمال شده برای آن شماره اصلاح شده است. ما عملکرد فاکتوریل را قبلاً انجام دادیم و این محصول یک عدد و فاکتوریل آن شماره منهای یک است. چنین برنامه بازگشتی با صفر معنی ندارد ، زیرا فاکتوریل ها فقط برای اعداد صحیح مثبت تعریف می شوند. غالباً مقدار مورد لبه به عنوان یک هویت تبدیل می شود. هویت برای ضرب 1 است زیرا اگر چیزی را با 1 ضرب کنید ، آن چیزی را پس می گیرید. همچنین هنگام انجام مبالغ لیست ها ، ما مبلغ یک لیست خالی را تعریف می کنیم زیرا 0 و 0 هویت برای علاوه بر این است. در QuickSort ، The Edge Case لیست خالی است و هویت نیز لیست خالی است ، زیرا اگر یک لیست خالی را به یک لیست اضافه کنید ، فقط لیست اصلی را پس می گیرید.

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