Quanti argomenti prende la funzione foldr di Haskell?

Question

Sono nuovo di Haskell e sto leggendo il libro "Real World Haskell". Nel capitolo 4 del libro l'autore chiede come esercizio di riscrivere la funzione groupby usando fold. Uno dei lettori del libro (Ottaviano Voicu) ha dato la seguente soluzione:

theCoolGroupBy :: (a -> a -> Bool) -> [a] -> [[a]] 
theCoolGroupBy eq xs = tail $ foldr step (\_ -> [[]]) xs $ (\_ -> False) 
         where step x acc = \p -> if p x then rest p else []:rest (eq x) 
              where rest q = let y:ys = acc q in (x:y):ys 

mia domanda è semplice: So che foldr prende 3 argomenti: una funzione, un valore iniziale e un elenco. Ma nella seconda riga del codice foldr accetta 4 argomenti. Perché questo succede? Grazie.

Answer 1

La risposta di Scott è corretta, il risultato di foldr è una funzione, quindi questo è il motivo per cui sembra che lo foldr richieda 4 argomenti. Le foldr funzioni ci vuole 3 argomenti (funzione, di base, le liste):

*Main> :type foldr 
foldr :: (a -> b -> b) -> b -> [a] -> b 

mi limiterò a dare qui un esempio che è meno complessa:

inc :: Int -> (Int -> Int) 
inc v = \x -> x + v 

test = inc 2 40 -- output of test is 42 

Nel codice precedente, inc prende uno argomento, v e restituisce una funzione che incrementa il suo argomento per v.

Come possiamo vedere qui, il tipo di ritorno di inc 2 è una funzione, per cui il suo argomento può essere semplicemente aggiunto alla fine:

*Main> :type inc 
inc :: Int -> Int -> Int 
*Main> :type inc 2 
inc 2 :: Int -> Int 
*Main> :type inc 2 40               
inc 2 40 :: Int 

parentesi potrebbero essere utilizzati per sottolineare che il valore di ritorno è una funzione , ma funzionalmente è identico al codice di cui sopra:

*Main> (inc 2) 40 
42 

PS: sono l'autore del commento originale :)

Answer 2

In questo caso, foldr viene utilizzato per creare una funzione. (\_ -> False) è l'argomento di quella funzione.

Answer 3

Tutte le funzioni in Haskell richiedono un solo argomento. Quando abbiamo una funzione con tipo a -> b -> c, è solo un modo più breve per scrivere a -> (b -> c), cioè una funzione, che accetta un argomento e produce una funzione che accetta un altro argomento. Vedere Currying per ulteriori informazioni.

In questo caso, vedere la risposta di @ sepp2k. foldr produce una funzione e ha bisogno di un altro argomento ("il 4").

Answer 4

In questa situazione, penso che sia meglio guardare la firma tipo di foldr:

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

e che corrisponda a quello per l'espressione che abbiamo (con parentesi aggiunto per chiarezza):

(foldr step (\_ -> [[]]) xs) (\_ -> False) 

Il secondo argomento di foldr è dello stesso tipo del suo risultato. In questo caso il secondo argomento è una funzione. In questo caso, ciò significa che l'espressione foldr con 3 argomenti sarà una funzione.

Quello che si vede essere il 4 ° argomento della funzione foldr potrebbe anche essere pensato come il primo argomento del risultato foldr!