costo Tempo di Haskell `operatore seq`

Question

This FAQ dice che

L'operatore ss è

seq :: a -> b -> b 

x seq y valuterà x, abbastanza per controllare che non è basso, poi scarto il risultato e valutare y. Questo potrebbe non sembrare utile, ma è che significa che x è valutato per essere valutato prima che y venga considerato.

Questo è tremendamente bello di Haskell, ma vuol dire che in

x `seq` f x 

verrà pagato il costo di valutare x due volte ("scartare il risultato")?

Answer 1

La funzione seq scarterà il valore di x, ma dal momento che il valore è stato valutato, tutti i riferimenti a x sono "aggiornato" per nessun punto più alla versione non valutata di x, ma per indicare invece la versione valutata. Pertanto, anche se seq valuta e rigetta x, il valore è stato valutato anche per gli altri utenti di x, senza alcuna valutazione ripetuta.

Answer 2

No, non è calcolo e dimentica, è calcolo - che forza il caching.

Ad esempio, si consideri questo codice:

let x = 1 + 1 
in x + 1 

Dal Haskell è pigro, questo restituisce ((1 + 1) + 1). Un thunk, contenente la somma di un thunk e uno, il thunk interiore è uno più uno.

Usiamo javascript, una lingua non pigro, per mostrare ciò che questo assomiglia:

function(){ 
    var x = function(){ return 1 + 1 }; 
    return x() + 1; 
} 

concatenamento insieme thunk come questo può cause stack overflows, if done repeatedly, così seq in soccorso.

let x = 1 + 1 
in x `seq` (x + 1) 

sto mentendo quando dico questo restituisce (2 + 1), ma questo è quasi vero - è solo che il calcolo della 2 è costretto ad accadere prima del resto accade (ma il 2 è ancora calcolato pigramente).

Tornando a javascript:

function(){ 
    var x = function(){ return 1 + 1 }; 
    return (function(x){ 
    return x + 1; 
    })(x()); 
} 

Answer 3

Credo che x verrà valutato una sola volta (e il risultato verrà mantenuto per uso futuro, come è tipico per le operazioni lazy). Questo comportamento è ciò che rende utile seq.

Answer 4

Ovviamente seq by itself does not "evaluate" anything. Registra solo la dipendenza dell'ordine di forzatura. La forzatura stessa è innescata dalla corrispondenza del modello. Quando seq x (f x) è forzato, verrà forzato prima x (memoizing il valore risultante), quindi sarà forzato f x.La valutazione lenta di Haskell significa che memorizza i risultati della forzatura delle espressioni, quindi non verrà eseguita alcuna "valutazione" ripetuta (citazioni spaventose qui).

Inserisco "valutazione" in preventivi spaventosi perché implica la valutazione completa. Nelle parole di Haskell wikibook,

"I valori Haskell sono molto stratificati, 'valutare' un valore Haskell potrebbe significare valutare fino a uno di questi livelli."

Permettetemi di ribadire: seq di per sé non valutare nulla.seq x x non valuta x in nessuna circostanza. seq x (f x) non valuta nulla quando f = id, contrariamente a quanto sembra dire lo the report.

Answer 5

Si può sempre verificare con unsafePerformIO o trace ...

import System.IO.Unsafe (unsafePerformIO) 

main = print (x `seq` f (x + x)) 
    where 
    f = (+4) 
    x = unsafePerformIO $ print "Batman!" >> return 3