پیاده‌سازی یک Lazy Iterator در زبان Go

در این نوشته درباره پیاده‌سازی یک Lazy Iterator ساده در زبان Go توضیحاتی را ارائه می‌کنم. کد مربوط به این نوشته را در لینک زیر می‌تونید ببینید که یک Lazy Iterator ساده (مشابه زبان‌های Functional) است:

در ادامه یک مسئله ساده را بررسی می‌کنم و بعد این مسئله را با استفاده از iteratorهای lazy حل می‌کنم.

برای مثال فرض کنید آرایه‌ای (دقیق‌تر slice) از اعداد دارم و قصد دارم مراحل زیر را روی هر عدد انجام بدم:

• اعداد فرد را از آرایه انتخاب کنم.
• این اعداد فرد را دو برابر کنم (ضربدر ۲).
• اعداد مرحله قبل که بزرگتر از ۵ هستن را انتخاب کنم.
• حاصل جمع اعداد نهایی را چاپ کنم.

برای این کار خیلی ساده می‌تونم یک حلقه for بنویسم و مراحل مورد نیاز را به ترتیب برای هر عدد داخل آرایه انجام بدم:

اما اگر بخوام این مسئله را به روش زبان‌های Functional حل کنم، می‌تونم یک Iterator داشته باشم که در هر مرحله عدد مورد نیاز را آماده می‌کنه و سپس یک سری تابع Map را روی آن عدد اعمال می‌کنه و در نهایت مقدار نهایی را Reduce می‌کنه. در شکل زیر می‌تونید این مراحل را ببینید:

در این شکل دو تابع Filter هم دارم که در خانواده توابع Map قرار می‌گیرن. اگر بخوام این کار را بصورت Lazy انجام بدم، باید کد را طوری بنویسم که تا وقتی تابع Reduce انتهایی اجرا نشده، توابع Map اعمال شده هیچ خروجی‌ای نداشته باشن. در این مثال تابع Reduce قراره همه ارقام را با هم جمع کنه. توجه کنید که می‌تونم توابع Map و Reduce مختلفی داشته باشم که کارهای متفاوتی روی ورودی خودشون انجام بدن و خروجی متفاوتی را تولید کنن. بعنوان نمونه می‌تونید به لینک ابتدای متن مراجعه کنید و برخی از این توابع را ببینید.

برای شروع پیاده‌سازی Iterator نیاز به یک Data Provider یا Generator دارم که بتونه یکی‌یکی اعداد را از لیست بخونه و بعنوان ورودی به توابع Map و Reduce بفرسته:

یک interface بعنوان Generator تعریف کردم که دو تابع Next و Value داره:

• تابع Next عدد بعدی را آماده می‌کنه و اگر عدد قابل آماده‌سازی بود مقدار true را برمی‌گردونه، اما اگر عدد بعدی وجود نداشت (مثلا در انتهای آرایه) باید مقدار false را برگردونه تا فرایند iteration متوقف بشه.
• تابع Value مقدار آماده شده توسط تابع Next را برمی‌گردونه.

برای استفاده از Generator ابتدا هر بار باید تابع Next اجرا بشه و اگر این تابع مقدار true برگردوند، مقدار آماده شده توسط تابع Value خونده بشه. این روش را در پکیج‌های استاندارد کتابخونه Go هم می‌تونید ببینید (برای مثال پکیج sql).

در ادامه یک struct تعریف می‌کنم تا Generator را implement کنه. در واقع یک struct می‌سازم تا یک slice را به Generator تبدیل کنه:

برای ساختن یک instance از این struct باید تابع NewSlice با یک slice بعنوان ورودی صدا زده بشه. خروجی این تابع یک pointer است. در داخل تابع Next عملیات Shift روی slice انجام میشه (هر بار اولین آیتم از slice حذف میشه) و تا وقتی‌که slice خالی نشده باشه مقدار true برمیگرده. با اجرای تابع Value هم مقدار حذف شده (آماده شده) فعلی از slice برمیگرده. همانطور که مشخصه در این روش پیاده‌سازی، slice ورودی Consume (مصرف) میشه و در نتیجه هر instance از این Generator فقط یک‌بار قابل استفاده است. در صورت تمایل می‌تونید تابع Next را طوری تغییر بدید که slice تغییری نکنه، برای این‌کار باید یک فیلد به struct اضافه کنید که اندیس فعلی روی slice را تعیین کنه و در هر بار صدا زدن Next یکی به مقدارش اضافه بشه.

الان می‌تونم یک struct برای Iterator تعریف کنم که بعنوان ورودی یک instance از implementerهای Generator را می‌گیره:

در این struct برای اینکه بتونم خاصیت Lazy را پیاده‌سازی کنم یک فیلد به نام mappers دارم که توابع مربوط به خانواده Map را به ترتیب ذخیره می‌کنه. به کمک این slice از توابع (Function Pointers) می‌تونم وقتی که تابع Reduce صدا زده شد به ترتیب توابع Map داخل mappers را یکی‌یکی روی هر عدد ورودی اعمال کنم.

قبل از تعریف توابع Map و Reduce یک instance از Iterator برای حل مسئله می‌سازم:

چون قصد دارم توابع Map را پشت‌سرهم بصورت یک زنجیره صدا بزنم، آن‌ها را طوری تعریف می‌کنم تا بعنوان خروجی pointer مربوط به Iterator را برگردونن:

ابتدا دو type alias برای توابع مورد نیاز تعریف می‌کنم تا راحت‌تر بتونم داخل توابع Map و Filter بعنوان ورودی ازشون استفاده کنم. تابع MapFunc یک عدد بعنوان ورودی می‌گیره و بعد از اعمال تغییرات مورد نیاز عدد جدید را برمی‌گردونه (برای مثال برای دو برابر کردن هر عدد). تابع PredicateFunc یک عدد بعنوان ورودی می‌گیره و اگر true برگردونه این عدد به مرحله بعد میره (برای مثال برای جداسازی اعداد فرد). همانطور که می‌بینید صدا زدن توابع Map و Filter در واقع هیچ کاری روی اعداد ورودی انجام نمیدن (Lazy) و فقط تابع ورودی را به لیست mappers اضافه می‌کنن.

حالا باید یک instance از نوع MapFunc و PredicateFunc داشته باشم تا بتونم مسئله را حل کنم:

توابع isOdd و greaterThanFive ساختار PredicateFunc را دارن و تابع double ساختار MapFunc را داره. بنابراین می‌تونم از این توابع به‌عنوان ورودی متدهای Map و Filter استفاده کنم:

در ادامه باید متد Reduce را طوری تعریف کنم که یک state داشته باشه و این state را بعد از خوندن هر عدد آپدیت کنه و در نهایت مقدار نهایی state را برگردونه. تابع Reduce جایی هستش که اعداد از Generator خونده میشن و توابع Map از لیست mappers یکی‌یکی و به‌ترتیب روی هر عدد اعمال میشن و در نهایت یک تابع reducer روی عدد Map شده صدا زده میشه تا state آپدیت بشه:

ورودی state در متد Reduce بعنوان مقدار اولیه در نظر گرفته میشه. حالا باید تابع reducer را با ساختار ReduceFunc تعریف کنم که در واقع عملیات جمع را انجام میده:

درنهایت باید این تابع را بعنوان ورودی به متد Reduce بدم و مقدار خروجی متد Reduce (جواب مسئله) را چاپ کنم (مقدار اولیه حاصل‌جمع را صفر وارد کردم):

توجه کنید که struct و interfaceهای مورد نیاز را فقط یک بار تعریف می‌کنید و هر بار می‌تونید از آن‌ها برای حل مسائل مختلف استفاده کنید. برای مثال:

برای مشاهده مثال‌های بیشتر از توابع Map و Reduce و همچنین نحوه پیاده‌سازی این ماژول بصورت جنریک (با استفاده از تایپ interface{}) می‌تونید به ریپازیتوری goterator در گیت‌هاب مراجعه کنید. در این ماژول توابع Map زیر پیاده‌سازی شدن (نسخه v0.2.0):

• متد Map: برای تبدیل یک مقدار به مقدار دیگر.
• متد Filter: برای فیلتر و حذف برخی مقادیر از iteration.
• متدهای Take و TakeWhile: برای در نظر گرفتن تعدادی از مقادیر.
• متدهای Skip و SkipWhile: برای صرف نظر کردن از چند مقدار اولیه.

همچنین توابع Reducer زیر هم در دسترس هستن:

• متد ForEach: برای اجرای یک تابع روی تمامی مقادیر Map شده.
• متد Collect: برای خروجی گرفتن از مقادیر Map شده بصورت یک slice با حفظ order اولیه.
• متد Reduce: برای آپدیت کردن یک state نهایی بعنوان خروجی با استفاده از تمامی مقادیر Map شده.
• متد Find: برای پیدا کردن اولین مقدار Map شده‌ای که یک خاصیت خاص را داره.
• متدهای Min و Max: برای پیدا کردن مقادیر کمینه و بیشینه در بین مقادیر Map شده.
• متد All: برای تعیین اینکه تمامی مقادیر Map شده یک خاصیت خاص را دارن.
• متد Any: برای تعیین اینکه حداقل یکی از مقادیر Map شده یک خاصیت را داره.
• متد Last: برای پیدا کردن آخرین مقدار Map شده بعنوان خروجی.
• متد Nth: برای پیدا کردن nامین مقدار Map شده بعنوان خروجی.
• متد Count: برای شمردن تعداد مقادیر Map شده بعنوان خروجی.

بعلاوه Generator برای کار با Channel و Slice بعنوان Data Provider پیاده سازی شده است.