Pourquoi Haskell ' fonction de « statu quo » s, id, consommer des tonnes de mémoire ?

Question

Haskell a une identité de fonction qui renvoie l'entrée inchangé. La définition est simple:

id :: a -> a
id x = x

Donc, pour s'amuser, cette sortie devrait 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

Après quelques secondes (et de 2 go de mémoire selon le Gestionnaire des Tâches), la compilation échoue avec l' ghc: out of memory. De même, l'interprète, dit - ghci: out of memory.

Depuis id est assez simple fonction, je ne serais pas s'attendre à une mémoire de charge au moment de l'exécution ou de la compilation. Qu'est-ce que la mémoire utilisée?

Answer 1

Nous connaissons le type d' id,

id :: a -> a

Et quand nous nous spécialisons ce pour id id, la gauche de la copie de l' id a type:

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

Et puis, quand vous vous spécialisez ce nouveau pour la gauche id en id id id, vous obtenez:

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

Donc, vous voyez chaque id vous ajoutez, le type de signature de la gauche id est deux fois plus grand.

Notez que les types sont supprimés lors de la compilation, donc cela ne fera que prendre de la mémoire dans GHC. Il ne prendra pas la mémoire de votre programme.