Perché questo codice Haskell funziona correttamente con elenchi infiniti?

Question

Ho un codice Haskell che fa funziona correttamente su una lista infinita, ma non capisco perché può farlo con successo. (Ho modificato il mio codice originale - che non ha gestito liste infinite - per incorporare qualcosa da qualche altro codice online, e improvvisamente vedo che funziona ma non so perché).

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

mia comprensione di foldr è che sarà un ciclo tra ogni elemento della lista (e forse che la comprensione è incompleta). Se è così, non dovrebbe importare come è formulata la funzione "step" ... il codice dovrebbe essere incapace di gestire loop infiniti.

Tuttavia, le seguenti opere:

*Main Data.List> myAny even [1..] 
True 

Si prega di aiutarmi a capire: perché ??

Answer 1

Facciamo una piccola traccia nella nostra testa di come Haskell valuterà la tua espressione. Sostituendo è uguale per uguale su ogni riga, l'espressione restituisce abbastanza rapidamente True:

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

Questo funziona perché acc viene passato come thunk non valutata (valutazione pigra), ma anche perché la funzione || è severo nel suo prima Argomento.

Quindi questo termina:

True || and (repeat True) 

ma questo non significa:

and (repeat True) || True 

Guardate la definizione di || per vedere il motivo per cui questo è il caso:

True || _ = True 
False || x = x 

Answer 2

Il punto chiave qui è che Haskell è un linguaggio non rigoroso. "Non severi" significa che consente funzioni non rigorose, il che significa che i parametri di funzione potrebbero non essere valutati completamente prima che possano essere utilizzati. Ciò ovviamente consente una valutazione lazy, che è "una tecnica per ritardare un calcolo fino a quando non è richiesto il risultato".

Start dal this Wiki article

Answer 3

non so Haskell, ma ho il sospetto che nel tuo caso, funziona a causa della valutazione pigra. Perché ti permette di lavorare con la lista infinitamente lunga, quando accedici, calcolerà il risultato quando ne hai bisogno.

Vedi http://en.wikipedia.org/wiki/Lazy_evaluation

Answer 4

mia comprensione di foldr è che ciclo volontà attraverso ogni elemento della lista (e forse che la comprensione è incompleta).

foldr (a differenza foldl) non c'è bisogno di scorrere ogni elemento della lista. È istruttivo osservare come è definito foldr.

foldr f z []  = z 
foldr f z (x:xs) = f x (foldr f z xs) 

Quando una chiamata a foldr viene valutata, costringe la valutazione di una chiamata alla funzione f. Notare come la chiamata ricorsiva a foldr è incorporata in un argomento della funzione f. Quella chiamata ricorsiva non viene valutata se f non valuta il suo secondo argomento.