Операції з масивом

Вказівки

Реалізуйте базові операції з масивами.

У функціональних мовах такі операції з масивами, як length, map і reduce, трапляються дуже часто. Реалізуйте низку базових операцій з масивами, не використовуючи наявні функції.

Точна кількість і назви операцій, які потрібно реалізувати, залежать від конкретного треку, щоб уникнути конфліктів з наявними назвами, але загалом потрібно реалізувати такі операції:

• 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
}

А потім для беззнакових цілих чисел, 32-бітних чисел з плаваючою комою тощо?

Невдовзі ми отримуємо безліч процедур, які виконують одну й ту саму роботу, але з різними типами. Якщо колись потрібно буде оновити логіку, доведеться подбати, щоб це було зроблено для всіх варіантів, а це може обернутися великою роботою з підтримки. Ще одна неприємність: кожній процедурі доводиться давати іншу назву, бо 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() вище). Якби ми опустили знак долара у визначенні першого параметра, компілятор шукав би в поточному пакеті та списку імпортів тип із назвою T і, найімовірніше, повернув би помилку компіляції Error: Undeclared name: T.

Друга інструкція працює точно так само, як перша, лише компілятор визначає T як f64.

Узагальненим типам зазвичай дають однолітерні назви (часто використовують T та E).

Тепер ми знаємо достатньо про параметричний поліморфізм, він же узагальнені типи, щоб узятися за вправу «Операції зі списками».