Perché questo codice Haskell funziona correttamente con elenchi infiniti?

Question

Ho del codice Haskell che funziona correttamente su un elenco infinito, ma non capisco perché può farlo con successo. (Ho modificato il mio codice originale - che non gestiva elenchi infiniti - per incorporare qualcosa di un 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

La mia comprensione di foldr è che passerà in rassegna tutti gli elementi dell'elenco (e forse quella comprensione è incompleta). In tal caso, non dovrebbe importare come il "passaggio" la funzione è definita ... il codice non dovrebbe essere in grado di gestire infiniti loop.

Tuttavia, le seguenti opere:

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

Per favore aiutami a capire: perché ??

Answer 1

Facciamo una piccola traccia nella nostra testa di come Haskell valuterà la tua espressione. Sostituendo uguale a uguale su ogni riga, l'espressione si valuta abbastanza rapidamente su 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 valutato (valutazione pigra), ma anche perché la funzione || è rigorosa nella sua prima argomento.

Quindi questo termina:

True || and (repeat True)

Ma questo non:

and (repeat True) || True

Guarda la definizione di || per capire perché questo è il caso:

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

Answer 2

  

La mia comprensione di Foldr è che   passerà in rassegna ogni elemento nel file   lista (e forse quella comprensione   è incompleto).

foldr (a differenza di foldl ) non deve scorrere in sequenza ogni elemento dell'elenco. È istruttivo esaminare come viene definito foldr .

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

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

Answer 3

Il punto chiave qui è che Haskell è un linguaggio non rigoroso. & Quot; non rigorosa " significa che consente funzioni non rigide, il che a sua volta significa che i parametri delle funzioni potrebbero non essere completamente valutati prima di poter essere utilizzati. Ciò ovviamente consente una valutazione pigra, che è "una tecnica per ritardare un calcolo fino a quando il risultato non è richiesto".

Inizia da questo articolo Wiki

Answer 4

Non conosco Haskell, ma sospetto che nel tuo caso funzioni a causa di una valutazione pigra. Poiché ti consente di lavorare con un elenco infinitamente lungo, quando accedi ad esso, calcolerà il risultato quando ne avrai bisogno.

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