comportamento foldl rispetto a foldr con elenchi infiniti

Question

Il codice per la funzione myAny in questa domanda usa cartellar.Interrompe l'elaborazione di un elenco infinito quando il predicato è soddisfatto.

L'ho riscritto usando foldl:

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

(Notare che gli argomenti della funzione step sono correttamente invertiti.)

Tuttavia, non interrompe più l'elaborazione di elenchi infiniti.

Ho tentato di tracciare l'esecuzione della funzione come in La risposta di Apocalisse:

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

Tuttavia, questo non è il modo in cui si comporta la funzione.In che modo è sbagliato?

Answer 1

Come folds differ sembra essere una frequente fonte di confusione, quindi ecco una panoramica più generale:

Prendi in considerazione la possibilità di raggruppare un elenco di n valori [x1, x2, x3, x4 ... xn ] con qualche funzione f e seme z.

foldl È:

• Associativo di sinistra: f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Coda ricorsiva:Scorre l'elenco, producendo successivamente il valore
• Pigro:Nulla viene valutato finché non è necessario il risultato
• Indietro: foldl (flip (:)) [] inverte un elenco.

foldr È:

• Associativo giusto: f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• Ricorsivo in un argomento:Si applica ogni iterazione f al valore successivo e il risultato della piegatura del resto dell'elenco.
• Pigro:Nulla viene valutato finché non è necessario il risultato
• In avanti: foldr (:) [] restituisce una lista invariata.

C'è un punto un po' sottile qui che a volte fa inciampare le persone:Perché foldl È indietro ogni applicazione di f viene aggiunto al al di fuori del risultato;e perché lo è Pigro, non viene valutato nulla finché non viene richiesto il risultato.Ciò significa che per calcolare qualsiasi parte del risultato, Haskell esegue prima l'iterazione del file intero elenco costruendo un'espressione di applicazioni di funzioni nidificate, quindi valuta il più esterno funzione, valutandone gli argomenti secondo necessità.Se f usa sempre il suo primo argomento, questo significa che Haskell deve ricorrere fino al termine più interno, quindi lavorare all'indietro calcolando ogni applicazione di f.

Questo è ovviamente molto diverso dall'efficiente ricorsione in coda che la maggior parte dei programmatori funzionali conosce e ama!

In effetti, anche se foldl è tecnicamente ricorsivo in coda, perché l'intera espressione del risultato viene costruita prima di valutare qualsiasi cosa, foldl può causare un overflow dello stack!

D'altra parte, considera foldr.È anche pigro, ma perché corre avanti, ogni applicazione di f viene aggiunto al dentro del risultato.Quindi, per calcolare il risultato, Haskell costruisce a separare applicazione della funzione, il cui secondo argomento è il resto dell'elenco ripiegato.Se f è pigro nel suo secondo argomento, ad esempio un costruttore di dati, il risultato sarà sempre più pigro, con ogni passaggio della piega calcolato solo quando viene valutata una parte del risultato che lo richiede.

Quindi possiamo capire perché foldr a volte funziona su elenchi infiniti quando foldl non:Il primo può convertire pigramente un elenco infinito in un'altra struttura dati infinita pigra, mentre il secondo deve ispezionare l'intero elenco per generare qualsiasi parte del risultato.D'altra parte, foldr con una funzione che necessita immediatamente di entrambi gli argomenti, ad esempio (+), funziona (o meglio, non funziona) in modo molto simile foldl, costruendo un'espressione enorme prima di valutarla.

Quindi i due punti importanti da notare sono questi:

• foldr può trasformare una struttura dati ricorsiva pigra in un'altra.
• Altrimenti, i piegamenti pigri si bloccheranno con un overflow dello stack su elenchi grandi o infiniti.

Potresti aver notato che sembra foldr può fare tutto foldl può, e altro ancora.Questo è vero!Infatti, foldl è quasi inutile!

Ma cosa succede se vogliamo produrre un risultato non pigro ripiegando una lista ampia (ma non infinita)?Per questo, vogliamo a piega rigorosa, Quale le librerie standard forniscono con cura:

foldl' È:

• Associativo di sinistra: f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• Coda ricorsiva:Scorre l'elenco, producendo successivamente il valore
• Rigoroso:Ogni applicazione di funzione viene valutata lungo il percorso
• Indietro: foldl' (flip (:)) [] inverte un elenco.

Perché foldl' È rigoroso, per calcolare il risultato Haskell lo farà valutare f ad ogni passo, invece di lasciare che l’argomento di sinistra accumuli un’espressione enorme e non valutata.Questo ci dà la solita ed efficiente ricorsione della coda che desideriamo!In altre parole:

• foldl' può piegare elenchi di grandi dimensioni in modo efficiente.
• foldl' si bloccherà in un ciclo infinito (senza causare un overflow dello stack) su un elenco infinito.

Il wiki di Haskell ha una pagina che parla di questo, anche.

Answer 2

myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

ecc.

Intuitivamente, foldl è sempre sul "fuori" o "sinistra" in modo che viene espansa prima. All'infinito.

Answer 3

Si può vedere nella documentazione di Haskell qui che foldl è ricorsiva in coda e non avrà mai fine se approvata una lista infinita, in quanto si chiede al parametro successivo prima di restituire un valore di ...

Answer 4

Non so Haskell, ma nello Schema, fold-right farà sempre 'atto' l'ultimo elemento di una lista prima. Così è non funziona per lista ciclico (che è lo stesso come quello infinito).

Non sono sicuro se fold-right può essere scritto ricorsiva in coda, ma per ogni lista ciclica si dovrebbe ottenere un overflow dello stack. fold-left OTOH è normalmente implementato con ricorsione in coda, e sarà solo rimanere bloccati in un loop infinito, se non terminare presto.