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

No puedo entender por qué aparentemente m1 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 las llamadas posteriores (presumiblemente almacena en caché la lista), mientras que m2 10000000 siempre tarda la misma cantidad de tiempo (reconstruir la lista con cada llamada). ¿Tienes idea de lo que está pasando? ¿Existen reglas generales sobre si GHC memorizará una función y cuándo lo hará? Gracias.

GHC no memoriza funciones.

Sin embargo, calcula cualquier expresión dada en el código como máximo 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 usa azúcar sintáctico como en su ejemplo, así que conviértalo a una sintaxis desazucarada equivalente:

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

(Nota: el informe Haskell 98 en realidad describe una sección de operador izquierda (a %)como equivalente a \b -> (%) a b, pero GHC lo desugar (%) a. Estos son técnicamente diferentes porque se pueden distinguir por seq. Creo que podría haber enviado un ticket 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á viendo.

De hecho, 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 resultar problemático en algunas situaciones. Por ejemplo, considere la función

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

GHC puede notar que yno depende xy reescribe 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 alrededor de 1 GB de la memoria donde yse almacena, mientras que la versión original se ejecutaría en un espacio constante y cabría en la caché del procesador. De hecho, en GHC 6.12.1, la función fes casi dos veces más rápida cuando se compila sin optimizaciones de lo que se compila -O2.

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

Consulte la wiki de GHC sobre CAF: http://www.haskell.org/haskellwiki/Constant_applicative_form

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

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

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

No estoy seguro, porque soy bastante nuevo en 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 SOLAMENTE de la entrada. La implicación obvia es que una función sin parámetros devuelve siempre el mismo valor una y otra vez, pase lo que pase.

Aparentemente, hay un mecanismo de optimización en el compilador de GHC que aprovecha este hecho para calcular el valor de dicha función solo una vez durante todo el tiempo de ejecución del programa. Lo hace con pereza, sin duda, pero no obstante lo hace. 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 de probarlo, entré GHCi y escribí: primes !! 1000. Se tomó unos segundos, pero finalmente obtuvo la respuesta: 7927. Luego llamé primes !! 1001y obtuve la respuesta al instante. De manera similar, en un instante obtuve el resultado de take 1000 primes, porque Haskell tuvo que calcular la lista completa de mil elementos para devolver el elemento 1001 antes.

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