8. القاء و بازگشت

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

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

8. 1. تطبیق الگو¶

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

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

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

به جای صفر و مکنده ، می توانیم از نماد آشناتری استفاده کنیم:

از آنجا که علاوه بر این و نماد صفر به ویژگی [الگوی] اختصاص یافته است ، می توان از آنها در تطبیق الگوی استفاده کرد. لاغر به سادگی این عبارات را عادی می کند تا سازندگان صفر و SUCC در معرض دید قرار گیرند.

تطبیق الگوی با هر نوع القایی مانند محصولات و انواع گزینه ها کار می کند:

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

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

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

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

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

می توانید #print sub2 را بنویسید تا ببینید که چگونه این عملکرد برای گیرنده ها تهیه شده است.(Lean به شما خواهد گفت که SUB2 از نظر عملکرد کمکی داخلی ، sub2. _main تعریف شده است ، اما می توانید آن را نیز چاپ کنید.)

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

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

در اینجا مثال دیگری است:

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

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

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

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

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

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

8. 2. کارتهای وحشی و الگوهای همپوشانی

یکی از نمونه های بخش آخر را در نظر بگیرید:

مثال را می توان به طور خلاصه نوشت:

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

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

می توانید بررسی کنید که این تعریف FOO همان هویت های تعریف شده را مانند گذشته برآورده می کند.

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

ما همچنین می توانیم از گزینه نوع α برای شبیه سازی الگوهای ناقص استفاده کنیم. ایده این است که برخی از A را برای الگوهای ارائه شده برگردانید و از هیچ یک برای موارد ناقص استفاده نکنید. مثال زیر هر دو رویکرد را نشان می دهد.

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

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

8. 3. بازگشت و القاء ساختاری

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

تعاریف ساختاری بازگشتی

تعاریف بازگشتی خوب

تعاریف متقابل متقابل

به طور کلی ، کامپایلر معادله ورودی فرم زیر را پردازش می کند:

در اینجا (A: α) دنباله ای از پارامترها است ، (B: β) توالی آرگومان هایی است که در آن تطبیق الگوی صورت می گیرد ، و γ هر نوع است که می تواند به A و B بستگی داشته باشد. هر خط باید دارای همان تعداد الگوهای باشد ، یکی برای هر عنصر β. همانطور که دیدیم ، یک الگوی یا یک متغیر است ، سازنده ای که برای الگوهای دیگر اعمال می شود ، یا عبارتی که به چیزی از آن شکل عادی می شود (جایی که غیر سازنده ها با ویژگی [الگوی] مشخص می شوند). ظواهر سازندگان شکاف سریع ، با استدلال به سازندگان که توسط متغیرهای داده شده نشان داده شده است. در بخش 8. 6 ، خواهیم دید که گاهی اوقات لازم است اصطلاحات صریح را در الگوهای لازم برای بررسی نوع بیان درج کنید ، اگرچه آنها در تطبیق الگوی نقشی ندارند. به همین دلیل اینها "اصطلاحات غیرقابل دسترسی" نامیده می شوند. اما ما نیازی به استفاده از چنین اصطلاحات غیرقابل دسترسی قبل از بخش 8. 6 نخواهیم داشت.

همانطور که در بخش آخر دیدیم ، اصطلاحات t₁ ،. Tₙ می تواند از هر یک از پارامترهای A و همچنین هر یک از متغیرهایی که در الگوهای مربوطه معرفی شده اند ، استفاده کند. آنچه بازگشت و القاء را ممکن می سازد این است که آنها همچنین می توانند تماس های بازگشتی به FOO را درگیر کنند. در این بخش ، ما با بازگشت ساختاری سر و کار خواهیم داشت ، که در آن استدلال های مربوط به FOO در سمت راست از سمت راست اتفاق می افتد: = زیرزمین الگوهای در سمت چپ است. ایده این است که آنها از نظر ساختاری کوچکتر هستند و از این رو در مرحله اولیه در نوع القایی ظاهر می شوند. در اینجا چند نمونه از بازگشت ساختاری از فصل گذشته ، که اکنون با استفاده از کامپایلر معادله تعریف شده است:

اثبات Zero_Add روشن می کند که اثبات با القاء واقعاً نوعی القاء در لاغر است.

مثال بالا نشان می دهد که معادلات تعیین کننده برای افزودن به طور تعریف ، و همین موضوع در مورد MUL نیز صادق است. کامپایلر معادله سعی می کند تا هر زمان ممکن را حفظ کند ، همانطور که در مورد القاء ساختاری ساده وجود دارد. با این حال ، در شرایط دیگر ، کاهش فقط به صورت گزاره ای وجود دارد ، یعنی آنها قضایای معادل هستند که باید صریحاً اعمال شوند. کامپایلر معادله چنین قضایای داخلی را تولید می کند. منظور آنها برای استفاده مستقیم توسط کاربر نیست. در عوض ، تاکتیک های SIMP و بازنویسی برای استفاده از آنها در صورت لزوم پیکربندی شده است. بنابراین هر دو اثبات زیر از کار Zero_add:

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

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

این ممکن است کمی عجیب به نظر برسد ، اما شما باید تعریف را به شرح زیر بخوانید: "M را اصلاح کنید ، و عملکردی را تعریف کنید که چیزی را به صورت بازگشتی اضافه کند ، به شرح زیر. برای افزودن صفر ، m را برگردانید. برای افزودن جانشین N ، ابتدا N را اضافه کنید ، و سپس جانشین را بگیرید. "مکانیسم اضافه کردن پارامترها به متن محلی همان چیزی است که باعث می شود پردازش عبارات مطابق با اصطلاحات ، همانطور که در بخش 8. 8 توضیح داده شده است.

یک نمونه جالب تر از بازگشت ساختاری توسط FIB عملکرد Fibonacci آورده شده است.

در اینجا ، مقدار عملکرد FIB در N + 2 (که به طور تعریف برابر با Succ (Succ N)) از نظر مقادیر در N + 1 (که از نظر تعریف معادل SUCC N) و مقدار در n تعریف شده است. این یک روش بسیار ناکارآمد برای محاسبه عملکرد Fibonacci است ، با این حال ، با یک زمان اجرا که در n نمایی است. در اینجا یک راه بهتر است:

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

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

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

8. 4. بازگشت و القاء خوب است

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

کتابخانه استاندارد Lean دو پیش بینی ، ACC R A و Well_founded R را تعریف می کند ، جایی که R یک رابطه باینری در یک نوع α است ، و A عنصری از نوع α است.

اولین ، ACC ، یک محمول القایی تعریف شده است. با توجه به تعریف آن ، ACC R X معادل ∀ y ، r y x → acc r y است. اگر از r y x فکر می کنید که نوعی رابطه سفارش y ≺ x را نشان می دهد ، پس ACC R X می گوید که X از پایین در دسترس است ، به این معنا که همه پیشینیان خود در دسترس هستند. به طور خاص ، اگر X پیشینای نداشته باشد ، در دسترس است. با توجه به هر نوع α ، ما باید با اختصاص مقادیر به همه پیشینیان خود ، بتوانیم مقداری را به هر عنصر قابل دسترسی α ، به صورت بازگشتی اختصاص دهیم.

این جمله که R به خوبی تأسیس شده است ، مشخص شده WELL_FOUNDED R ، دقیقاً عبارتی است که هر عنصر از نوع در دسترس است. با توجه به ملاحظات فوق ، اگر R یک رابطه خوب در یک نوع α باشد ، باید با توجه به رابطه r ، یک اصل بازگشت به خوبی در α داشته باشیم. و ، در واقع ، ما این کار را انجام می دهیم: کتابخانه استاندارد Well_found. fix را تعریف می کند ، که دقیقاً به همین هدف عمل می کند.

در اینجا شخصیت های طولانی از شخصیت ها وجود دارد ، اما اولین بلوکی که قبلاً دیده ایم: نوع ، α ، رابطه ، R و فرض ، H ، که R به خوبی پایه گذاری شده است. متغیر C نشان دهنده انگیزه تعریف بازگشتی است: برای هر عنصر x: α ، ما می خواهیم یک عنصر c x بسازیم. عملکرد F دستور العمل القایی را برای انجام این کار فراهم می کند: به ما می گوید چگونه می توان یک عنصر C x را ساخت ، با توجه به عناصر C y برای هر سلف y از x.

توجه داشته باشید که Well_founded. fix به همان اندازه یک اصل القایی کار می کند. این گفته است که اگر ≺ به خوبی پایه گذاری شده باشد و شما می خواهید ∀ x ، c x را اثبات کنید ، کافی است که برای یک x دلخواه نشان دهیم ، اگر ما ∀ y ≺ x ، c y داشته باشیم ، پس C x داریم.

در اینجا اساساً تعریف تقسیم بر اعداد طبیعی است که در کتابخانه استاندارد یافت می شود.

تعریف تا حدودی غیرقابل توصیف است. در اینجا بازگشتی روی x است ، و div. f x f: ℕ → ℕ عملکرد "تقسیم توسط y" را برای آن x ثابت باز می گرداند. باید به یاد داشته باشید که استدلال دوم Div. F ، دستور العمل بازگشت ، تابعی است که قرار است تقسیم را با عملکرد y برای همه مقادیر x₁ کوچکتر از x بازگرداند.

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

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

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

مثال زیر مشابه است: هر عدد طبیعی را به یک عبارت باینری تبدیل می کند ، که به عنوان لیستی از 0 و 1 ارائه می شود. ما باید کامپایلر معادله را ارائه دهیم که نشان می دهد تماس بازگشتی در حال کاهش است ، که ما در اینجا با پشیمانی انجام می دهیم. متأسفم مانع از ارزیابی موفقیت آمیز عملکرد Bytecode نمی شود.

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

مکانیسم های Lean برای حدس زدن یک رابطه خوب و سپس اثبات این که کاهش تماس های بازگشتی هنوز در وضعیت بدی است. آنها با گذشت زمان بهبود می یابند. هنگام کار ، آنها روش بسیار راحت تری برای تعریف توابع نسبت به استفاده از Well_founded. fix به صورت دستی ارائه می دهند. وقتی این کار را نمی کنند ، دومی همیشه به عنوان پشتیبان موجود است.

8. 5بازگشت متقابل ¶

Lean همچنین از تعاریف بازگشتی متقابل پشتیبانی می کند. نحو شبیه به انواع القایی متقابل است ، همانطور که در بخش 7. 9 توضیح داده شده است. به عنوان مثال:

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

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

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

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

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

8. 6. تطبیق الگوی وابسته

تمام نمونه های تطبیق الگوی مورد نظر ما در بخش 8. 1 به راحتی با استفاده از Case_on و Rec_on می توانند به راحتی نوشته شوند. با این حال ، این اغلب در مورد خانواده های القایی شاخص مانند وکتور α N موردی نیست ، زیرا تقسیم پرونده محدودیت هایی را در مقادیر شاخص ها تحمیل می کند. بدون کامپایلر معادله ، برای تعریف توابع بسیار ساده مانند MAP ، zip و anzip با استفاده از Recursors به کد دیگ بخار زیادی نیاز داریم. برای درک دشواری ، در نظر بگیرید که برای تعریف دم عملکردی که یک بردار V را می گیرد ، در نظر بگیرید: بردار α (Succ N) و عنصر اول را حذف می کند. اولین فکر ممکن است استفاده از عملکرد Case_on باشد:

اما چه مقدار باید در پرونده صفر برگردیم؟چیزی خنده دار در جریان است: اگر V دارای بردار نوع α (Succ N) باشد ، نمی تواند صفر باشد ، اما مشخص نیست که چگونه این را به مواردی_ون بگوییم.

یک راه حل تعریف یک عملکرد کمکی است:

در مورد صفر ، M به 0 فوری می شود ، و No_Confusion از این واقعیت استفاده می کند که 0 = Succ N نمی تواند رخ دهد. در غیر این صورت ، V از فرم A :: W است ، و ما می توانیم به سادگی W را پس از ریختن آن از یک بردار طول M به یک بردار طول n برگردانیم.

دشواری در تعیین دم ، حفظ روابط بین شاخص ها است. فرضیه E: M = N + 1 در Tail_Aux برای برقراری ارتباط بین N و شاخص مرتبط با فرض جزئی استفاده می شود. علاوه بر این ، مورد صفر = N + 1 غیرقابل دستیابی است ، و روش متعارف برای دور انداختن چنین موردی استفاده از NO_CONFUSION است.

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

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

عملکرد MAP برای تعریف با دست نسبت به عملکرد دم حتی خسته کننده تر است. ما شما را تشویق می کنیم تا با استفاده از rec_on ، cases_on و no_confusion ، آن را امتحان کنید.

8. 7. شرایط غیرقابل دسترسی

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

مثال زیر را می توان در [GOMM06] یافت. ما یک نوع القایی را اعلام می کنیم که خاصیت "بودن در تصویر F" را تعریف می کند. شما می توانید یک عنصر از نوع Image_Of F B را به عنوان شواهدی که B در تصویر F است مشاهده کنید ، به موجب آن از صندوق بین سازنده برای ساخت چنین شواهدی استفاده می شود. سپس می توانیم هر عملکرد F را با "معکوس" تعریف کنیم که هر چیزی را در تصویر F به عنصری که برای آن نقشه برداری شده است ، می گیرد. قوانین تایپ ما را وادار می کند که برای اولین استدلال f A را بنویسیم ، اما این اصطلاح نه متغیر است و نه یک برنامه سازنده ، و هیچ نقشی در تعریف الگوی مطابقت ندارد. برای تعریف عملکرد معکوس در زیر ، ما باید F را غیرقابل دسترسی نشان دهیم.

در مثال بالا ، حاشیه نویسی غیرقابل دسترسی روشن می کند که F یک متغیر تطبیق الگوی نیست.

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

استدلال باید بعد از روده بزرگ ظاهر شود ، زیرا نمی توان در طول تعریف ثابت نگه داشت. هنگام اجرای این تعریف ، کامپایلر معادله با تمایز موردی شروع می شود که آیا اولین استدلال 0 یا از فرم n+1 است. این به دنبال تقسیم موارد تو در تو در دو آرگومان بعدی است ، و در هر صورت کامپایلر معادله قانون را با الگوی اول سازگار نیست.

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

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

استفاده از اصطلاحات غیرقابل دسترسی صریح ، آن را حتی روشن تر می کند.

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

8. 8عبارات مطابقت

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

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