Технічно, Higher Order Function це просто функція, яка робить принаймні одне з такого:
- Приймає функцію як один зі своїх аргументів.
- Повертає функцію як результат.
У світі функціонального програмування вжиток зазвичай вужчий.
Зазвичай цей термін позначає такі функції, як filter, map і reduce, які застосовують передану функцію до елементів колекції.
Операції над колекціями
На цьому етапі силабусу ми вже бачили різні способи застосувати операцію до всіх елементів колекції, яку можна перебирати, як-от Vector:
- Використати цикл (як у більшості мов програмування від початку цифрової ери).
- Використати включення (у стилі Python).
- Використати трансляцію (характерний синтаксис Julia, хоча й багато запозичено з R, Matlab і NumPy).
Ця концепція зосередиться на функціях вищого порядку (знайомих із будь-якої функціональної мови, як-от Haskell чи F#).
Інші можливі підходи:
- Рекурсія (як у мовах родини ML).
- Julia дозволяє це, але без оптимізації хвостових викликів це загрожує переповненням стека.
- Метапрограмування з макросами (традиційна особливість Lisp).
- Це широко використовується в просунутому програмуванні Julia, але в більшості випадків до цього варто підходити обережно.
- Інші варіанти, ймовірно, легше написати й набагато легше зневаджувати.
Фільтрування
Функція filter() приймає передану функцію, яка повертає булеве значення (англ. Boolean), і застосовує її до колекції.
До поверненого значення потрапляють лише елементи, для яких функція повертає true; воно має той самий базовий тип, що й вхідні дані (див. нижче).
julia> filter(iseven, 1:6)
3-element Vector{Int64}:
2
4
6
# String is a collection of Chars, so String in -> String out
julia> filter(!isascii, "Hrōðgār")
"ōðā"
# tuple input -> tuple output
julia> filter(iseven, (1, 2, 3, 4, 5))
(2, 4)
Для багатовимірних масивів filter вирівнює вхідні виміри й повертає Vector: головний виняток із будь-якого правила про відповідність типу вихідних даних типу вхідних.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> filter(isodd, m)
3-element Vector{Int64}:
1
5
3
У прикладах вище використано вбудовані функції, але анонімні функції в цьому контексті дуже поширені.
julia> filter(x -> x % 3 == 0, 1:20)
6-element Vector{Int64}:
3
6
9
12
15
18
Існує також версія на місці, filter!(), як і для багатьох функцій у цій концепції.
Відображення
Функція map() перетворює колекцію, застосовуючи функцію до кожного елемента.
У простих випадках це може бути схоже на трансляцію, коли форма вихідних даних збігається з формою вхідних.
julia> map(√, [1, 4, 9])
3-element Vector{Float64}:
1.0
2.0
3.0
julia> map(x -> x^2 + 1, 1:4)
4-element Vector{Int64}:
2
5
10
17
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> map(√, m)
2×3 Matrix{Float64}:
1.0 1.41421 1.73205
2.0 2.23607 2.44949
map() також працює поелементно з кількома колекціями.
julia> map(*, [1, 2], [3, 4])
2-element Vector{Int64}:
3
8
Концептуально це можна уявити як еквівалент запуску zip() для кількох вхідних колекцій, а потім map() для кожного елемента проміжного результату.
Це лише приблизна аналогія, яка нічого не каже про реалізацію!
Як і з zip(), колекції невідповідної форми обрізаються до виміру (вимірів) найменшої.
Іноді потрібні лише побічні ефекти переданої функції, як-от запис у базу даних або push! до масиву.
Тоді доступна функція вищого порядку foreach(), яка завжди повертає nothing.
Згортання
Функція reduce() приймає функцію з двома аргументами й застосовує її до колекції, що приводить до зменшення вимірності.
Абстрактно це може звучати заплутано, але погляньмо на такі функції, як sum() або prod(), які приймають колекцію й повертають одне значення.
julia> sum(1:4) # add
10
julia> prod(1:4) # multiply
24
Ці спеціальні функції добре оптимізовані, і їх завжди варто використовувати, коли вони доступні.
Інші приклади: maximum() і minimum(), логічні функції all() та any(), а також багато статистичних функцій.
Лише для ілюстрації погляньмо на ту саму функціональність, реалізовану через загальнішу reduce() (нагадаємо, що інфіксні оператори + і * насправді є функціями всередині).
julia> reduce(+, 1:4) # add
10
julia> reduce(*, 1:4) # multiply
24
Як і sum() та інші функції агрегації, reduce() може приймати необовʼязковий іменований аргумент dims, щоб указати вимір (виміри) для згортання.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> reduce(+, m; dims=1)
1×3 Matrix{Int64}:
5 7 9
Це прості приклади, бо додавання й множення є комутативними (1+2 == 2+1) та асоціативними ( (1+2)+3 == 1+(2+3) ).
Це далеко не універсально!
Навіть такі звичні операції, як віднімання й ділення, неасоціативні.
Є додаткова проблема: помилки чисел із плаваючою комою можуть накопичуватися у великих колекціях, тож згортання зліва направо може дати трохи інший результат, ніж справа наліво.
Напрямок роботи функції reduce у Julia залежить від реалізації й не гарантований.
Щоб явно контролювати напрямок, є функції foldl() і foldr(), які умовно починають відповідно з «лівого» й «правого» краю (насправді зверху й знизу для Vector).
julia> foldl(-, 1:3) # (1 - 2) - 3
-4
julia> foldr(-, 1:3) # 1 - (2 - 3)
2
Зауважмо, що вони призначені для колекцій, які можна розглядати як одновимірні, і повертають скалярний результат.
Використання аргументу dims не підтримується для foldl і foldr, лише для reduce.
MapReduce
Поєднання операції map з reduce дуже поширене в різних галузях програмування.
Ми могли б послідовно виконати map, а потім reduce для проміжної колекції.
Однак це у кращому разі неефективно й дуже погано масштабується зі зростанням колекції.
Замість цього наполегливо рекомендується використовувати обʼєднану функцію mapreduce().
Вона може реалізувати значно продуктивніший алгоритм, який переплітає операції map/reduce.
Перший аргумент - функція для відображення, другий - оператор згортання.
julia> mapreduce(x -> x^2 + 1, +, 1:3)
17
# equivalent to (2 + 5 + 10)
julia> sum(map(x -> x^2 + 1, 1:3))
17
Як і можна було очікувати, у Julia також є функції mapfoldl() і mapfoldr() для ситуацій, де напрямок важливий.
Навчальна вправа
