Esempio di funzione ricorsiva Haskell con foldr

Question

Ho ripreso l'apprendimento di Haskell, dopo una breve interruzione e attualmente sto cercando di capire meglio come funzionano le espressioni di ricorsione e lambda in Haskell.

In questo: YouTube video, c'è un esempio funzione che mi ha molto più di quanto probabilmente dovrebbe puzzle, in termini di come funziona realmente:

firstThat :: (a -> Bool) -> a -> [a] -> a 
firstThat f = foldr (\x acc -> if f x then x else acc) 

Per motivi di chiarezza e dato che non era immediatamente ovvio per me, ti darò un esempio di applicazione di questa funzione per alcuni argomenti:

firstThat (>10) 2000 [10,20,30,40] --returns 20, but would return 2000, if none of the values in the list were greater than 10 

favore correggetemi, se le mie ipotesi sono sbagliate.

Sembra firstThat prende tre argomenti:

1. una funzione che prende un argomento e restituisce un valore booleano. Poiché l'operatore > è in realtà una funzione infisso, il primo argomento nell'esempio precedente sembra il risultato di un'applicazione parziale alla funzione >: è corretta?
2. un valore specificato dello stesso tipo previsto come argomento mancante alla funzione fornita come primo argomento
3. un elenco di valori del tipo suddetto

Ma la funzione effettiva firstThat sembra essere definito in modo diverso dalla sua dichiarazione di tipo, con un solo argomento. Dal momento che lo foldr accetta normalmente tre argomenti che ho raccolto, è in atto una sorta di applicazione parziale. L'espressione lambda fornita come argomento a foldr sembra che manchi anche i suoi argomenti.

Quindi, come funziona esattamente questa funzione? Mi scuso se sono troppo denso o non riesco a vedere la foresta per gli alberi, ma non riesco a capirlo, il che è frustrante.

Qualsiasi utile spiegazione o esempio (s) sarebbe molto apprezzato.

Grazie!

Answer 1

Ma la funzione effettiva firstThat sembra essere definito in modo diverso dalla sua dichiarazione tipo, con solo un argomento. Dal momento che lo foldr accetta normalmente tre argomenti che ho raccolto, è in atto una sorta di applicazione parziale.

Hai ragione. Tuttavia, c'è un modo più bello di dirlo che parlare di "argomenti mancanti" - uno che non ti porta a chiedere dove sono andati. Ecco due modi in cui gli argomenti non mancano.

In primo luogo, considerare questa funzione:

add :: Num a => a -> a -> a 
add x y = x + y 

Come forse sapete, possiamo anche definire in questo modo:

add :: Num a => a -> a -> a 
add = (+) 

che funziona perché le funzioni Haskell sono valori come qualsiasi altro. Possiamo semplicemente definire un valore, add, come uguale a un altro valore, (+), che sembra essere una funzione. Non è richiesta una sintassi speciale per dichiarare una funzione.Il risultato è che scrivere argomenti esplicitamente è (quasi) mai necessario; il motivo principale per cui lo facciamo perché rende spesso il codice più leggibile (ad esempio, potrei definire firstThat senza scrivere esplicitamente il parametro f, ma non lo farò perché il risultato è piuttosto orribile).

In secondo luogo, ogni volta che si vede un tipo di funzione con tre argomenti ...

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

... si può anche leggere come questo ...

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

... che è , una funzione di un argomento che produce una funzione di due argomenti. Questo funziona per tutte le funzioni di più di un argomento. La chiave d'asporto è che, nel cuore, tutte le funzioni di Haskell richiedono un solo argomento. Questo è il motivo per cui un'applicazione parziale funziona. Quindi, vedendo ...

firstThat :: (a -> Bool) -> a -> [a] -> a 
firstThat f = foldr (\x acc -> if f x then x else acc) 

... si può dire che con precisione che hai scritto esplicitamente tutti i parametri che prende firstThat - vale a dire, una sola :)

---

Il lambda espressione fornita come argomento a foldr sembra che manchi anche i suoi argomenti.

Non proprio. foldr (quando limitato a liste) è ...

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

... e così la funzione passata ad esso prende due argomenti (sentitevi liberi di aggiungere le virgolette aria intorno "due", data la discussione di cui sopra). La lambda è stato scritto come ...

\x acc -> if f x then x else acc 

... con due argomenti espliciti, x e acc.

Answer 2

una funzione che accetta un argomento e restituisce un valore booleano. Poiché l'operatore> è in realtà una funzione infissa, il primo argomento nell'esempio precedente sembra il risultato di un'applicazione parziale alla funzione>: è corretto?

sì: (>10) è l'abbreviazione di \x -> x > 10, proprio come (10>) sarebbe l'abbreviazione di \x -> 10 > x.

un valore non specificato dello stesso tipo previsto come l'argomento mancante alla funzione fornita come primo argomento

prima di tutto, non è un argomento mancante: omettendo un argomento, si ottiene un valore della funzione. tuttavia, il tipo del secondo argomento corrisponde effettivamente all'argomento della funzione >10, così come corrisponde al tipo di elementi dell'elenco [10,20,30,40] (che è un miglior ragionamento).

un elenco di valori del tipo suddetto

sì.

Ma la funzione effettiva prima Sembra essere definita diversamente dalla dichiarazione del tipo, con un solo argomento. Dato che foldr normalmente accetta tre argomenti, ho riscontrato che si sta verificando una sorta di applicazione parziale. L'espressione lambda fornita come argomento di foldr sembra che manchi anche i suoi argomenti.

perché è dato, ad es. foo x y z = x * y * z, queste 2 linee sono equivalenti:

bar x  = foo x 
bar x y z = foo x y z 

- che è a causa di un concetto chiamato accattivarsi. Il Currying è anche il motivo per cui le firme dei tipi di funzione non sono (a, b) -> c ma invece a -> b -> c, che a sua volta equivale a a -> (b -> c) a causa della giusta associatività dell'operatore di tipo ->.

Pertanto, queste due linee sono equivalenti:

firstThat f  = foldr (\x acc -> if f x then x else acc) 
firstThat f x y = foldr (\x acc -> if f x then x else acc) x y 

---

Nota: che è possibile utilizzare anche Data.List.find combinato con Data.Maybe.fromMaybe:

λ> fromMaybe 2000 $ find (>10) [10, 20, 30] 
20 
λ> fromMaybe 2000 $ find (>10) [1, 2, 3] 
2000 

---

Vedi anche:

• https://en.wikipedia.org/wiki/Currying.
• https://www.fpcomplete.com/user/EFulmer/currying-and-partial-application
• http://learnyouahaskell.com/higher-order-functions