از مارس 2020، School of Haskell به حالت فقط خواندنی تغییر یافته است.
بخش ها
در آموزش قبلی طراحی یک ماشین حساب را ترسیم کردم و حلقه ورودی/خروجی سطح بالا را پیاده سازی کردم. این یک الگوی معمولی در Haskell است: سطح بالا در IO monad پیاده‌سازی می‌شود (بالاخره، امضای main IO () است) اما وقتی به سطوح پایین‌تر پایین می‌روید، وارد قلمروی بدون عوارض می‌شوید. توابع خالصاولین چنین تابعی توکنیزه کردن با امضای زیر است:
قبل از شروع اجرای آن، باید نوع داده Token را تعریف کنیم و در مورد String s اطلاعات بیشتری کسب کنیم.
انواع داده هاسکل
یک تفاوت عمده بین داده ها در زبان های امری و داده ها در Haskell وجود دارد. داده های Haskell تغییر ناپذیر است. هنگامی که یک آیتم داده را ساختید، برای همیشه یکسان می ماند.
خب، به دلیل یکی دیگر از ویژگی های هاسکل: تنبلی، کاملاً درست نیست. فراخوانی سازنده یک نوع داده با ارزیابی آن یکسان نیست. تنها زمانی که در واقع به داخل یک آیتم داده نگاه می‌کنید، سازنده ارزیابی می‌شود، و تنها بخشی که شما به آن نگاه می‌کنید.
اما برای همه مقاصد، وضعیت یک آیتم داده پس از ساخت آن ثابت می ماند. علاوه بر این، هر آیتم داده ای نحوه ساخت خود را به خاطر می آورد. به یاد می آورد که از کدام سازنده استفاده شده و چه مقادیری به آن منتقل شده است.
اما چگونه می توان بدون داده های قابل تغییر برنامه نوشت؟در واقع، آن دسته از ما که مجبور بودیم با برنامه نویسی همزمان در زبان های ضروری سر و کار داشته باشیم، مجبور بودیم (اغلب راه سخت) را یاد بگیریم تا در صورت امکان از تغییرپذیری اجتناب کنیم. هرچه فرصت‌های کمتری برای کسانی که به سختی می‌توانند بازی‌های داده سطح پایین را بازتولید و اشکال‌زدایی کنند، کد شما قابل اعتمادتر است. این یک دلیل دیگر برای یادگیری برنامه نویسی در Haskell است حتی اگر شغل شما مستلزم استفاده از زبان های ضروری باشد: شما یاد خواهید گرفت که چگونه مسائل را بدون متغیرهای قابل تغییر حل کنید.
در Haskell شما اغلب خواهید دید که جهش با ساخت و ساز جایگزین شده است. به جای اصلاح یک عنصر از ساختار داده، یک کپی از آن را با تغییر مناسب در جای خود می سازید. اگر از ساختارهای داده اشتباه استفاده کنید، این ترفند می تواند بسیار گران باشد. ما از چنین ساختارهای داده ای به نفع به اصطلاح ساختارهای داده پایدار، که در صورت اصلاح نیازی به کپی برداری زیادی ندارند، فاصله خواهیم گرفت. به عنوان مثال، نیروی کار ساختارهای داده هاسکل لیست است، نه آرایه بردار. بعداً در این مورد بیشتر صحبت خواهیم کرد.
انواع داده های شمارش شده
ساده‌ترین انواع داده‌ها فقط تمام مقادیر ممکن را برمی‌شمارند. برای مثال، Bool شمارشی از True و False است (همانطور که در Prelude، کتابخانه استاندارد Haskell تعریف شده است):
تعریف ساختار داده با کلمه کلیدی داده معرفی می شود. Bool نام نوعی است که ما تعریف می کنیم. سمت راست علامت مساوی سازنده هایی را که با میله های عمودی از هم جدا شده اند فهرست می کند. هنگامی که یک مقدار Bool جدید ایجاد می کنید، از یکی از این دو سازنده استفاده می کنید. نام سازنده باید با یک حرف بزرگ شروع شود و باید در هر فایل منحصر به فرد باشد (دو ساختار داده نمی توانند یک نام سازنده را به اشتراک بگذارند).
وقتی می‌خواهید یک مقدار Bool را بررسی کنید، آن را با یکی از سازنده‌ها تطبیق می‌دهید (به یاد داشته باشید، یک مقدار به یاد می‌آورد که چگونه ساخته شده است). چندین روش برای تطبیق مقادیر با سازنده ها در Haskell وجود دارد. بیایید با ساده ترین مورد شروع کنیم: تعریف یک تابع با استفاده از چندین معادله. به جای تعریف یک تابع با یک معادله، به این صورت:
می توانید آن را به دو معادله مربوط به دو الگوی سازنده، True و False تقسیم کنید:
الگوها به ترتیب مطابقت دارند، بنابراین وقتی boolToInt با False فراخوانی می شود، زمان اجرا ابتدا سعی می کند آن را با True مطابقت دهد و شکست می خورد، بنابراین به الگوی دوم False می رود و موفق می شود.(همه معادلات برای یک تابع باید متوالی باشند.)
(توجه: برای صرفه جویی در پرانتز، من شروع به استفاده از عملگر تابع تابع $ می کنم که در آموزش اول معرفی کردم. مدت زیادی از آن گذشته است، بنابراین در اینجا یک جمع بندی سریع وجود دارد: $ یک فراخوانی تابع را از آرگومانش جدا می کند. بسیار مفید است. وقتی آرگومان فراخوانی تابع دیگری باشد، زیرا فراخوانی های تابع به سمت چپ متصل می شوند. در مثال ما، بدون $ یا پرانتز، فراخوانی های تابع باند: (print boolToInt) False، و کامپایل نمی شود. عملگر $ اولویت بسیار کمی دارد. بنابراین، چیزی که در سمت راست قرار دارد، قبل از فراخوانی تابع سمت چپ، ارزیابی می‌شود و به سمت راست متصل می‌شود.)
در اینجا یک شمارش مفید است که ما در پروژه خود استفاده خواهیم کرد:
مثال 1. تابعی بنویسید که یک عملگر را بگیرد و یکی از کاراکترهای '+'، '-'، '*' یا '/' را برگرداند.
رمز
توکنایزر ما باید اپراتورها، شناسه ها و اعداد را بشناسد. ما می توانیم چهار عملگر را برشماریم، اما نمی توانیم همه شناسه ها یا اعداد ممکن را برشماریم. برای آن توکن‌ها باید اطلاعات بیشتری را ذخیره کنیم: به ترتیب یک رشته و یک Int. در اینجا تعریف Token آمده است:
هر سه سازنده اکنون آرگومان ها را می گیرند. سازنده TokOp مقداری از نوع Operator را می گیرد، TokIdent یک رشته و TokNum یک Int می گیرد. به عنوان مثال، می توانید با استفاده از ( TokIdent "x") و غیره یک Token ایجاد کنید.
وقتی در مورد کلاس های نوع صحبت می کنیم، بند مشتق را با جزئیات بیشتری توضیح خواهم داد. در حال حاضر کافی است بدانیم که مشتق کردن Show به این معنی است که راهی برای تبدیل هر Token به رشته وجود دارد (چه با فراخوانی show یا با چاپ کردن آن)، و استخراج Eq به این معنی است که می‌توانیم Token s را برای (in-) مقایسه کنیم. برابریکامپایلر به اندازه کافی باهوش است که این قابلیت را به تنهایی پیاده سازی کند (اگر نتواند، با خطا مواجه می شود).
تطبیق الگو در این سازنده‌ها جالب‌تر است: ما نه تنها نام سازنده را مطابقت می‌دهیم، بلکه مقداری را که در ابتدا با آن نامیده می‌شد، مطابقت می‌دهیم. در اینجا تعریفی از تابع showContent ارائه شده است که از این نوع تطبیق الگو استفاده می کند:
توجه داشته باشید که الگوهای سازنده غیر پیش پا افتاده نیاز به پرانتز دارند. در این الگوها، آرگومان سازنده با یک متغیر (با حروف کوچک) جایگزین می‌شود که باید به مقدار ذخیره شده در Token متصل شود. به عنوان مثال، در الگوی (TokIdent str)، str به رشته ای که در ساخت توکن منطبق استفاده شده است، متصل می شود. اگر توکن با استفاده از TokIdent "x" ساخته شده باشد، str به "x" محدود می شود.(برای متغیرهای تغییرناپذیر ترجیح می دهیم از کلمه "bind" به جای "تخصیص" استفاده کنیم.)
به طور کلی، سازنده‌ها ممکن است آرگومان‌های زیادی از انواع مختلف بگیرند و همه آنها را می‌توان با الگوها مطابقت داد.
مثال 2. یک نوع داده Point را با یک سازنده Pt تعریف کنید که دو دابل s مربوط به مختصات x و y یک نقطه را می گیرد. تابع inc بنویسید که یک Point بگیرد و یک Point جدید که مختصات آن یک بیشتر از مختصات اصلی باشد را برمی گرداند. از تطبیق الگو استفاده کنید.
به هر حال، ما تطبیق الگو را قبلاً روی جفت ها دیده ایم. سازنده یک جفت (,) است.
مثال 3. تمرین قبلی را با استفاده از جفت به جای نقطه s حل کنید.
لیست ها و بازگشت
در Haskell یک رشته لیستی از کاراکترها است. مسلماً، ذخیره و پردازش فهرست نسبت به پردازش آرایه‌های کاراکترها در زبان‌های امری کارآمدی مکان/زمان کمتری دارد. با این حال، مگر اینکه برنامه شما رشته ای فشرده باشد، راحتی دستکاری لیست بر این کاستی ها غلبه می کند. و جایگزین کردن String با ByteString مبتنی بر آرایه کارآمدتر در برنامه‌های کاربردی رشته‌ای بسیار آسان است.
از آنجایی که رشته ها را دستکاری می کنیم -- و رشته ها لیستی از کاراکترها هستند -- ابتدا باید لیست ها را یاد بگیریم.
ابتدا باید از خود بپرسیم: فهرست چیست؟اگر به این فکر می کنید که «تک پیوند یا دو پیوند؟»، در مورد پیاده سازی صحبت می کنید، نه ماهیت یک لیست. پس ماهیت یک لیست چیست؟مانند هر نوع داده انتزاعی، لیست با عملیاتی که می توانید روی آن انجام دهید تعریف می شود. ضروری ترین عملیات ایجاد یک لیست است.
فرد باید بتواند با اضافه کردن یک عنصر به لیست موجود، یک لیست جدید ایجاد کند. این عملیات اغلب "معایب" نامیده می شود، کلمه ای که از اصطلاحات تخصصی Lisp گرفته شده است. توجه داشته باشید که این تعریف خود ارجاعی است -- شما یک لیست از یک لیست ایجاد می کنید. برای شروع از جایی، باید بتوانید یک لیست از هیچ ایجاد کنید - یک لیست خالی. در اینجا تعریفی از لیستی از اعداد صحیح است که فقط بر اساس این توضیحات است:
این واقعیت که این تعریف بازگشتی است نباید حداقل ما را آزار دهد. نکته مهم این است که به ما امکان می دهد لیست های دلخواه ایجاد کنیم:
از این تعریف می توان در تطبیق الگو نیز استفاده کرد. به عنوان مثال، در اینجا تابعی وجود دارد که بررسی می‌کند آیا یک لیست تک‌تنه است:
در این مثال، من از الگوی wildcard _ . اجازه دهید به شما یادآوری کنم که الگوی او با هر چیزی مطابقت دارد (بدون ارزیابی آن). به عنوان مثال، در بند اول singleton من عدد صحیح ذخیره شده در لیست را کنار می گذارم. در بند دوم، کل لیست را نادیده می‌گیرم، زیرا می‌دانم که بند اول، که لیست‌های یک عنصری را می‌گیرد، ابتدا امتحان می‌شود.
مهمتر از همه، از آنجا که لیست به صورت بازگشتی تعریف می شود، پیاده سازی الگوریتم های بازگشتی برای آن آسان است. به عنوان مثال، برای محاسبه مجموع تمام عناصر لیست کافی است بگوییم که مجموع آن برابر با عنصر اول به اضافه مجموع بقیه است. و البته مجموع یک لیست خالی صفر است. پس بزن که بریم:
اما شما نمی خواهید برای هر نوع عنصر ممکن یک نوع لیست جدید تعریف کنید. خوشبختانه، چندشکلی استاتیک در Haskell به طرز شرم آور آسان است. بدون نیاز به زشتی قالب پرمخاطب. شما فقط انواع را با تعیین یک آرگومان نوع پارامتر می کنید. شما می توانید با جایگزین کردن Int با پارامتر نوع a یک لیست عمومی تعریف کنید (پارامترهای نوع باید با حروف کوچک شروع شوند و معمولاً از ابتدای الفبا گرفته می شوند):
لیست A در این تعریف یک نوع عمومی است. لیست به خودی خود یک سازنده نوع نامیده می شود ، زیرا می توانید با ارائه یک آرگومان نوع ، مانند لیست int یا لیست (لیست کاراکتر) از آن برای ساخت یک نوع جدید استفاده کنید (لیستی از لیست شخصیت ها). برای جلوگیری از سردرگمی ، سازندگان در سمت راست یک تعریف داده اغلب سازندگان داده نامیده می شوند ، بر خلاف سازنده نوع در سمت چپ.
در واقعیت ، شما نیازی به تعریف نوع لیست ندارید - تعریف آن به زبان ساخته شده است ، و نحو آن بسیار راحت است. نام نوع یک لیست شامل یک جفت براکت مربع با نوع Varaible بین آنها است. منفی توسط یک روده بزرگ infix جایگزین می شود ،:و لیست خالی یک جفت خالی از براکت مربع است ، []. شما ممکن است به نوع لیست داخلی فکر کنید که توسط این معادله تعریف شده است:
بگذارید مثال قبلی را با این نماد جدید بازنویسی کنم:
یک ویژگی مناسب دیگر وجود دارد: نحو ویژه برای لیست های لیست. به جای نوشتن یک سری سازنده ، 2: 8: 64: [] ، می توانید بنویسید [2 ، 8 ، 64].
تطبیق الگوی ممکن است توخالی شود. به عنوان مثال ، شما ممکن است با سه عنصر اول یک لیست با الگوی (A: (B: (C: REST))) یا ، با استفاده از همکاران صحیح: ، به سادگی (A: B: C: استراحت) مطابقت داشته باشید. واد
سرانجام ، این تعریف رشته است:
رشته با مقداری قند نحوی خاص خود همراه است: هنگام تعریف لفظات رشته ای ، می توانید به جای لفظ تر "سلام" بنویسید ['h' ، 'e' ، 'l' ، 'l' ، 'o'].
در اینجا ، کلمه کلیدی نوع مترادف نوع را معرفی می کند (مانند Typedef در C). شما همیشه می توانید به عقب برگردید و یک رشته را به عنوان لیستی از کاراکتر رفتار کنید - به ویژه ، ممکن است آن را مانند یک لیست مطابقت دهید. ما در اجرای Tokenize بسیاری از این موارد را انجام خواهیم داد. مترادف نوع ، خوانایی کد را افزایش می دهد و منجر به پیام های خطای بهتر می شود ، اما انواع جدیدی ایجاد نمی کنند.
در آموزش بعدی ما به کار خود روی Tokenizer ادامه خواهیم داد و در مورد نگهبانان می آموزیم و به انجام کاری می پردازیم.
تمرینات
سابق 4. هنجاری را اجرا کنید که لیستی از Double S را به خود اختصاص داده و ریشه مربع (SQRT) از مجموع مربع های عناصر آن را برمی گرداند.
سابق 5. اجرای عملکردی را که از هر عنصر دیگری از یک لیست پرش می کند ، پیاده سازی کنید.
سابق 6. تابعی را اجرا کنید که یک جفت لیست را به خود اختصاص داده و لیستی از جفت ها را برمی گرداند. به عنوان مثال ([1 ، 2 ، 3 ، 4] ، [1 ، 4 ، 9]) باید [(1 ، 1) ، (2 ، 4) ، (3 ، 9)] تولید کند. توجه کنید که در صورت لزوم طولانی تر از دو لیست کوتاه می شود. از الگوهای تو در تو استفاده کنید.
اتفاقاً ، یک زیپ عملکرد دو زایی در مقدمه وجود دارد که همین کار را انجام می دهد:
