Haskell Language
Funzioni di ordine superiore

Osservazioni

Nozioni di base su funzioni di ordine superiore

Rivedi l' applicazione parziale prima di procedere.

In Haskell, una funzione che può assumere altre funzioni come argomenti o funzioni di ritorno è chiamata funzione di ordine superiore .

Di seguito sono elencate tutte le funzioni di ordine superiore :

map       :: (a -> b) -> [a] -> [b]
filter    :: (a -> Bool) -> [a] -> [a]
takeWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]
iterate   :: (a -> a) -> a -> [a]
zipWith   :: (a -> b -> c) -> [a] -> [b] -> [c]
scanr     :: (a -> b -> b) -> b -> [a] -> [b]
scanl     :: (b -> a -> b) -> b -> [a] -> [b]

Questi sono particolarmente utili in quanto ci permettono di creare nuove funzioni in aggiunta a quelle che già abbiamo, passando funzioni come argomenti ad altre funzioni. Da qui il nome, le funzioni di ordine superiore .

Tenere conto:

Prelude> :t (map (+3))
(map (+3)) :: Num b => [b] -> [b]

Prelude> :t (map (=='c'))
(map (=='c')) :: [Char] -> [Bool]

Prelude> :t (map zipWith)
(map zipWith) :: [a -> b -> c] -> [[a] -> [b] -> [c]]

Questa capacità di creare facilmente funzioni (come ad esempio un'applicazione parziale come quella usata qui) è una delle caratteristiche che rendono la programmazione funzionale particolarmente potente e ci consente di ricavare soluzioni brevi ed eleganti che altrimenti prenderebbero dozzine di linee in altre lingue. Ad esempio, la seguente funzione ci fornisce il numero di elementi allineati in due elenchi.

aligned :: [a] ->  [a] -> Int
aligned xs ys = length (filter id (zipWith (==) xs ys))

Lambda Expressions

Le espressioni Lambda sono simili alle funzioni anonime in altre lingue.

Le espressioni lambda sono formule aperte che specificano anche le variabili che devono essere associate. La valutazione (trovare il valore di una chiamata di funzione) viene quindi ottenuta sostituendo le variabili associate nel corpo dell'espressione lambda, con gli argomenti forniti dall'utente. In parole povere, le espressioni lambda ci consentono di esprimere le funzioni tramite binding e sostituzione variabili.

Le espressioni Lambda sono simili

\x -> let {y = ...x...} in y

All'interno di un'espressione lambda, le variabili sul lato sinistro della freccia sono considerate vincolate sul lato destro, cioè sul corpo della funzione.

Considera la funzione matematica

f(x) = x^2

Come definizione Haskell lo è

f    x =  x^2

f = \x -> x^2

il che significa che la funzione f è equivalente all'espressione lambda \x -> x^2 .

Considerare il parametro della map funzioni di ordine superiore, che è una funzione di tipo a -> b . Nel caso in cui venga utilizzato una sola volta in una chiamata per map e in nessun altro punto del programma, è opportuno specificarlo come espressione lambda invece di nominare una tale funzione throwaway. Scritto come espressione lambda,

\x -> let {y = ...x...} in y

x contiene un valore di tipo a , ...x... è un'espressione Haskell che si riferisce alla variabile x y contiene un valore di tipo b . Quindi, per esempio, potremmo scrivere quanto segue

map (\x -> x + 3)

map (\(x,y) -> x * y)

map (\xs -> 'c':xs) ["apples", "oranges", "mangos"]

map (\f -> zipWith f [1..5] [1..5]) [(+), (*), (-)]

accattivarsi

In Haskell, tutte le funzioni sono considerate al curry: cioè, tutte le funzioni in Haskell richiedono un solo argomento.

Prendiamo la funzione div :

div :: Int -> Int -> Int

Se chiamiamo questa funzione con 6 e 2 otteniamo in modo inaspettato 3:

Prelude> div 6 2
3

Tuttavia, questo non si comporta nel modo in cui potremmo pensare. Il primo div 6 viene valutato e restituisce una funzione di tipo Int -> Int . Questa funzione risultante viene quindi applicata al valore 2 che restituisce 3.

Quando guardiamo la firma del tipo di una funzione, possiamo spostare il nostro pensiero da "prende due argomenti di tipo Int " a "prende un Int e restituisce una funzione che accetta un Int ". Questo viene riaffermato se consideriamo che le frecce nella notazione del tipo si associano alla destra , quindi div può infatti essere letto così:

div :: Int -> (Int -> Int)

In generale, la maggior parte dei programmatori può ignorare questo comportamento almeno mentre stanno imparando la lingua. Da un punto di vista teorico , "le dimostrazioni formali sono più facili quando tutte le funzioni sono trattate in modo uniforme (un argomento in, uno risultato)."