عملیات لیست

دستورالعمل‌ها

عملیات پایه‌ای لیست را پیاده‌سازی کنید.

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

تعداد و نام دقیق عملیاتی که باید پیاده‌سازی شوند بسته به track است تا با نام‌های موجود تداخل نکنند، اما عملیات کلی که پیاده‌سازی می‌کنید عبارت‌اند از:

• append (با گرفتن دو لیست، همه‌ی عناصر لیست دوم را به انتهای لیست اول اضافه می‌کند)؛
• concatenate (با گرفتن چندین لیست، همه‌ی عناصر همه‌ی لیست‌ها را در یک لیست مسطح ترکیب می‌کند)؛
• filter (با گرفتن یک «محمول» و یک لیست، لیست همه‌ی عناصری را برمی‌گرداند که predicate(item) برایشان «درست» است)؛
• length (با گرفتن یک لیست، تعداد کل عناصر آن را برمی‌گرداند)؛
• map (با گرفتن یک تابع و یک لیست، لیست نتایج اعمال function(item) روی همه‌ی عناصر را برمی‌گرداند)؛
• foldl (با گرفتن یک تابع، یک لیست و «انباشتگر» اولیه، هر عنصر را از سمت چپ در انباشتگر تا می‌کند (کاهش می‌دهد))؛
• foldr (با گرفتن یک تابع، یک لیست و «انباشتگر» اولیه، هر عنصر را از سمت راست در انباشتگر تا می‌کند (کاهش می‌دهد))؛
• reverse (با گرفتن یک لیست، لیستی برمی‌گرداند که همه‌ی عناصر اصلی را دارد، اما با ترتیب معکوس).

توجه کنید که ترتیبی که آرگومان‌ها به توابع تا (foldl، foldr) داده می‌شوند اهمیت دارد.

پیاده‌سازی

برای این تمرین باید از چندریختی پارامتری Odin (که معمولاً به آن «ژنریک» می‌گویند) استفاده کنید. اگر تا حالا این قابلیت را ندیده‌اید، اینجا یک مرور سریع داریم تا کارتان راه بیفتد.

چندریختی پارامتری یکی از قابلیت‌های زبان‌های برنامه‌نویسی است که به برنامه‌نویسان اجازه می‌دهد درباره‌ی نوع‌هایی که در کدشان استفاده می‌کنند کم‌دقت‌تر (عمومی‌تر، که اسمش هم از همین‌جا می‌آید) باشند و در عین حال «ایمنی نوع» را حفظ کنند. واضح است که این کار فقط در زبان‌های به‌شدت نوع‌دار مثل Odin معنا دارد.

بیایید با یک مثال شروع کنیم. فرض کنید می‌خواهید همه‌ی عناصر یک آرایه را به‌اندازه‌ی یک مقدار ثابت افزایش دهید؛ مسئله‌ی ساده‌ای است.

incr_array_int :: proc(a: []int, by: int) -> []int {

    new_array := make([]int, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

حالا اگر همین قابلیت را برای اعداد اعشاری هم لازم داشته باشید چه؟

incr_array_f64 :: proc(a: []f64, by: f64) -> []f64 {

    new_array := make([]f64, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

و بعد برای اعداد صحیح بدون علامت، اعشارهای ۳۲ بیتی و به همین ترتیب؟

چیزی نمی‌گذرد که سر از انبوهی از رویه‌ها درمی‌آورید که دقیقاً کار یکسانی انجام می‌دهند، اما روی نوعی متفاوت. اگر روزی لازم شود منطق کار را به‌روزرسانی کنید، باید مطمئن شوید که این کار را برای همه‌ی گونه‌ها انجام می‌دهید و همین می‌تواند به کار نگهداری زیادی تبدیل شود. آزار دیگر این است که باید به هر رویه نام متفاوتی بدهید، چون Odin از سربارگذاری ضمنی رویه پشتیبانی نمی‌کند (هنوز می‌توانید از سربارگذاری صریح استفاده کنید، اما آن داستانِ تمرین دیگری است).

Odin که زبانی کاربردی است، با چندریختی پارامتری راه‌حلی ارائه می‌دهد. تا زمانی که کامپایلر بتواند نوع یک پارامتر را در زمان کامپایل تشخیص دهد، می‌توانید به آن یک نام ژنریک بدهید، مثل T. بیایید رویه‌ی بالا را بازنویسی کنیم:

incr_array :: proc(a: []$T, by: T) -> []T {

    new_array := make([]T, len(a))
    for i := 0; i < len(a); i+= 1 {
        new_array[i] = a[i] + by
    }
    return new_array
}

دقت کنید که همه‌ی حاشیه‌نویسی‌های نوع (int یا f64) را با T جایگزین کرده‌ایم و اینکه اولین ظهور T با علامت دلار ($T) همراه است. نوع $T به کامپایلر Odin می‌گوید که نام T یک نام ژنریک برای نوع است که هنگام کامپایل با نام واقعی جایگزین می‌شود. و چون کامپایلر حالا نوع ژنریک T را می‌شناسد، ظهورهای بعدی همان نوع فقط باید با نام نوع انتخاب‌شده (T) علامت‌گذاری شوند.

حالا می‌توانید کدی مثل این بنویسید:

a_int := incr_array([]int{1, 2, 3}, 10)
a_f64 := incr_array([]f64{1.0, 2.0, 3.0}, 10.0)

در دستور اول، کامپایلر Odin نوع پارامتر اول ([]int) را با نوع پارامتر ژنریک ([]$T) تطبیق می‌دهد، نتیجه می‌گیرد که T = int است و بعد نسخه‌ای را کامپایل می‌کند که در آن همه‌ی نمونه‌های بعدی T با int جایگزین شده‌اند (معادل نسخه‌ی تخصص‌یافته‌ی incr_array_int() در بالا). اگر علامت دلار را در تعریف پارامتر اول حذف می‌کردید، کامپایلر در پکیج فعلی و فهرست importها به دنبال نوعی به نام T می‌گشت و به احتمال زیاد خطای کامپایلی Error: Undeclared name: T را برمی‌گرداند.

دستور دوم دقیقاً مثل اولی کار می‌کند، فقط این بار کامپایلر T را f64 تشخیص می‌دهد.

مرسوم است که به انواع ژنریک نام‌های یک‌حرفی بدهند (T و E زیاد استفاده می‌شوند).

حالا باید به‌قدر کافی درباره‌ی چندریختی پارامتری، یا همان انواع ژنریک، بدانید تا سراغ تمرین List Operations بروید.