2012-09-12 4 views
6

Duplicar posibles:
When is memoization automatic in GHC Haskell?Haskell y memoization de la función pura resulta

Como consecuencia, la pura función siempre devuelve el mismo valor para una entrada fija. Dicho esto, ¿Haskell (más precisamente GHC) almacena en caché (memoriza) automáticamente estos resultados si hay suficiente memoria (pregunta 1) y el desarrollador tiene algún control sobre ella (pregunta 2)?

+1

@LoganCapaldo Oh, sí, ya veo. Pero esa publicación tiene alrededor de 2 años, tal vez hubo algún progreso. – Cartesius00

+3

Si edita su pregunta para a) reconocer la otra yb) aclarar qué quiere decir con "progreso" en comparación con la respuesta al original y o por qué o por qué no ocurriría el "progreso" podría haber algunas respuestas valiosas. No estoy preparado para entrar en ello, pero creo que encontrarás que la memorización automática del tipo que podrías estar imaginando es una lata de gusanos más grande de lo que podría parecer a primera vista. –

Respuesta

11

que votaron para cerrar, pero la respuesta corta:

GHC no hace ninguna memoization automática de funciones, y que es probablemente una buena cosa, ya que haría que la complejidad del espacio aún más difícil de razonar acerca. Además, la memorización no es en general un problema muy solucionable, ya que requiere que el argumento de la función sea comparable para la igualdad, lo que no es realmente posible para todos los tipos (por ejemplo, funciones).

Haskell tiene una semántica no estricta. GHC proporciona una llamada, más o menos, por modelo de costo de necesidad. Aunque la sobrecarga de la evaluación diferida a altos niveles de optimización no es tan mala debido al analizador de rigor.

Es muy fácil de implementar la memorización en Haskell utilizando la evaluación perezosa. Sin embargo, ten cuidado con el uso del espacio.

fib' :: (Integer -> Integer) -> Integer -> Integer 
fib' f 0 = 0 
fib' f 1 = 1 
fib' f n | n > 1 = (f (n - 1)) + ((f (n - 2)) 

slow_fib :: Integer -> Integer 
slow_fib = fib' slow_fib 

fibs :: [Integer] 
fibs = map (fib' memo_fib) [0..] 

memo_fib :: Integer -> Integer 
memo_fib n = fibs !! n 

Esto no es tan rápido, y es una fuga de espacio, pero capta la idea general. Puede learn more on the Haskell wiki.