16

No está seguro de qué es exactamente a Google por esta cuestión, por lo que voy a publicar directamente al SO:optimización de la función de llamadas en Haskell

  1. variables en Haskell son inmutables
  2. funciones puras deberían dar lugar a los mismos valores para los mismos argumentos

a partir de estos dos puntos es posible deducir que si se llama somePureFunc somevar1 somevar2 en su código dos veces, que sólo tiene sentido para calcular el valor en la primera llamada. El valor resultante puede almacenarse en una especie de tabla hash gigante (o algo así) y buscarse durante las siguientes llamadas a la función. Tengo dos preguntas:

  1. ¿GHC realmente hace este tipo de optimización?
  2. Si lo hace, ¿cuál es el comportamiento en el caso en que es más barato repetir el cálculo que buscar los resultados?

Gracias.

+0

Dudo que necesites una "tabla hash gigante" a menos que desees optimizar situaciones donde dos variables independientes suceden dos tienen los mismos valores, pero eso no vale la pena el esfuerzo e incluso menos útil por el hecho de que los argumentos de función ganaron t se evaluará completamente con frecuencia (es decir, no se puede comprobar si son realmente iguales, al menos no sin desperdiciar ese precioso tiempo de cálculo que desea usar). – delnan

+1

Vea esto not-a-faq http://stackoverflow.com/questions/5898162/what-is-the-lifetime-of-a-memoized-value-in-a-functional-language-like-haskell –

Respuesta

16

GHC no funciona automáticamente memoization. Consulte las preguntas frecuentes de GHC en Common Subexpression Elimination (no es exactamente lo mismo, pero creo que el razonamiento es el mismo) y la respuesta a this question.

Si quiere hacer memoizations usted mismo, entonces eche un vistazo a Data.MemoCombinators.

Otra forma de ver la memorización es utilizar la pereza para aprovechar las ventajas de la memorización. Por ejemplo, puede definir una lista en términos de sí mismo. La definición a continuación es una lista infinita de todos los números de Fibonacci (tomado de la Haskell Wiki)

fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

Debido a que la lista se realiza con pereza es similar a tener precalculados (memoized) los valores anteriores. p.ej. fibs !! 10 creará los primeros diez elementos para que fibs 11 sea mucho más rápido.

5

Guardar cada resultado de llamada de función (véase hash consing) es válido, pero puede ser una fuga de espacio gigante y, en general, también ralentiza mucho su programa. A menudo cuesta más verificar si tiene algo en la tabla que calcularlo realmente.

Cuestiones relacionadas