Domande su pieghe e overflow dello stack

Question

Learn È un Haskell parla foldl' come alternativa al foldl perché foldl è incline a impilare overflow.

• Secondo LYAH, foldl (+) 0 (replicate 1000000 1) deve sovrapporsi, ma non sulla mia macchina. Perché no? Anche se aumentassi quel numero a 10 milioni, non fuoriesce. Prende solo molta memoria fino a quando il mio computer OS X diventa inutilizzabile e devo riavviarlo.
• In quali casi è necessario utilizzare foldl anziché foldl'? Nella mia esperienza foldl' "funziona correttamente" mentre foldl può essenzialmente danneggiare il mio computer (vedi sopra).
• Non capisco perché non ci sia nulla di simile per foldr. Perché lo stack dello stack foldr non può essere sovraccarico e perché non c'è lo foldr'?

Answer 1

Non si blocca con overflow dello stack perché lo stack è ora infinito per impostazione predefinita. Cioè, il comportamento di runtime predefinito di GHC è quello di consentire allo stack di crescere indefinitamente - non esiste alcun limite che può innescare un errore di overflow dello stack.

https://ghc.haskell.org/trac/ghc/ticket/8189

Ecco una descrizione di come funziona:

pile della discussione (tra cui stack del thread principale) vivono sul mucchio. Con lo lo stack cresce, i nuovi blocchi di stack vengono aggiunti come richiesto; se lo stack si riduce di nuovo, questi blocchi di stack aggiuntivi vengono recuperati dal raccoglitore di dati inutili . La dimensione iniziale dello stack predefinita è volutamente piccola, in ordine per mantenere il tempo e lo spazio in eccesso per la creazione del thread su un minimo e per rendere pratico lo spawn dei thread anche per le minuscole parti di lavoro .

Answer 2

Perché non è possibile foldr overflow dello stack e perché non c'è foldr '?

Ebbene, foldr non è ricorsiva coda, cioè esso non chiama direttamente su se stesso:

foldr f a (x:xs) = f x (foldr f a xs) 

Dopo foldr è ridotto, il controllo passa al fornita dall'utente f. Pertanto, non è necessario disporre di un foldr' che forza gli argomenti prima di passarli a f: se ciò è voluto, il chiamante può semplicemente passare un rigoroso f (ad esempio sfruttando modelli di scoppio o seq).

Se l'overflow dello stack dipende da cosa fa f. Ad esempio,

f x y = x 

causerà l'accesso alla lista solo nel suo primo elemento. Al contrario,

f x y = seq y x 

potrebbe causare un overflow dello stack (o un comportamento a uso di memoria).Invece,

f x y = x+1 : y 

farà sì che la lista di output da produrre pigramente, in modo simile a map (+1) xs, senza alcuna brutta sorpresa.

Come sottolinea @dfeuer, esiste Data.Foldable.foldr' che funziona su qualsiasi Foldable come una piega a destra rigorosa. Sulle liste, è praticamente ridondante, come discusso sopra. Su altri tipi Foldable, può invece essere significativo.