Συναρτήσεις ανώτερου βαθμού

Στα μαθηματικά και στην επιστήμη των υπολογιστών μια συνάρτηση ανώτερου βαθμού (Αγγλικά higher-order function ή functional form ή functional ή functor) είναι μια μαθηματική συνάρτηση που έχει τα παρακάτω χαρακτηριστικά :

• παίρνει μια ή περισσότερες συναρτήσεις ως είσοδο
• επιστρέφει μια συνάρτηση ως έξοδο

Οι υπόλοιπες συναρτήσεις θεωρούνται πρώτου βαθμού συναρτήσεις. Στο λάμβδα-λογισμό όλες οι συναρτήσεις θεωρούνται συναρτήσεις ανώτερου βαθμού που παίρνουν τιμές στην μορφή $(\tau _{1}\to \tau _{2})\to \tau _{3}\to \tau _{4}$ (που σημαίνει ότι έχουμε ως είσοδο μια συνάρτηση από $\tau _{1}\to \tau _{2}$ και η έξοδος είναι μια νέα συνάρτηση $\tau _{3}\to \tau _{4}$). Ως παράδειγμα συνάρτησης ανώτερου βαθμού να πάρουμε την συνάρτηση applyTwice η οποία παίρνει ως είσοδο μια συνάρτηση και επιστρέφει την συνάρτηση εφαρμοσμένη δύο φορές. Παρακάτω είναι η συνάρτηση ορισμένη στην γλώσσα Haskell και έχει τύπο $(a\to a)\to a\to a$ (που σημαίνει ότι παίρνει ως είσοδο μια συνάρτηση $(a\to a)$ και επιστρέφει μια νέα συνάρτηση $a\to a$):

applyTwice :: (a -> a) -> a -> a  
applyTwice f x = f (f x)

Τρέχουμε μερικά παραδείγματα με την παραπάνω συνάρτηση στον διερμηνέα ghci της Haskell. Στο πρώτο παράδειγμα τρέχει δύο φορές την συνάρτηση / τελεστή πολλαπλασιασμού στην τιμή του 10 και αποτιμάται η έκφραση (2*10)*2. Στο δεύτερο παράδειγμα τρέχει η συνάρτηση ένωσης λιστών με χαρακτήρες ++ δύο φορές πάνω στην λίστα/αλφαριθμητικό χαρακτήρων εκτελώντας την έκφραση ("example" ++ " 1") + " 1".

*Main> applyTwice (*2) 10
40
*Main> applyTwice (++ " 1") "example"
"example 1 1"