¿Cuándo es automática la memorización en GHC Haskell?

Question

No puedo entender por qué M1 es al parecer memoized mientras m2 no está en lo siguiente:

m1  = ((filter odd [1..]) !!) 

m2 n = ((filter odd [1..]) !! n) 

m1 10000000 tarda alrededor de 1,5 segundos en la primera convocatoria, y una fracción de eso en llamadas posteriores (presumiblemente almacena en caché la lista), mientras que m2 10000000 siempre toma la misma cantidad de tiempo (reconstruyendo la lista con cada llamada). ¿Tienes idea de lo que está pasando? ¿Hay alguna regla general sobre si y cuando GHC memorizará una función? Gracias.

Answer 1

GHC no memoriza funciones.

lo hace, sin embargo, calcular cualquier expresión dada en el código como máximo una vez por cada vez que se introduce su entorno lambda-expresión, o como máximo una vez cada vez si se está en el nivel superior. Determinar dónde los lambda-expresiones son Puede ser un poco complicada cuando se utiliza azúcar sintáctico como en su ejemplo, así que vamos a convertir estos al equivalente de la sintaxis Desazucarado:

m1' = (!!) (filter odd [1..])    -- NB: See below! 
m2' = \n -> (!!) (filter odd [1..]) n 

(Nota: El informe de Haskell 98 describe realmente un operador de izquierda sección como (a %) como equivalente a \b -> (%) a b, pero GHC desugars a (%) a. Estos son técnicamente diferentes, ya que pueden ser distinguidos por seq. Creo que podría haber presentado un billete GHC Trac sobre esto.)

Teniendo en cuenta esto, se puede ver que en m1', la expresión filter odd [1..] no está contenida en n cualquier expresión lambda, por lo que solo se computará una vez por ejecución de su programa, mientras que en m2', filter odd [1..] se computará cada vez que se ingrese la expresión lambda, es decir, en cada llamada de m2'. Eso explica la diferencia en el tiempo que estás viendo.

---

En realidad, algunas versiones de GHC, con ciertas opciones de optimización, compartirán más valores que la descripción anterior indica. Esto puede ser problemático en algunas situaciones. Por ejemplo, considere la función

f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x]) 

GHC podría darse cuenta de que y no depende de x y volver a escribir la función de

f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x]) 

En este caso, la nueva versión es mucho menos eficiente, ya que tendrá para leer aproximadamente 1 GB de la memoria donde se almacena y, mientras que la versión original se ejecutará en espacio constante y se ajustará en la memoria caché del procesador. De hecho, bajo GHC 6.12.1, la función f es casi el doble de rápida cuando se compila sin optimizaciones que la compilada con -O2.

Answer 2

m1 se calcula una sola vez porque es un formulario de aplicación constante, mientras que m2 no es un CAF, por lo que se calcula para cada evaluación.

Véase el wiki de GHC en los CAF: http://www.haskell.org/haskellwiki/Constant_applicative_form

Answer 3

Hay una diferencia fundamental entre las dos formas: la restricción se aplica a monomorphism M1 pero no M2, porque m2 ha dado explícitamente argumentos. Entonces, el tipo de m2 es general, pero m1 es específico.Los tipos que se les asignan son:

m1 :: Int -> Integer 
m2 :: (Integral a) => Int -> a 

compiladores más Haskell e intérpretes (todos ellos, que yo sepa en realidad) no memoize estructuras polimórficas, por lo que la lista interna de m2 se vuelve a crear cada vez que se llama, en donde de M1 no es .

Answer 4

No estoy seguro, porque soy bastante nuevo para Haskell, pero parece que es porque la segunda función está parametrizada y la primera no. La naturaleza de la función es que, su resultado depende del valor de entrada y en el paradigma funcional, especialmente depende de la entrada. La implicación obvia es que una función sin parámetros devuelve siempre el mismo valor una y otra vez, sin importar qué.

Aparently hay un mecanismo de optimización en el compilador GHC que explota este hecho para calcular el valor de dicha función una sola vez para todo el tiempo de ejecución del programa. Lo hace perezosamente, sin duda, pero lo hace de todos modos. Me di cuenta de que yo mismo, cuando escribí la siguiente función:

primes = filter isPrime [2..] 
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n] 
     where f `divides` n = (n `mod` f) == 0 

Luego de probarlo, entré GHCi y escribió: primes !! 1000. Me tomó unos segundos, pero finalmente obtuve la respuesta: 7927. Luego llamé al primes !! 1001 y obtuve la respuesta al instante. Del mismo modo, en un instante obtuve el resultado para take 1000 primes, porque Haskell tuvo que calcular toda la lista de mil elementos para devolver 1001º elemento antes.

Por lo tanto, si puede escribir su función de modo que no requiera parámetros, probablemente la desee. ;)