haskell - ¿Por qué el producto[0..] no se evalúa como "instantáneamente"?

lazy-evaluation

Question

Estoy tratando de entender la pereza. Debido a que 0 multiplicado por cualquier número es 0, ¿no debería el product [0..] evaluar a 0? También intenté foldl (*) 1 [0..] , y para definir mi propio producto como

myProduct 0 _ = 0
myProduct _ 0 = 0
myProduct a b = a*b

¿Por qué no se detiene el pliegue tan pronto como se encuentra un 0?

Answer 1

Debido a que el operador de multiplicar no sabe que está encadenado, y la función de plegado no conoce el comportamiento particular del operador de multiplicar para cualquier argumento. Con esa combinación, necesita agotar la lista para terminar el pliegue. De hecho, por esta razón, foldl no funciona en absoluto en listas infinitas. foldr hace, porque puede expandir la función desde el encabezado de la lista.

foldl (*) 1 [0..] -> (((..(((1*0)*1)*2)*3....)*inf

La multiplicación más externa en el caso de foldl nunca se puede encontrar, porque la lista es infinita. Por lo tanto, no puede seguir la cadena para concluir que el resultado es cero. Puede, y lo hace, calcular el producto a lo largo de la lista, y ese producto pasa a ser cero, pero no terminará. Si utiliza scanl en su lugar, puede ver estos productos intermedios.

foldr (*) 1 [0..] -> 0*(1*(2*(3*((...((inf*1)))...)))

La multiplicación más externa en el caso de foldr se encuentra inmediatamente, porque el resto de la lista se deja de hecho como un thunk perezoso. Solo se ejecuta un paso:

foldr (*) 1 [0..] -> 0*(foldr (*) 1 [1..])

Entonces, debido a que su operador de multiplicación personalizado myProduct no es estricto en el segundo argumento, si el primer argumento es cero, foldr myProduct 1 [0..] puede terminar.

Como nota al margen, la función de producto de preludio está restringida a listas finitas (y puede implementarse con foldl). Incluso si usara foldr, probablemente no sería un atajo porque el operador de multiplicación estándar es estricto; Hacer lo contrario sería computacionalmente costoso en el caso común donde los productos no son ni cero ni están encadenados.

-- sum and product compute the sum or product of a finite list of numbers.

sum, product     :: (Num a) => [a] -> a
sum              =  foldl (+) 0  
product          =  foldl (*) 1

Además, hay una razón por la que no usa foldr; Como pudimos ver en las funciones de expansión y exploración, los pliegues de la izquierda pueden calcularse a medida que consumen la lista. El pliegue derecho, si el operador no realiza un atajo, debe construir una expresión tan grande como la propia lista para comenzar el cálculo. Esta diferencia se debe a que es la expresión más interna la que inicia el cálculo en el caso estricto, pero la expresión más externa es la que produce el resultado, lo que permite el caso perezoso. Lazy vs no-estricta en la wiki de Haskell podría explicar mejor que yo, e incluso menciona que la coincidencia de patrones, que usó para describir el acceso directo en myProduct, puede ser estricta.

Answer 2

Puedes tenerlo así:

myproduct xs = foldr op id xs 1
  where
    op x r acc = if x==0 then 0 else acc `seq` r (acc*x)

Este es un pliegue a la derecha que multiplica los números de la izquierda, opera en espacio constante, y se detiene tan pronto como se encuentra un 0.

Answer 3

Si cambias las dos primeras líneas:

myProduct _ 0 = 0
myProduct 0 _ = 0
myProduct a b = a*b

el segundo argumento siempre se evaluará antes del primero y el plegado infinito ya no funcionará.

Dado que es imposible definir un myProduct que funcione perezosamente para ambos argumentos (no evaluar el segundo si el primero es 0 y no evaluar el primero si el segundo es 0) quizás estemos mejor con tener * siempre evaluar ambos argumentos.