costo Tiempo de Haskell `operador seq`

Question

This FAQ dice que

El operador de la SEC es

seq :: a -> b -> b 

x seq y evaluará x, suficiente para comprobar que no es inferior, entonces descarte el resultado y evalúa y. Esto puede no parecer útil, pero significa que se garantiza que x se evalúa antes de considerar a y.

Eso es tremendamente agradable de Haskell, pero tampoco significa que en

x `seq` f x 

el costo de la evaluación de x se pagarán dos veces ("descartar el resultado")?

Answer 1

La función seq para desechar el valor de x, pero desde entonces se ha evaluado el valor, todas las referencias a x están "actualizado" a ningún punto más en la versión sin evaluar de x, pero en su lugar apunta a la versión evaluada. Por lo tanto, aunque seq evalúa y descarta x, el valor se ha evaluado también para otros usuarios de x, lo que no permite realizar evaluaciones repetidas.

Answer 2

No, no es calcular y olvidar, es cálculo, lo que obliga al almacenamiento en caché.

Por ejemplo, considere este código:

let x = 1 + 1 
in x + 1 

Desde Haskell es perezoso, esto se evalúa como ((1 + 1) + 1). Un thunk, que contiene la suma de un thunk y uno, siendo el thunk interno uno más uno.

Vamos a usar JavaScript, un lenguaje no perezoso, para mostrar el aspecto que tiene:

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

el encadenamiento de los procesadores sencillos como este puede cause stack overflows, if done repeatedly, por lo seq al rescate.

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

que miento cuando te digo esto se evalúa como (2 + 1), pero eso es casi cierto - es sólo que el cálculo de la 2 se ve obligado a pasar antes de que ocurra el resto (pero el 2 todavía se calcula perezosamente).

Volviendo a javascript:

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

Answer 3

Creo que x solo se evaluará una vez (y el resultado se conservará para usarlo en el futuro, como es habitual en las operaciones perezosas). Ese comportamiento es lo que hace que seq sea útil.

Answer 4

Por supuesto seq by itself does not "evaluate" anything. Simplemente registra la dependencia del orden de forzamiento. El forzamiento mismo se desencadena mediante la coincidencia de patrones. Cuando se fuerza seq x (f x), primero se forzará x (memorizando el valor resultante) y luego se forzará f x.La evaluación perezosa de Haskell significa que memoriza los resultados del forzamiento de expresiones, por lo que no se realizará una "evaluación" repetida (citas de miedo aquí).

Pongo "evaluación" en citas de miedo porque implica evaluación completa. En las palabras de Haskell wikibook,

"Los valores de Haskell están muy estratificados; 'evaluar' un valor de Haskell podría significar evaluar cualquiera de estas capas."

Permítanme reiterar: seq por sí mismo no evalúa nada.seq x x no evalúa x bajo ninguna circunstancia. seq x (f x) no evalúa nada cuando f = id, contrariamente a lo que the report parece haber estado diciendo.

Answer 5

Siempre se puede comprobar 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