la función seq y rigor

Question

Me he estado preguntando mucho sobre esto, pero no he podido encontrar nada al respecto.

Al usar la función seq, ¿cómo funciona realmente realmente? En todas partes, solo se explica diciendo que seq a b evalúa a, descarta el resultado y devuelve b.

Pero, ¿qué significa eso realmente? Sería el siguiente resultado en la evaluación estricta:

foo s t = seq q (bar q t) where 
     q = s*t 

Lo que quiero decir es, se q evaluado rigurosamente antes de ser utilizado en bar? Y sería lo siguiente equivalente:

foo s t = seq (s*t) (bar (s*t) t) 

Me resulta un poco difícil obtener detalles sobre la funcionalidad de esta función.

Answer 1

No estás solo. seq es probablemente una de las funciones de Haskell más difíciles de usar correctamente, por varias razones diferentes. En el primer ejemplo:

foo s t = seq q (bar q t) where 
     q = s*t 

q se evalúa antes de evaluar bar q t. Si bar q t nunca se evalúa, q tampoco lo será. Así que si usted tiene

main = do 
    let val = foo 10 20 
    return() 

como val no se utiliza, no será evaluado. Por lo tanto, q no será evaluado. Si por el contrario tiene

main = print (foo 10 20) 

el resultado de foo 10 20 es evaluado (por print), por lo que dentro de fooq se evalúa antes de que el resultado de bar.

Esta es también la razón esto no funciona:

myseq x = seq x x 

punto de vista semántico, esto significa que la primera x serán evaluados antes de evaluar la segunda x. Pero si el segundo x nunca se evalúa, el primero tampoco tiene que serlo. Entonces seq x x es exactamente equivalente a x.

Su segundo ejemplo puede o no ser lo mismo. Aquí, la expresión s*t se evaluará antes de la salida bar, pero puede no ser la misma s*t como el primer parámetro para bar. Si el compilador realiza una eliminación común de sub-expresiones, puede que las dos expresiones comunes sean comunes. Sin embargo, GHC puede ser bastante conservador acerca de dónde hace CSE, por lo que no puede confiar en esto. Si defino bar q t = q*t, realiza el CSE y evalúa s*t antes de usar ese valor en la barra. Puede que no lo haga para expresiones más complejas.

También es posible que desee saber lo que se entiende por evaluación estricta.seq evalúa el primer argumento para la forma normal de cabeza débil (WHNF), que para los tipos de datos significa desempaquetar el constructor más externo. Considere esto:

baz xs y = seq xs (map (*y) xs) 

xs debe ser una lista, a causa de map. Cuando seq lo evalúa, será esencialmente transformar el código en

case xs of 
    [] -> map (*y) xs 
    (_:_) -> map (*y) xs 

Esto significa que determinará si la lista está vacía o no, a continuación, devuelve el segundo argumento. Tenga en cuenta que ninguno de los valores de la lista se evalúan. Así que usted puede hacer esto:

Prelude> seq [undefined] 4 
4 

pero no este

Prelude> seq undefined 5 
*** Exception: Prelude.undefined 

Cualquiera que sea el tipo que utiliza para seq s primer argumento, la evaluación de WHNF se va lo suficientemente lejos para averiguar el constructor y no hay más datos. A menos que el tipo de datos tenga componentes marcados como estrictos con un patrón bang. Entonces todos los campos estrictos también se evaluarán a WHNF.

Editar: (gracias a Daniel Wagner para la sugerencia en los comentarios)

Para funciones, seq evaluará la expresión hasta que la función "tiene una proyección lambda", lo que significa que está listo para su aplicación. He aquí algunos ejemplos que podrían demuestran lo que esto significa:

-- ok, lambda is outermost 
Prelude> seq (\x -> undefined) 'a' 
'a' 

-- not ok. Because of the inner seq, `undefined` must be evaluated before 
-- the lambda is showing 
Prelude> seq (seq undefined (\x -> x)) 'b' 
*** Exception: Prelude.undefined 

Si se piensa en una unión como un constructor de datos (built-in) de lambda, seq en funciones es perfectamente coherente con su uso en los datos.

Además, "vinculación lambda" abarca todos los tipos de definiciones de funciones, ya sea definidas por la notación lambda o como una función normal.

La sección Controversy de la página de HaskellWiki tiene algunas pequeñas consecuencias acerca de las funciones de seq.

Answer 2

que se pueda imaginar seq como:

seq a b = case a of 
      _ -> b 

Este evaluará a a la cabeza-forma normal (WHNF) y luego continuar con la evaluación de b.

Edición después augustss comentario: este case ... of es el strict, GHC Core one, que siempre obliga a su argumento.