Dlaczego funkcja Haskella "nie rób nic", id, zużywa ton pamięci?

Question

Haskell ma funkcję identyfikacji, która zwraca dane wejściowe bez zmian. Definicja jest prosta:

id :: a -> a 
id x = x 

Tak dla zabawy, to powinien wypisać 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 

Po kilku sekundach (i około 2 GB pamięci według Task Manager), kompilacja nie powiedzie się z ghc: out of memory. Podobnie, tłumacz mówi: ghci: out of memory.

Od id jest dość prosta funkcja, nie spodziewam się, że jest to obciążenie pamięci w czasie wykonywania lub czas kompilacji. Do czego służy cała pamięć?

Answer 1

Wiemy typ id,

id :: a -> a 

A kiedy specjalizujemy to dla id id The lewo kopię id ma typ:

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

a kiedy specjalizują się to ponownie dla najbardziej po lewej id w id id id, otrzymasz:

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

Widzisz więc każdy dodany id, podpis typu z lewej strony id jest dwa razy większy.

Należy pamiętać, że typy są usuwane podczas kompilacji, więc zajmie to tylko pamięć w GHC. Nie zajmie pamięci w twoim programie.