Τεχνικά, μια Higher Order Function είναι απλώς μια συνάρτηση που κάνει τουλάχιστον ένα από τα παρακάτω:
- Δέχεται μια συνάρτηση ως ένα από τα ορίσματά της.
- Επιστρέφει μια συνάρτηση ως αποτέλεσμά της.
Στον κόσμο του συναρτησιακού προγραμματισμού, η χρήση τείνει να είναι στενότερη.
Ο όρος συνήθως αναφέρεται σε συναρτήσεις όπως οι filter, map και reduce, που εφαρμόζουν μια συνάρτηση που τους περνάμε στα στοιχεία μιας συλλογής.
Λειτουργίες σε συλλογές
Σε αυτό το σημείο του προγράμματος σπουδών, έχουμε ήδη δει διάφορους τρόπους να εφαρμόζουμε μια πράξη σε όλα τα στοιχεία μιας επαναλήψιμης συλλογής, όπως ένα Vector:
- Με έναν βρόχο (όπως οι περισσότερες γλώσσες προγραμματισμού από την αυγή της ψηφιακής υπολογιστικής).
- Με μια κατανόηση (στο στυλ της Python).
- Με broadcasting (χαρακτηριστική σύνταξη της Julia, αν και με μεγάλο χρέος στις R, Matlab και NumPy).
Αυτή η έννοια θα επικεντρωθεί στις συναρτήσεις ανώτερης τάξης (γνωστές από κάθε συναρτησιακή γλώσσα, όπως η Haskell ή η F#).
Άλλες πιθανές προσεγγίσεις περιλαμβάνουν:
- Την αναδρομή (όπως στις γλώσσες της οικογένειας ML).
- Η Julia το επιτρέπει, αλλά χωρίς βελτιστοποίηση τελικών κλήσεων κινδυνεύει με υπερχείλιση στοίβας.
- Τον μεταπρογραμματισμό με μακροεντολές (παραδοσιακά χαρακτηριστικό της Lisp).
- Χρησιμοποιείται ευρέως στον προχωρημένο προγραμματισμό σε Julia, αλλά στις περισσότερες περιπτώσεις χρησιμοποίησέ το με προσοχή.
- Οι άλλες επιλογές είναι πιθανότατα πιο εύκολες στο γράψιμο και πολύ πιο εύκολες στο debug.
Φιλτράρισμα
Η συνάρτηση 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() μετασχηματίζει μια συλλογή εφαρμόζοντας μια συνάρτηση σε κάθε στοιχείο.
Σε απλές περιπτώσεις αυτό μπορεί να μοιάζει με το broadcasting, με το σχήμα της εξόδου να ταιριάζει με αυτό της εισόδου.
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() για περιπτώσεις όπου η κατεύθυνση έχει σημασία.
Άσκηση εκμάθησης
