Accumulatore in foldr

Question

Nel Haskell Wikibook, foldr è implementato come segue:

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

Si afferma che il valore iniziale dell'accumulatore è impostato come argomento. Ma, a quanto ho capito, acc è il valore dell'identità per l'operazione (ad esempio 0 per la somma o 1 per il prodotto) e il suo valore non cambia durante l'esecuzione della funzione. Perché allora si fa riferimento qui e in altri testi come un accumulatore, implicando che cambia o accumula un valore passo dopo passo?

Posso vedere che un accumulatore è rilevante in una piega a sinistra, come ad esempio foldl, ma la spiegazione di wikibook è errata, e solo per simmetria, nel qual caso è sbagliato?

Answer 1

consideri la valutazione di un semplice foldr espressione in base alla (corretta) definizione ha fornito:

foldr (+) 0 [1,2,3,4] 
= 1 + foldr (+) 0 [2,3,4] 
= 1 + 2 + foldr (+) 0 [3,4] 
= 1 + 2 + 3 + foldr (+) 0 [4] 
= 1 + 2 + 3 + 4 + foldr (+) 0 [] 
= 1 + 2 + 3 + 4 + 0 
= 10 

Quindi hai ragione: acc in realtà non "accumulare" nulla. Non assume mai un valore diverso da 0.

Perché si chiama "acc" se non è un accumulatore? Somiglianza con foldl? Hysterical raisins? A lie to children? Non ne sono sicuro.

Modifica: farò anche notare che l'implementazione GHC di foldr utilizza z (presumibilmente per zero) anziché acc.

Answer 2

acc non accumula nulla nel caso di foldr come è stato sottolineato.

Vorrei aggiungere che senza di esso, non è chiaro cosa dovrebbe accadere quando l'input è una lista vuota.

Modifica anche la firma del tipo di f, limitando le funzioni che è possibile utilizzare.

es:

foldr' :: (a -> a -> a) -> [a] -> a 
foldr' f [] = error "empty list???" 
foldr' f (x:[]) = x 
foldr' f (x:xs) = f x (foldr' f xs)