Perché procedure di ordine superiore?

Question

Quindi, se una lingua fornisce una procedura di ordine superiore, allora posso avere una procedura che restituisce la procedura. Qualcosa del tipo:

(define (Proc a b c)
  (lambda (x) ( #| method body here in terms of a b c and x |# )))

Per creare una nuova procedura, farei semplicemente qualcosa del tipo:

(define ProcA (Proc a1 b1 c1)) ; Would create ProcA that has 1 argument

Attività simili potrebbero essere eseguite in una lingua che non supporta la procedura di ordine superiore definendo Proc che accetta 4 anziché 3 argomenti e chiamando questa procedura per definire ProcA , come:

(define (Proc a b c x) ( #| method body -- does not return any procedure |# )
(define (ProcA x) (Proc a1 b1 c1 x))

Quindi perché c'è così tanta confusione sulla procedura di ordine superiore? Mi sto perdendo qualcosa?

Answer 1

È una buona osservazione che una funzione che restituisce un'altra funzione è la stessa di una funzione che accetta due argomenti. Questo è chiamato " Currying " ;. Detto in altro modo, una funzione da A a B è la prova di un'implicazione logica, che A implica B, oppure:

A => B.

Come noti, se A implica che B implica C, allora A e B implicano C, oppure:

(A => (B => C)) <==> ((A, B) => C)

Ma una funzione di ordine superiore non è necessariamente una funzione che restituisce un'altra funzione. Una funzione di ordine superiore è una funzione che utilizza un'altra funzione come argomento . Questa è una differenza importante e gli HOF sono strumenti di programmazione estremamente potenti.

Ad esempio, considera questa funzione di Haskell:

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : (map f xs)

Questa funzione di ordine superiore accetta una funzione f e la applica a tutti gli elementi di un elenco. Nelle lingue senza HOF, dovresti fare ciò che questa funzione fa con un loop o qualcosa di simile, ma in una lingua che ha HOF, puoi chiamare f per ogni elemento nell'elenco con una semplice chiamata come questa :

map f myList

Certo, i costrutti di controllo nelle lingue ti consentono di approssimare le funzioni di ordine superiore, ma una lingua che ha funzioni di ordine superiore ti consente di inventare i tuoi costrutti di controllo . Lo schema certamente si qualifica.

Answer 2

Non proverò a ricapitolare l'argomento qui, ma in Perché Questioni di programmazione funzionale , John Hughes sostiene che le funzioni di ordine superiore sono utili perché forniscono modi più efficaci per "incollare insieme". parti di un programma e quindi semplificano il riutilizzo del codice. Gli esempi sono in un linguaggio molto vecchio che non viene più utilizzato molto, ma sono ancora facili da seguire e abbastanza convincenti. Leggere l'articolo di John è un buon modo per ottenere una risposta dettagliata alla tua domanda "perché c'è così tanta confusione sulle procedure di ordine superiore".

Answer 3

Si tratta più della mentalità che della fattibilità. Ti consente di trattare le funzioni come cittadini di prima classe e pensare in termini di funzioni che operano su funzioni per creare altre funzioni, ecc.

Ovviamente potresti farlo o simularlo con altre lingue, ma se non è un meccanismo sintattico è un po 'trattato come un'aggiunta o un hack.

Answer 4

OK, ma nel secondo esempio, stai creando quella procedura in fase di compilazione con un elenco preordinato di a1 , b1 e c1 . Nel primo esempio, lo stai creando in fase di esecuzione quando chiami ProcA e puoi crearne quanti ne desideri, in modo da poter fare cose molto più interessanti.

Answer 5

Pensa a una funzione di trasformazione o a un algoritmo di ordinamento attraverso un array. Ora, vuoi renderlo davvero flessibile in modo da consentire all'utente della tua funzione di specificare il comportamento della tua funzione lasciando loro passare una funzione come argomento.

Supponiamo che tu scriva un algoritmo di ordinamento con il seguente prototipo procedurale:

sort(Array a, void (*fn)(a::element_type, a::element_type));

L'utente di quella funzione potrebbe specificare, passando il fn appropriato, se desidera un ordine decrescente o crescente.

Answer 6

Avresti bisogno di una classe interna per simularlo correttamente. Il primo caso, Proc è chiuso su a, bec. Nel secondo caso, il chiamante di ProcA non può controllare il modo in cui a1, b1 e c1 vengono passati all'altra procedura, può solo controllare x. Quindi, il modo in cui controlli a1, b1 e c1 è attraverso le variabili di utilizzo in un ambito più elevato (livello del modulo o qualcosa del genere), il che rende la tua funzione non pura. In tal caso, non è possibile garantire che, dati gli stessi argomenti tra le chiamate, ProcA restituirà lo stesso risultato. Dove con Proc, puoi sempre essere sicuro che se lo chiami con gli stessi argomenti, accadranno gli stessi risultati.

Answer 7

Uso le funzioni di ordine superiore in JavaScript, ad esempio, quando utilizzo una casella di selezione. Posso passare la funzione che verrà chiamata quando viene selezionata un'opzione, poiché l'unica differenza per me era che, che semplifica il mio codice, riduce la ridondanza.

Vedo la stessa cosa in altre lingue che utilizzo che supporta le funzioni di ordine superiore, in quanto posso quindi iniziare a vedere come ripulire il mio codice, dove c'è una ridondanza che può essere localizzata e qualsiasi differenza può essere fatto in una funzione.

Una volta supportato C #, sapevo che ora era più mainstream. :)

Answer 8

Se una funzione accetta e / o restituisce una funzione, viene chiamata funzione di ordine superiore (HOF). Per i programmatori inesperti, provenienti da C, C ++ o Java, le funzioni di ordine superiore sembrano magiche, ma sono molto semplici. Immagina una semplice funzione che restituisce il risultato di 2 + 3:

(define (foo) (+ 2 3)) ;; (foo) => 5

Questa è una funzione noiosa, aggiunge sempre da 2 a 3. Che cosa succede se la generalizziamo, in modo che aggiunga 2 non solo a 3, ma a qualsiasi numero fornito dall'utente?

(define (foo n) (+ 2 n)) ;; (foo 10) => 12

Quando una lingua non supporta le funzioni di ordine superiore, sei costretto a pensare che funzioni e valori (ad esempio numeri, valori booleani, elenchi) siano 2 cose distinte. Ma programmazione funzionale (FP) offusca la distinzione tra di loro. Immagina che l'unica differenza tra una funzione e un valore sia che una funzione può essere chiamata, a parte questo puoi fare una funzione qualunque cosa tu possa fare con un 2 o #t o '(abc) : potresti fornirlo come argomento, oppure tornare da una funzione, o archiviarlo in una variabile o inserirlo in un elenco. Ad esempio, generalizziamo ulteriormente la nostra piccola funzione, quindi non solo potrebbe aggiungere 2 a n , ma moltiplicare 2 per n o applicare qualsiasi altra funzione che accetti due numeri :

(define (foo f n) (f 2 n))
;; (foo + 10) => 12
;; (foo * 10) => 20
;; (foo expt 10) => 1024

Quando ti rendi conto che una funzione può essere trattata nello stesso modo in cui un numero o una stringa vengono trattati, anonimo funzioni (chiamate & # 8220; lambdas & # 8221; in gergo FP) hanno perfettamente senso. Le funzioni anonime sono in realtà più basilari e & # 8220; normali & # 8221; rispetto alle normali funzioni con nome, le funzioni con nome sono solo funzioni anonime inserite in una variabile, proprio come abbiamo inserito un numero in una variabile per usarlo più volte.

(+ 2 2) ;; is no different from:
(let ((a 2)) (+ a a))
(lambda (x y) (* x y)) ;; is no different from:
(define (foo x y) (* x y)) ;; which is an abbreviation for:
(define foo (lambda (x y) (* x y))).

Quindi gli HOF ci consentono di generalizzare le nostre funzioni per renderle super flessibili. Se guardi la tua funzione, vedi la logica dietro di essa, puoi capire che se qualcosa opera sui tuoi dati, probabilmente anche qualcos'altro potrebbe farlo. Se aggiungi 2 numeri insieme, potresti probabilmente moltiplicarli, sottrarli o esponerli tra loro o altro. Invece di scrivere una nuova funzione per ogni caso ogni volta, potresti semplicemente accettare un parametro aggiuntivo, che deve essere una funzione.

In FP utilizziamo sempre HOF, ad esempio, quando manipoliamo elenchi. 3 funzioni sono bread and butter di FP: map , filter e foldl . map accetta una funzione con 1 argomento, applica questa funzione a ogni elemento di un elenco e restituisce un nuovo elenco con elementi modificati. filter accetta un predicato (funzione che restituisce un valore booleano) con 1 argomento, applica il predicato a ogni elemento di un elenco e restituisce un nuovo elenco con elementi che non soddisfano il predicato rimosso.

(map (lambda (n) (+ n 1)) '(1 2 3 4 5) ;; '(2 3 4 5 6)
(define (foo n) (+ n 1))
(map foo '(1 2 3 4 5)) ;; '(2 3 4 5 6)
(filter (lambda (n) (> n 3)) '(1 2 3 4 5)) ;; '(4 5)
(define (bar n) (> n 3))
(filter bar '(1 2 3 4 5)) ;; '(4 5)

Immagina di avere un elenco di funzioni 1-arity & # 8212; di nuovo, puoi fare quello che vuoi con una funzione e archiviarlo anche in una struttura di dati & # 8212; e vuoi applicarle tutte al stesso numero e ottieni un elenco di risultati.

(let ((xs (list (lambda (x) (+ x 1))
                (lambda (x) (* x 2))
                (lambda (x) (- x)))))
  (map (lambda (f) (f 10)) xs)) ;; => (11 20 -10)

Conclusione: quando un linguaggio di programmazione supporta correttamente i concetti di programmazione funzionale, le funzioni di ordine superiore consentono flessibilità e generalità, il che rende il tuo codice più potente (puoi usare la stessa funzione per vari casi d'uso ) e conciso (non è necessario scrivere 10 versioni di una funzione). Alcune funzioni di ordine superiore sono utilizzate pesantemente nella programmazione funzionale, in modo da sbarazzarsi di cicli for-basso e dettagliati e scrivere una riga che fa tutto invece.

Nota: foldl , che è lo stesso di & # 8220; piega a sinistra & # 8221; o & # 8220; lasciato ridurre & # 8221 ;, è ancora più potente. Se sei davvero interessato e hai tempo, ti preghiamo di leggere la prima metà di la mia risposta usando ridurre . Anche se non è scritto per Scheme / Racket, ma invece per Common Lisp / Emacs Lisp, puoi ancora capire l'idea che sta dietro fold / ridurre.