Perché la funzione "fa niente" di Haskell, id, consuma tonnellate di memoria?

Question

Haskell ha una funzione di identità che restituisce l'input invariato. La definizione è semplice:

id :: a -> a 
id x = x 

Così, per divertimento, questo dovrebbe uscita 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 

Dopo pochi secondi (e circa 2 GB di memoria secondo Task Manager), la compilazione fallisce con ghc: out of memory. Allo stesso modo, l'interprete dice ghci: out of memory.

Poiché id è una funzione piuttosto semplice, non mi aspetto che sia un carico di memoria in fase di esecuzione o in fase di compilazione. A cosa serve tutta la memoria?

Answer 1

Sappiamo che il tipo di id,

id :: a -> a 

E quando specializzati questo per id id, il lasciato copia di id è digitare:

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

E poi, quando vi specializzate di nuovo per il più a sinistra id in id id id, si ottiene:

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

Così vedete ogni id aggiunto, la firma del tipo più a sinistra dello id è due volte più grande.

Nota che i tipi vengono cancellati durante la compilazione, quindi questo occuperà solo memoria in GHC. Non occuperà memoria nel tuo programma.