online - haskell core download

¿Por qué la función "no hacer nada" de Haskell, id, consume toneladas de memoria?

Question

Haskell tiene una función de identidad que devuelve la entrada sin cambios. La definición es simple:

id :: a -> a
id x = x

Así que para divertirse, esto debería producir 8 :

f = id id id id id id id id id id id id id id id id id id id id id id id id id id id
main = print $ f 8

Después de unos segundos (y aproximadamente 2 gb de memoria según Task Manager), la compilación falla con ghc: out of memory . Del mismo modo, el intérprete dice ghci: out of memory .

Como id es una función bastante simple, no esperaría que fuera una carga de memoria en tiempo de ejecución o de compilación. ¿Para qué se usa todo el recuerdo?

Answer 1

Conocemos el tipo de id ,

id :: a -> a

Y cuando nos especializamos para id id , la copia izquierda de id tiene tipo:

id :: (a -> a) -> (a -> a)

Y luego, cuando lo vuelves a especializar para la id situada más a la izquierda en id id id , obtienes:

id :: ((a -> a) -> (a -> a)) -> ((a -> a) -> (a -> a))

Para que vea cada id que agrega, la firma de tipo de la id de la izquierda es el doble de grande.

Tenga en cuenta que los tipos se eliminan durante la compilación, por lo que esto solo ocupará la memoria en GHC. No ocupará memoria en su programa.