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

Вказівки

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

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

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

• append (отримавши два масиви, додати всі елементи другого масиву в кінець першого);
• concatenate (отримавши низку масивів, поєднати всі елементи з усіх масивів в один плаский масив);
• filter (отримавши предикат і масив, повернути масив усіх елементів, для яких predicate(item) є правдою);
• length (отримавши масив, повернути загальну кількість елементів у ньому);
• map (отримавши функцію і масив, повернути масив результатів застосування function(item) до всіх елементів);
• foldl (отримавши функцію, масив і початковий акумулятор, згорнути (звести) кожен елемент у акумулятор зліва);
• foldr (отримавши функцію, масив і початковий акумулятор, згорнути (звести) кожен елемент у акумулятор справа);
• reverse (отримавши масив, повернути масив з усіма початковими елементами, але у зворотному порядку).

Зауважте, порядок, у якому аргументи передаються до функцій згортання (foldl, foldr), має значення.

Хвилинку, це неможливо!

Реалізувати ці операції зі списками, не використавши жодної вбудованої функції, у Roc практично неможливо, бо для цього потрібен спосіб додавати елементи на початок або в кінець списку. В інших мовах можна було б скористатися операторами на кшталт : у Haskell або += у Python, але в Roc доведеться використовувати функції List.

Тож у цій вправі дозволено використовувати List.append (але уникаймо будь-яких інших вбудованих функцій).

Багато функціональних мов програмування використовують звʼязні списки як основний тип колекції. Додати елемент на початок або вилучити перший елемент зі звʼязного списку ефективно, тож у таких мовах операції зі списками реалізують через List.prepend. У Roc ж List - це масив (безперервна ділянка байтів). Масиви мають інші властивості, ніж звʼязні списки, як-от здатність ефективно звертатися до елементів за індексом і додавати нові елементи. Через це в Roc ми часто використовуємо List.append і рідко вживаємо List.prepend.

Іменування

У Roc назви трохи відрізняються від тих, що наведені в загальних інструкціях:

• concat замість append
• join замість concatenate
• len замість length
• fold замість foldl
• fold_rev замість foldr

Водночас у Roc стандартними є такі назви функцій:

• filter
• map
• reverse

Підказка

Спробуймо використати:

match list {
    [] => ...
    [first, .. as rest] => ...
}

або

match list {
    [] => ...
    [.. as rest, last] => ...
}