optimization - tuplas - listas infinitas haskell

Optimización de llamadas a funciones en Haskell

Question

No estoy seguro de qué buscar exactamente en Google para esta pregunta, así que lo publicaré directamente en SO:

1. Las variables en Haskell son inmutables.
2. Las funciones puras deberían dar como resultado los mismos valores para los mismos argumentos.

A partir de estos dos puntos, es posible deducir que si llama somePureFunc somevar1 somevar2 en su código, solo tiene sentido calcular el valor durante 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 de que en realidad es más barato repetir el cálculo que buscar los resultados?

Gracias.

Answer 1

GHC no hace la memoization automática. Consulte las preguntas frecuentes de GHC sobre la eliminación de la subexpresión común (no es exactamente lo mismo, pero supongo que el razonamiento es el mismo) y la respuesta a esta pregunta .

Si desea realizar una memoización usted mismo, entonces eche un vistazo a Data.MemoCombinators .

Otra forma de ver la memoización es usar la pereza para aprovechar la memoización. Por ejemplo, puede definir una lista en términos de sí misma. La siguiente definición es una lista infinita de todos los números de Fibonacci (tomada de la Wiki de Haskell )

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

Debido a que la lista se realiza perezosamente, es similar a tener valores previos precomputados (memorizados). por ejemplo, fibs !! 10 fibs !! 10 creará los primeros diez elementos de modo que fibs 11 sea ​​mucho más rápido.

Answer 2

Guardar el resultado de cada llamada de función (cf. 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 comprobar si tiene algo en la tabla que realmente calcularlo.