Quali sono alcuni usi interessanti delle funzioni di ordine superiore?

Question

Attualmente sto facendo un corso di programmazione funzionale e sono piuttosto divertito dal concetto di funzioni e funzioni di ordine superiore come cittadini di prima classe. Tuttavia, non riesco ancora a pensare a molte funzioni di ordine superiore praticamente utili, concettualmente sorprendenti o semplicemente interessanti. (Oltre alle tipiche e piuttosto noiose funzioni map, filter, ecc.).

Conoscete esempi di funzioni così interessanti?

Forse funzioni che restituiscono funzioni, funzioni che restituiscono elenchi delle funzioni (?), Ecc

Apprezzerei esempi in Haskell, che è la lingua Attualmente sto imparando :)

Answer 1

Bene, si nota che Haskell non ha sintassi per i loop? No while o do o for. Perché questi sono solo tutte le funzioni di ordine superiore:

funzioni

map :: (a -> b) -> [a] -> [b] 

foldr :: (a -> b -> b) -> b -> [a] -> b 

filter :: (a -> Bool) -> [a] -> [a] 

unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 

iterate :: (a -> a) -> a -> [a] 

di ordine superiore sostituiscono la necessità di cotto nel sintassi nella lingua per strutture di controllo, il che significa praticamente ogni programma Haskell utilizza queste funzioni - che li rende molto utile !

Sono il primo passo verso una buona astrazione perché ora possiamo collegare il comportamento personalizzato a una funzione di scheletro di uso generale.

In particolare, monads sono possibili solo perché possiamo concatenare e manipolare funzioni per creare programmi.

Il fatto è che la vita è piuttosto noiosa quando è il primo ordine. La programmazione diventa interessante solo se si dispone di un ordine superiore.

Answer 2

Ci sono diversi esempi qui: http://www.haskell.org/haskellwiki/Higher_order_function

Vorrei anche raccomandare questo libro: http://www.cs.nott.ac.uk/~gmh/book.html che è un'ottima introduzione a tutti Haskell e copre le funzioni di ordine superiore.

Le funzioni di ordine superiore utilizzano spesso un accumulatore, quindi possono essere utilizzate per formare un elenco di elementi conformi a una determinata regola da un elenco più grande.

Answer 3

Sono richieste anche funzioni di ordine superiore per in fase di elaborazione, che Haskell utilizza ovunque. Essenzialmente, una funzione che prende due argomenti equivale a una funzione che accetta un argomento e restituisce un'altra funzione che accetta un argomento. Quando si vede una firma tipo come questo in Haskell:

f :: A -> B -> C 

... il (->) può essere letto come un diritto-associativa, dimostrando che questo è in realtà una funzione di ordine superiore di ritorno in funzione del tipo di B -> C:

f :: A -> (B -> C) 

una funzione non curry di due argomenti avrebbe invece avere un tipo come questo:

f' :: (A, B) -> C 

Così ogni volta che si utilizza parziale applicazione in Haskell, stai lavorando con funzioni di ordine superiore.

Answer 4

Una cosa interessante e un po 'folle che è possibile fare è simulare un sistema orientato agli oggetti utilizzando una funzione e archiviando i dati nell'ambito della funzione (ad esempio in una chiusura). È un ordine superiore nel senso che la funzione generatore di oggetti è una funzione che restituisce l'oggetto (un'altra funzione).

mio Haskell è piuttosto arrugginita quindi non posso facilmente fare un esempio Haskell, ma ecco un esempio Clojure semplificato che convoglia spera il concetto:

(defn make-object [initial-value] 
    (let [data (atom {:value initial-value})] 
     (fn [op & args] 
     (case op 
      :set (swap! data assoc :value (first args)) 
      :get (:value @data))))) 

Usage:

(def a (make-object 10)) 

(a :get) 
=> 10 

(a :set 40) 

(a :get) 
=> 40 

Same principio funzionerebbe in Haskell (tranne che probabilmente avresti bisogno di cambiare l'operazione di set per restituire una nuova funzione poiché Haskell è puramente funzionale)

Answer 5

Controlla il pa per 'Even Higher-Order Functions for Parsing or Why Would Anyone Ever Want To Use a Sixth-Order Function?' di Chris Okasaki. È scritto usando ML, ma le idee si applicano ugualmente a Haskell.

Answer 6

Ho davvero iniziato a sentire la potenza quando ho imparato che una funzione può far parte di una struttura dati. Ecco una "monade del consumatore" (technobabble: monade gratuita su (i ->)).

data Coro i a 
    = Return a 
    | Consume (i -> Coro i a) 

Quindi un Coro possibile cedere immediatamente un valore, o sarà un altro a seconda del Coro alcuni input. Per esempio, questo è un Coro Int Int:

Consume $ \x -> Consume $ \y -> Consume $ \z -> Return (x+y+z) 

Questo consuma tre ingressi interi e restituisce la loro somma. Si potrebbe anche avere comportano in modo diverso in base agli ingressi:

sumStream :: Coro Int Int 
sumStream = Consume (go 0) 
    where 
    go accum 0 = Return accum 
    go accum n = Consume (\x -> go (accum+x) (n-1)) 

Questo consuma un int e quindi consuma che molte più Ints prima di cedere la loro somma. Questo può essere pensato come una funzione che prende arbitrariamente molti argomenti, costruiti senza magie linguistiche, solo funzioni di ordine superiore.

Le funzioni nelle strutture dati sono uno strumento molto potente che non faceva parte del mio vocabolario prima di iniziare a fare Haskell.

Answer 7

Ecco un piccolo Parafrasato code frammento: diverse funzioni di "ordine superiore"

rays :: ChessPieceType -> [[(Int, Int)]] 
rays Bishop = do 
    dx <- [1, -1] 
    dy <- [1, -1] 
    return $ iterate (addPos (dx, dy)) (dx, dy) 
... -- Other piece types 

-- takeUntilIncluding is an inclusive version of takeUntil 
takeUntilIncluding :: (a -> Bool) -> [a] -> [a] 

possibleMoves board piece = do 
    relRay <- rays (pieceType piece) 
    let ray = map (addPos src) relRay 
    takeUntilIncluding (not . isNothing . pieceAt board) 
    (takeWhile notBlocked ray) 
    where 
    notBlocked pos = 
     inBoard pos && 
     all isOtherSide (pieceAt board pos) 
    isOtherSide = (/= pieceSide piece) . pieceSide 

Questo utilizza:

iterate :: (a -> a) -> a -> [a] 
takeUntilIncluding -- not a standard function 
takeWhile :: (a -> Bool) -> [a] -> [a] 
all :: (a -> Bool) -> [a] -> Bool 
map :: (a -> b) -> [a] -> [b] 
(.) :: (b -> c) -> (a -> b) -> a -> c 
(>>=) :: Monad m => m a -> (a -> m b) -> m b 

(.) è l'operatore ., e (>>=) è la do -notation "interruzione di linea operatore".

Durante la programmazione in Haskell basta usarli. Dove non hai le funzioni di ordine superiore è quando ti rendi conto di quanto fossero incredibilmente utili.

Answer 8

Molte tecniche utilizzate nella programmazione OO sono soluzioni alternative per la mancanza di funzioni di ordine superiore.

Questo include un numero di design patterns che sono onnipresenti nella programmazione funzionale. Ad esempio, il pattern visitor è un modo piuttosto complicato per implementare uno fold.La soluzione è creare una classe con metodi e passare un elemento della classe come argomento, come sostituto per passare una funzione.

Il modello strategy è un altro esempio di uno schema che spesso passa oggetti come argomenti come sostituto di ciò che è effettivamente previsto, funzioni.

Analogamente, dependency injection spesso implica alcuni schemi goffi per passare un proxy per le funzioni quando spesso sarebbe meglio passare semplicemente le funzioni direttamente come argomenti.

Quindi la mia risposta sarebbe che le funzioni di ordine superiore sono spesso utilizzate per eseguire gli stessi tipi di compiti che i programmatori OO eseguono, ma direttamente e con molto meno codice.

Answer 9

Joel Spolsky ha scritto un famous essay dimostrando come Map-Reduce funziona utilizzando le funzioni di ordine superiore di Javascript. Una lettura obbligata per chiunque faccia questa domanda.

Answer 10

Una cosa che è divertente, se non particolarmente pratica, è Church Numerals. È un modo di rappresentare interi usando nient'altro che funzioni. Pazzo, lo so. < shamelessPlug> Ecco uno implementation in JavaScript che ho creato. Potrebbe essere più facile da capire rispetto a un'implementazione Lisp/Haskell. (Probabilmente no, per essere sinceri, JavaScript non era pensato per questo genere di cose.) </shamelessPlug>

Answer 11

Ecco uno schema che non ho visto nominare nessun altro ancora che mi ha davvero sorpreso la prima volta L'ho imparato. Considera un pacchetto di statistiche in cui hai una lista di campioni come input e vuoi calcolare un mucchio di statistiche diverse su di loro (ci sono anche molti altri modi per motivare questo). La linea di fondo è che si dispone di un elenco di funzioni che si desidera eseguire. Come li gestisci tutti?

statFuncs :: [ [Double] -> Double ] 
statFuncs = [minimum, maximum, mean, median, mode, stddev] 

runWith funcs samples = map ($samples) funcs 

Qui sono presenti tutti i tipi di qualità superiore, alcuni dei quali sono stati citati in altre risposte. Ma voglio sottolineare la funzione '$'. Quando ho visto per la prima volta questo uso di "$", sono rimasto senza parole. Prima di allora non avevo ritenuto di essere molto utile se non come una vantaggiosa sostituzione parentesi ... ma questo era quasi magica ...

Answer 12

Sono un fan particolare di ordine superiore Memoizzazione:

memo :: HasTrie t => (t -> a) -> (t -> a) 

(Dato qualsiasi funzione, restituire una versione memoized di tale funzione. limitata dal fatto che gli argomenti della funzione devono poter essere codificato in un trie.)

Questo è da http://hackage.haskell.org/package/MemoTrie

Answer 13

È stato detto che Javascript supporta alcune funzioni di ordine superiore, tra cui an essay from Joel Spolsky. Mark Jason Dominus ha scritto un intero libro chiamato Higher–Order Perl; la fonte del libro è disponibile per il download gratuito in una varietà di formati eccellenti, incluso PDF.

Fin da almeno 3 Perl, Perl ha supportato una funzionalità più simile a Lisp che a C, ma non è stato fino a Perl 5 che il supporto completo per le chiusure e tutto ciò che ne consegue era disponibile. E nessuna delle prime implementazioni di Perl 6 è stata scritta in Haskell, che ha avuto molta influenza su come il design di quella lingua è progredito.

esempi di approcci di programmazione funzionale in Perl appaiono nella programmazione di tutti i giorni, soprattutto con map e grep:

@ARGV = map { /\.gz$/ ? "gzip -dc < $_ |" : $_ } @ARGV; 

@unempty = grep { defined && length } @many; 

Dal sort ammette anche una chiusura, il modello map/sort/map è super comune:

@txtfiles = map { $_->[1] } 
      sort { 
        $b->[0] <=>  $a->[0] 
           || 
       lc $a->[1] cmp lc $b->[1] 
           || 
        $b->[1] cmp  $a->[1] 
      } 
      map { -s => $_ } 
      grep { -f && -T } 
      glob("/etc/*"); 

o

@sorted_lines = map { $_->[0] } 
       sort { 
        $a->[4] <=> $b->[4] 
          || 
        $a->[-1] cmp $b->[-1] 
          || 
        $a->[3] <=> $b->[3] 
          || 
        ... 
       } 
       map { [$_ => reverse split /:/] } @lines; 

La funzione reduce rende lista hackery facile senza looping:

$sum = reduce { $a + $b } @numbers; 

$max = reduce { $a > $b ? $a : $b } $MININT, @numbers; 

C'è molto più di questo, ma questo è solo un assaggio. Le chiusure facilitano la creazione di generatori di funzioni, scrivendo le proprie funzioni di ordine superiore, non solo usando i builtin. In effetti, uno dei modelli di eccezione più comuni,

try { 
    something(); 
} catch { 
    oh_drat(); 
}; 

è non un built-in. Tuttavia, è quasi banale definire con try una funzione che accetta due argomenti: una chiusura nel primo argomento e una funzione che richiede una chiusura nel secondo.

Perl 5 non ha integrato il curriculum, sebbene esista un modulo per questo. Perl 6, tuttavia, ha continui curricula e continuazioni di prima classe, oltre a molto altro ancora.

Answer 14

Martín Escardó fornisce an interesting example of a higher-order function:

equal :: ((Integer -> Bool) -> Int) -> ((Integer -> Bool) -> Int) -> Bool 

Dati due funzionali f, g :: (Integer -> Bool) -> Int, quindi equal f g decide se f e g sono (estensionalmente) pari o no, anche se f e g non hanno un dominio finito. In effetti, il codominio, Int, può essere sostituito da qualsiasi tipo con un'uguaglianza decidibile.

Il codice fornito da Escardó è scritto in Haskell, ma lo stesso algoritmo dovrebbe funzionare in qualsiasi linguaggio funzionale.

È possibile utilizzare le stesse tecniche descritte da Escardó per calcolare integrali definiti di qualsiasi funzione continua con precisione arbitraria.