para pagina oficial mac descargar haskell ghc memoization

pagina - haskell website



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

GHC no memoriza funciones.

Sin embargo, calcula cualquier expresión dada en el código a lo sumo una vez cada vez que se ingresa su expresión lambda circundante, o como máximo una vez si está en el nivel superior. Determinar dónde están las expresiones lambda puede ser un poco complicado cuando usas azúcar sintáctico como en tu ejemplo, así que conviértelos a una sintaxis desajustada equivalente:

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

(Nota: El informe Haskell 98 realmente describe una sección de operador izquierdo como (a %) como equivalente a /b -> (%) ab , pero GHC lo desagrupa a (%) a . Estos son técnicamente diferentes porque se pueden distinguir por seq . Creo que podría haber presentado un boleto de GHC Trac sobre esto.)

Dado esto, puede ver que en m1'' , la expresión filter odd [1..] no está contenida en ninguna expresión lambda, por lo que solo se calculará una vez por ejecución de su programa, mientras que en m2'' , filter odd [1..] se calculará 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 de los que indica la descripción anterior. 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 notar que y no depende de x y reescribir la función para

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

En este caso, la nueva versión es mucho menos eficiente porque tendrá que leer aproximadamente 1 GB de la memoria donde y está almacenada, 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 cuando se compila con -O2 .

No puedo entender por qué m1 aparentemente está memorizado mientras que m2 no está en lo siguiente:

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

m1 10000000 tarda aproximadamente 1,5 segundos en la primera llamada, y una fracción de eso en llamadas posteriores (presumiblemente almacena en caché la lista), mientras que m2 10000000 siempre lleva la misma cantidad de tiempo (reconstruye 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.

Hay una diferencia crucial entre las dos formas: la restricción de monomorfismo se aplica a m1 pero no a m2, porque m2 tiene explícitamente argumentos dados. Entonces, el tipo de m2 es general, pero m1 es específico. Los tipos que están asignados son:

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

La mayoría de los compiladores e intérpretes de Haskell (todos ellos que conozco en realidad) no memorizan las estructuras polimórficas, por lo que la lista interna de m2 se recrea cada vez que se invoca, donde m1 no lo hace.

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 el tiempo de ejecución del programa completo. Lo hace perezosamente, sin duda, pero lo hace de todos modos. Lo noté 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, para probarlo, ingresé a GHCI y escribí: primes !! 1000 primes !! 1000 . Me tomó unos segundos, pero finalmente obtuve la respuesta: 7927 . ¡Entonces llamé a primes !! 1001 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 manera que no tome parámetros, probablemente la quiera. ;)