مقدمه ای بر انواع بازگشتی

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

مطالب سری

اینم مطالب این سریال:

• بخش 1: مقدمه ای بر انواع بازگشتی و کاتامورفیسم

یک نوع بازگشتی اولیه

بیایید با یک مثال ساده شروع کنیم - چگونه یک هدیه را مدل کنیم.

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

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

می توانید ببینید که سه مورد از موارد "ظروف" هستند که به هدیه دیگری اشاره می کنند. قاب Wrapped مقداری کاغذ و یک هدیه درونی دارد، همانطور که جعبه Boxed و همچنین کیف WithACard نیز وجود دارد. دو مورد دیگر، کتاب و شکلات، به یک هدیه اشاره نمی کنند و می توانند گره ها یا پایانه های "برگی" در نظر گرفته شوند.

وجود ارجاع به یک هدیه درونی در این سه مورد، Gift را یک نوع بازگشتی می کند. توجه داشته باشید که بر خلاف توابع، کلمه کلیدی rec برای تعریف انواع بازگشتی مورد نیاز نیست.

بیایید چند مقدار نمونه ایجاد کنیم:

قبل از شروع کار با این ارزش ها، یک توصیه…

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

من پیشنهاد می کنم که در F#، هر نوع بازگشتی باید از ترکیبی از موارد بازگشتی و غیر بازگشتی تشکیل شود. اگر عناصر غیر بازگشتی مانند Book وجود نداشت، همه مقادیر نوع باید بی نهایت بازگشتی باشند.

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

اگر تنبلی، جهش یا بازتاب را مجاز کنید، می توان چنین انواعی را ایجاد کرد. اما به طور کلی، در یک زبان غیر تنبل مانند F#، ایده خوبی است که از چنین انواعی اجتناب کنید.

کار با انواع بازگشتی

پایان اطلاعیه خدمات عمومی - بیایید کدنویسی کنیم!

ابتدا بگویید که توضیحی در مورد هدیه می خواهیم. منطق این خواهد بود:

• برای دو مورد غیر بازگشتی، رشته ای را که آن مورد را توصیف می کند، برگردانید.
• برای سه مورد بازگشتی، رشته ای را برگردانید که مورد را توصیف می کند، اما شامل توصیف هدیه داخلی نیز می شود. این بدان معنی است که تابع توضیحات به خودش اشاره می کند و بنابراین باید با کلمه کلیدی rec علامت گذاری شود.

در اینجا یک نمونه پیاده سازی آمده است:

به تماس های بازگشتی مانند این در مورد Boxed توجه کنید:

اگر این را با مقادیر مثال خود امتحان کنیم، بیایید ببینیم چه چیزی به دست می آید:

این برای من بسیار خوب به نظر می رسد. مواردی مانند Happyholidays بدون فضای کمی خنده دار به نظر می رسند ، اما به اندازه کافی خوب است که این ایده را نشان دهید.

در مورد ایجاد عملکرد دیگر چیست؟به عنوان مثال ، کل هزینه هدیه چقدر است؟

برای TotalCost ، منطق خواهد بود:

• کتاب ها و شکلات ها قیمت را در داده های خاص ضبط می کنند ، بنابراین از آن استفاده کنید.
• بسته بندی 0. 5 به هزینه اضافه می کند.
• یک جعبه 1. 0 به هزینه اضافه می کند.
• یک کارت 2. 0 به هزینه اضافه می کند.

و در اینجا هزینه های این دو مثال وجود دارد:

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

و نتایج:

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

پارامتر کردن همه چیزها

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

چگونه می توانیم منطق ناوبری را از منطق برنامه جدا کنیم؟

پاسخ: همه چیزها را پارامتر کنید!

مثل همیشه ، ما می توانیم با عبور از توابع ، منطق برنامه را پارامتر کنیم. در این حالت ، ما برای هر مورد به پنج عملکرد نیاز خواهیم داشت.

در اینجا نسخه جدید و پارامتر شده است - من توضیح خواهم داد که چرا من آن را به زودی Catagift خوانده ام.

می توانید ببینید که این عملکرد با استفاده از یک فرآیند کاملاً مکانیکی ایجاد شده است:

• هر پارامتر عملکرد (FBook ، fchocolate و غیره) با یک مورد مطابقت دارد.
• برای دو مورد غیر Recursive ، پارامتر عملکرد تمام داده های مرتبط با آن مورد منتقل می شود.
• برای سه مورد بازگشتی ، دو مرحله وجود دارد:
  • اول ، عملکرد Catagift به صورت بازگشتی در Iergift نامیده می شود تا یک Iergiftresult دریافت کند
  • سپس به کنترل کننده مناسب تمام داده های مرتبط با آن مورد منتقل می شود ، اما با تعویض درونی داخلی.

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

  • Iergiftresult اکنون کل هزینه هدیه داخلی است ، بنابراین من آن را به Iercost تغییر نام داده ام.
  • عملکرد TotalCostusingCata به خودی خود بازگشتی نیست ، زیرا از عملکرد Catagift استفاده می کند ، و بنابراین دیگر نیازی به کلمه کلیدی Rec ندارد.

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

  ما می توانیم عملکرد توضیحات را با استفاده از Catagift به همان روش بازنویسی کنیم و تغییر درونی را به Iertext تغییر دهیم.

  و نتایج مانند گذشته است:

  معرفی کاتامورفیسم

  عملکرد Catagift که در بالا نوشتیم ، از اجزای یونانی "پایین + شکل" "Catamorphism" نامیده می شود. در استفاده عادی ، یک کاتامورفیسم تابعی است که بر اساس ساختار آن ، یک نوع بازگشتی را به یک مقدار جدید فرو می برد. در حقیقت ، شما می توانید به عنوان نوعی "الگوی بازدید کننده" به یک کاتامورفیسم فکر کنید.

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

  That is, if we want to create a function with signature Gift > string or Gift >int ، ما می توانیم با مشخص کردن عملکردی برای هر مورد در ساختار هدیه ، از یک کاتامورفیسم استفاده کنیم.

  ما در بالا دیدیم که چگونه می توانیم با استفاده از Catamorphism ، TotalCost را به عنوان TotalCostusingCata بازنویسی کنیم و بعداً نمونه های دیگری را نیز مشاهده خواهیم کرد.

  catamorphisms و برابر

  کاتامورفیسم ها اغلب "برابر" خوانده می شوند ، اما بیش از یک نوع برابر وجود دارد ، بنابراین من تمایل به استفاده از "catamorphism" برای مراجعه به مفهوم و "برابر" برای مراجعه به یک نوع خاص از پیاده سازی خواهم داشت.

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

  مرتب کردن

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

  ابتدا ، Catagift fbook fchocolate fwapped fbox fcard سه بار ، یک بار برای هر مورد بازگشتی ، سه بار محصول می کند. بیایید نام آن را مانند recurse اختصاص دهیم:

  The recurse function has the simple signature Gift >"الف - یعنی هدیه ای را به نوع بازگشت مورد نیاز ما تبدیل می کند ، بنابراین می توانیم از آن برای کار با مقادیر مختلف درونی استفاده کنیم.

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

  به طور کلی من از سایه زدن خودداری می کنم ، اما این یک مورد است که در واقع یک عمل خوب است ، زیرا این نوع اشکال مخصوصاً نامطبوع را از بین می برد.

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

  یک چیز دیگر. من می خواهم به صراحت نوع بازگشت را حاشیه نویسی کنم و آن را "r" بنامم. بعداً در این سری ما با انواع دیگری مانند "A و" B سر و کار خواهیم داشت ، بنابراین سازگار بودن مفید خواهد بود و همیشه یک نام استاندارد برای نوع بازگشت داریم.

  نسخه نهایی اینجاست:

  این بسیار ساده تر از اجرای اصلی است ، و همچنین تقارن بین یک سازنده مورد مانند بسته بندی شده (هدیه ، سبک) و کنترل کننده مربوطه fwrapped (هدیه Recurse ، سبک) را نشان می دهد. که ما را به خوبی به ...

  رابطه بین سازندگان مورد و دستگیره ها

  در اینجا امضای عملکرد Catagift است. می بینید که هر عملکرد کنترل کننده مورد (fbook ، fbox و غیره) دارای همان الگوی است: ورودی که شامل تمام داده های مربوط به آن مورد و یک نوع خروجی مشترک است.

  راه دیگر برای فکر کردن در مورد این مسئله این است که: در هر کجا که یک نوع هدیه در سازنده وجود دارد ، آن را با یک r جایگزین کرده است.

  • سازنده Book. Book یک کتاب می گیرد و یک هدیه را برمی گرداند. کنترل کننده FBook یک کتاب می گیرد و یک R را برمی گرداند.
  • سازنده Gift. wroped یک هدیه * بسته بندی می کند * بسته بندی شده و هدیه ای را برمی گرداند. کنترل کننده fwrapped یک بسته بندی 'r * papaperstyle را به عنوان ورودی می گیرد و یک r را برمی گرداند.

  در اینجا رابطه بیان شده از طریق امضاهای نوع است:

  و غیره برای بقیه.

  فواید کاتامورفیسم

  نظریه های زیادی در پشت کاتامورفیسم وجود دارد ، اما در عمل چه مزایایی دارد؟

  چرا زحمت ایجاد یک عملکرد خاص مانند Catagift را دارید؟چرا فقط توابع اصلی را تنها نمی گذاریم؟

  دلایل زیادی وجود دارد ، از جمله:

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

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

  در بخش های بعدی ، ما به سه نکته آخر با جزئیات بیشتر نگاه خواهیم کرد.

  با استفاده از پارامترهای عملکرد برای پنهان کردن ساختار داخلی

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

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

  در اینجا یک مثال است. بیایید بگوییم که من یک طرح قبلی برای Gift داشتم که قاب WithACard را نداشت. من آن را نسخه 1 می نامم:

  و بگویید که ما یک تابع کاتامورفیسم برای آن ساختار ساخته و منتشر کردیم:

  توجه داشته باشید که این فقط چهار پارامتر تابع دارد.

  حال فرض کنید که نسخه 2 Gift همراه باشد که کیس WithACard را اضافه می کند:

  و اکنون پنج مورد وجود دارد.

  اغلب، وقتی یک پرونده جدید اضافه می کنیم، می خواهیم همه مشتریان را بشکنیم و آنها را مجبور کنیم که با پرونده جدید برخورد کنند.

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

  این تابع هنوز فقط چهار پارامتر تابع دارد - هیچ رفتار خاصی برای مورد WithACard وجود ندارد.

  تعدادی روش جایگزین برای سازگاری وجود دارد، مانند برگرداندن یک مقدار پیش فرض. نکته مهم این است که مراجعه کنندگان از تغییر آگاه نیستند.

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

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

  برای مثال، می توانیم یک الگوی فعال برای چهار مورد اول ایجاد کنیم و مورد WithACard را نادیده بگیریم.

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

  توابع رسیدگی به پرونده در مقابل تطبیق الگو

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

  در اینجا مثالی وجود دارد که در آن همه موارد "کانتینر" نادیده گرفته می شوند و فقط موارد "محتوا" بررسی می شوند.

  و در اینجا در حال استفاده است، با دو مورد باقیمانده که با استفاده از لوله کشی به صورت "داخلی" مدیریت می شوند:

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

  استفاده از کاتامورفیسم برای نقشه برداری

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

  اما یک «مقدار واحد» می تواند بیش از یک ساختار اولیه باشد - می تواند یک ساختار پیچیده نیز باشد، مانند یک ساختار بازگشتی دیگر.

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

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

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

  ما به راحتی می توانیم از یک هدیه به یک هدیه minuschocolate نقشه برداری کنیم ، زیرا موارد تقریباً موازی هستند.

  • یک کتاب از طریق دست نخورده منتقل می شود.
  • شکلات خورده می شود و با عذرخواهی جایگزین می شود.
  • پرونده بسته بندی شده از طریق دست نخورده منتقل می شود.
  • جعبه و موارد باکارد نادیده گرفته می شود.

  کپی کردن عمیق

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

  برای دیدن منظور من ، اجازه دهید تابعی به نام DeepCopy را تعریف کنیم که مقدار اصلی را کلون می کند. هر دستیار مورد فقط سازنده مورد مربوطه است:

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

  شما می توانید آزمایش کنید که این خودتان کار می کند:

  بنابراین این منجر به روش دیگری برای تفکر در مورد یک کاتامورفیسم می شود:

  • یک کاتامورفیسم تابعی برای یک نوع بازگشتی است به گونه ای که وقتی در سازه های موردی از نوع عبور می کنید ، یک عملکرد "کلون" دریافت می کنید.

  نقشه برداری و تغییر در یک پاس

  یک نوع جزئی در DeepCopy به ما این امکان را می دهد تا از طریق یک شیء دوباره بچرخیم و بیت های آن را همانطور که انجام می دهیم تغییر دهیم.

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

  و در اینجا در حال استفاده است:

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

  قوانینی برای ایجاد کاتامورفیسم

  ما در بالا دیدیم که ایجاد یک کاتامورفیسم یک فرایند مکانیکی است:

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

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

    خلاصه

    ما در این پست دیده ایم که چگونه می توان یک نوع بازگشتی را تعریف کرد و به کاتامورفیسم معرفی شد.

    در پست بعدی ما از این قوانین برای ایجاد کاتامورفیسم برای برخی از حوزه های دیگر استفاده خواهیم کرد.