Tecnicamente, una Higher Order Function è semplicemente una funzione che fa almeno una di queste cose:
- Accetta una funzione come uno dei suoi argomenti.
- Restituisce una funzione come risultato.
Nel mondo della programmazione funzionale, l'uso tende a essere più ristretto.
Il termine di solito si riferisce a funzioni come filter, map e reduce, che applicano una funzione passata agli elementi di una collezione.
Operare sulle collezioni
A questo punto del percorso, abbiamo già visto vari modi per applicare un'operazione a tutti gli elementi di una collezione iterabile, come un Vector:
- Usare un ciclo (come nella maggior parte dei linguaggi di programmazione fin dall'alba dell'informatica digitale).
- Usare una comprensione (in stile Python).
- Usare il broadcasting (sintassi tipicamente Julia, anche se con un grande debito verso R, Matlab e NumPy).
Questo concetto si concentrerà sulle funzioni di ordine superiore (note a chiunque abbia usato un linguaggio funzionale, come Haskell o F#).
Altri approcci possibili includono:
- La ricorsione (come nei linguaggi della famiglia ML).
- Julia lo permette, ma senza l'ottimizzazione delle chiamate in coda rischia di esaurire lo stack.
- La metaprogrammazione con le macro (tradizionalmente una caratteristica di Lisp).
- È molto usata nella programmazione avanzata in Julia, ma da affrontare con cautela nella maggior parte dei casi.
- Le altre opzioni sono probabilmente più facili da scrivere e molto più facili da debuggare.
Filtrare
La funzione filter() accetta una funzione passata con un valore restituito booleano e la applica a una collezione.
Solo gli elementi che restituiscono true vengono inclusi nel valore restituito, che è dello stesso tipo di base dell'input (vedi sotto).
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)
Con gli array multidimensionali, filter appiattisce le dimensioni dell'input e restituisce un Vector: la principale eccezione a qualsiasi regola sulla corrispondenza tra tipo di output e tipo di input.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> filter(isodd, m)
3-element Vector{Int64}:
1
5
3
Gli esempi sopra usano funzioni integrate, ma in questo contesto è molto comune l'uso di funzioni anonime.
julia> filter(x -> x % 3 == 0, 1:20)
6-element Vector{Int64}:
3
6
9
12
15
18
Esiste anche una versione in-place, filter!(), come per molte delle funzioni di questo concetto.
Mappare
La funzione map() trasforma una collezione applicando una funzione a ogni elemento.
Nei casi semplici può essere simile al broadcasting, con la forma dell'output che corrisponde a quella dell'input.
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() opera elemento per elemento anche su più collezioni.
julia> map(*, [1, 2], [3, 4])
2-element Vector{Int64}:
3
8
Concettualmente, possiamo pensarlo come equivalente a eseguire zip() sulle diverse collezioni di input, e poi map() su ogni elemento del risultato intermedio.
È solo un'analogia approssimativa, che non implica nulla sull'implementazione!
Come con zip(), le collezioni di forma non corrispondente vengono troncate alla dimensione (o alle dimensioni) della più piccola.
A volte servono solo gli effetti collaterali della funzione passata, come una scrittura su database o un push! su un array.
In quel caso è disponibile la funzione di ordine superiore foreach(), che restituisce sempre nothing.
Ridurre
La funzione reduce() accetta una funzione a 2 argomenti e la applica a una collezione, portando a una riduzione di dimensionalità.
Detto così in astratto può sembrare confuso, ma pensa a funzioni come sum() o prod(), che prendono una collezione e restituiscono un unico valore.
julia> sum(1:4) # add
10
julia> prod(1:4) # multiply
24
Queste funzioni specializzate sono altamente ottimizzate e andrebbero sempre usate quando sono disponibili.
Altri esempi includono maximum() e minimum(), le funzioni logiche all() e any() e molte funzioni statistiche.
Solo a scopo illustrativo, considera la stessa funzionalità implementata con la più generica reduce() (ricorda che gli operatori infissi + e * in realtà internamente sono funzioni).
julia> reduce(+, 1:4) # add
10
julia> reduce(*, 1:4) # multiply
24
Come con sum() e altre funzioni di aggregazione, reduce() può accettare un argomento per parola chiave opzionale dims, per specificare la dimensione (o le dimensioni) da ridurre.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> reduce(+, m; dims=1)
1×3 Matrix{Int64}:
5 7 9
Questi esempi sono facili, perché la somma e la moltiplicazione sono sia commutative (1+2 == 2+1) sia associative ( (1+2)+3 == 1+(2+3) ).
Ma questo è ben lungi dall'essere universale!
Persino operazioni comuni come la sottrazione e la divisione non sono associative.
C'è anche il problema aggiuntivo che gli errori in virgola mobile possono accumularsi su collezioni grandi, quindi una riduzione da sinistra a destra può produrre una risposta leggermente diversa da una da destra a sinistra.
La direzione della funzione reduce di Julia dipende dall'implementazione e non è garantita.
Per controllare esplicitamente la direzione, esistono le funzioni foldl() e foldr(), che in linea teorica partono rispettivamente da «sinistra» e da «destra» (in realtà dall'alto e dal basso, nel caso di un Vector).
julia> foldl(-, 1:3) # (1 - 2) - 3
-4
julia> foldr(-, 1:3) # 1 - (2 - 3)
2
Nota che queste sono pensate per collezioni che possono essere trattate come monodimensionali, restituendo un risultato scalare.
L'uso di un argomento dims non è supportato da foldl e foldr, ma solo da reduce.
MapReduce
Combinare un'operazione di map con una reduce è molto comune in vari ambiti della programmazione.
Potremmo eseguire map in sequenza e poi eseguire reduce su una collezione intermedia.
Tuttavia, questo è inefficiente nella migliore delle ipotesi e scala molto male man mano che la collezione diventa più grande.
È caldamente consigliato usare invece la funzione combinata mapreduce().
Può implementare un algoritmo molto più performante che intreccia le operazioni di map e reduce.
Il primo argomento è la funzione con cui fare la map, il secondo argomento è l'operatore di 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
Come ci si potrebbe aspettare, Julia ha anche le funzioni mapfoldl() e mapfoldr() per le situazioni in cui la direzione è importante.
Esercizio di apprendimento
