Perché il seguente codice Haskell non terminano:Perché questo codice Haskell non termina?
foldr (||) True $ repeat False -- never terminates
quando qualcosa di simile fa:
foldr (||) False $ repeat True -- => True
Per me, è la seconda espressione che sembra di essere in più problemi di non terminare. Cosa c'è che non va nella mia visione della pigra valutazione di Haskell?
Penso che la tua comprensione del pigro sia corretta, ma non per foldr. Diamo un'occhiata al suo "specification"
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
poi guardare la tua espressione
foldr (||) True $ repeat False -- never terminates
Come si vede il True (z), che siamo "alla ricerca di" per ottenere || di sospendere non sarà raggiunto fino a quando l'intera lista è stata consumata. E ciò non accadrà in quanto la lista è infinita.
Questo dovrebbe anche spiegare l'esempio di chiusura.
In effetti, stavo fraintendendo foldr, non valutazione pigra! –
Il primo si espande a False || (False || (False || ...)), mentre il secondo si espande a True || (True || (True || ...)). Il secondo argomento a foldr è un'aringa rossa: viene visualizzata nell'applicazione più interna di ||, non nell'esterno, quindi non può mai essere effettivamente raggiunta.
Il problema è abbastanza ovvio, se si aprire il foldr manualmente:
foldr (||) True $ repeat False == False || (False || (False (False || ... True)))
Quindi, al fine di ottenere la finale False, il codice ha dovuto valutare la lista fino alla sua (inesistente) finale. Nel secondo esempio, si ripete lo True, pertanto è possibile una valutazione del cortocircuito. Non aspettarti la magia dalla valutazione pigra!
Hai invertito True e False nello svolgimento. –
@Daniel Grazie. È troppo tardi qui a Berlino ... – fuz
Una ennesima intuizione per voi è che || non è commutativa in Haskell, è prevenuto:
Prelude> undefined || True
*** Exception: Prelude.undefined
Prelude> True || undefined
True
Quindi, a differenza in matematica, || e flip (||) sono diverse funzioni. Per esempio. confrontare
foldr (||) False $ repeat True e foldr (flip (||)) False $ repeat True
Gli ex termina, ma quest'ultimo non lo fanno.
Grazie. Questa è davvero un'altra sorpresa per me! –
è sempre possibile utilizzare stepeval per questi tipi di problemi. ci vuole un secondo per decifrare, ma può essere utile. http://bm380.user.srcf.net/cgi-bin/stepeval.cgi?expr=foldr+%28%7C%7C%29+True+%24+repeat+False – gatoatigrado
Ho scritto stepeval e non sta valutando quell'espressione correttamente! Ha alcuni bug, temo (in questo caso dimentica il 'let' anche se ne ha ancora bisogno) –