tuplas - Definición de función Haskell y matrices de almacenamiento en caché

multiplicar haskell

Question

Tengo una pregunta acerca de cómo implementar el almacenamiento en caché (memorización) usando matrices en Haskell. El siguiente patrón funciona:

f = (fA !)
  where fA = listArray...

Pero esto no es así (la velocidad del programa sugiere que la matriz se está recreando en cada llamada o algo así):

f n = (fA ! n)
  where fA = listArray...

La definición de fA fuera de una cláusula where (en "alcance global") también funciona con cualquiera de los patrones.

Tenía la esperanza de que alguien pudiera indicarme una explicación técnica de cuál es la diferencia entre los dos patrones anteriores.

Tenga en cuenta que estoy usando el último GHC, y no estoy seguro si esto es solo una peculiaridad del compilador o parte del lenguaje en sí.

EDITAR:! se utiliza para el acceso a la matriz, entonces fA! 5 significa fA [5] en sintaxis de C ++. Mi comprensión de Haskell es que (fA!) N sería lo mismo que (fA! N) ... también hubiera sido más convencional para mí haber escrito "fn = fA! N" (sin los paréntesis). De todos modos, obtengo el mismo comportamiento sin importar cómo hago entre paréntesis.

Answer 1

Genial, gracias por tus respuestas, que me ayudaron mucho, y definitivamente revisaré los memominadores de datos en Hackage. Viniendo de un trasfondo pesado en C ++, he estado luchando por comprender exactamente qué hará Haskell (principalmente en términos de complejidad) con un programa determinado, que los tutoriales parecen no tener.

Answer 2

La diferencia de comportamiento no está especificada por el estándar Haskell. Todo lo que tiene que decir es que las funciones son las mismas (dará como resultado el mismo resultado con la misma entrada).

Sin embargo, en este caso, hay una manera simple de predecir el rendimiento de tiempo y memoria que la mayoría de los compiladores cumplen. Insisto en que esto no es esencial, solo que la mayoría de los compiladores lo hacen.

Primero reescriba sus dos ejemplos como expresiones lambda puras, expandiendo la sección:

f = let fA = listArray ... in /n -> fA ! n
f'' = /n -> let fA = listArray ... in fA ! n

Los compiladores usan el enlace para indicar el uso compartido. La garantía es que en un entorno dado (conjunto de variables locales, cuerpo lambda, algo así), el lado derecho de un enlace let sin parámetros se evaluará a lo sumo una vez. El entorno de fA en el primero es el programa completo, ya que no está bajo ninguna lambda, pero el entorno de este último es más pequeño ya que está bajo una lambda.

Lo que esto significa es que en este último, fA puede evaluarse una vez para cada n diferente, mientras que en el primero esto está prohibido.

Podemos ver este patrón en efecto incluso con funciones de múltiples argumentos:

g x y = (a ! y) where a = [ x ^ y'' | y'' <- [0..] ]
g'' x = (/y -> a ! y) where a = [ x ^ y'' | y'' <- [0..] ]

Luego en:

let k = g 2 in k 100 + k 100

Podríamos calcular 2 ^ 100 más de una vez, pero en:

let k = g'' 2 in k 100 + k 100

Solo lo calcularemos una vez.

Si está trabajando con memoria, recomiendo datacombinators en Hackage, que es una biblioteca de tablas memo de diferentes formas, por lo que no tiene que hacer las suyas.

Answer 3

La mejor forma de encontrar lo que sucede es decirle al compilador que muestre su representación intermedia con -v4 . El resultado es voluminoso y un poco difícil de leer, pero debería permitirle saber exactamente cuál es la diferencia en el código generado y cómo llegó el compilador allí.

Probablemente notará que fA se está moviendo fuera de la función (al "alcance global") en su primer ejemplo. En su segundo ejemplo, probablemente no lo es (lo que significa que se recreará en cada llamada).

Una razón posible para que no se mueva fuera de la función sería porque el compilador está pensando que depende del valor de n . En su ejemplo de trabajo, no hay n para que fA dependa de.

Pero la razón por la que creo que el compilador está evitando mover fA afuera en su segundo ejemplo es porque está tratando de evitar una fuga de espacio. Considera lo que sucedería si fA , en lugar de tu matriz, fuera una lista infinita (en la que usaste el operador !! ). Imagine que lo llamó una vez con un número grande (por ejemplo, f 10000 ), y luego solo lo llamó con números pequeños ( f 2 , f 3 , f 12 ...). Los 10000 elementos de la llamada anterior todavía están en la memoria, desperdiciando espacio. Entonces, para evitar esto, el compilador crea fA nuevamente cada vez que llame a su función.

La fuga de espacio probablemente no suceda en su primer ejemplo porque en ese caso f solo se llama una vez, devolviendo un cierre (ahora estamos en la frontera de los mundos puros funcionales y los imperativos, entonces las cosas se vuelven un poco más sutiles ) Este cierre reemplaza la función original, que nunca volverá a llamarse, por lo que fA solo se llama una vez (y por lo tanto, el optimizador se siente libre de moverlo fuera de la función). En su segundo ejemplo, f no se reemplaza por un cierre (ya que su valor depende del argumento) y, por lo tanto, se volverá a llamar.

Si quieres entender más sobre esto (lo que te ayudará a leer la salida -v4 ), puedes echarle un vistazo al papel Spineless Tagless G-Machine ( enlace de citadores ).

En cuanto a su pregunta final, creo que es una peculiaridad del compilador (pero podría estar equivocado). Sin embargo, no me sorprendería si todos los compiladores hicieran lo mismo, incluso si no fuera parte del lenguaje.