Haskell ma funkcję tożsamości, która zwraca dane wejściowe w niezmienionej postaci. Definicja jest prosta:
id :: a -> a
id x = x
Więc dla zabawy powinno to dać 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 Menedżera zadań) kompilacja kończy się niepowodzeniem ghc: out of memory
. Podobnie mówi tłumacz ghci: out of memory
.
Ponieważ id
jest to dość prosta funkcja, nie spodziewałbym się, że będzie obciążała pamięć w czasie wykonywania lub kompilacji. Do czego służy cała pamięć?
id
pliki. W VIM, z kursorem w sprawie definicjif
, to zrobić::s/id id/id . id ./g
.Odpowiedzi:
Znamy rodzaj
id
,A kiedy specjalizujemy się w tym
id id
, lewa kopiaid
ma typ:A potem, kiedy to specjalizują się ponownie do najbardziej na lewo
id
wid id id
, można uzyskać:Widzisz więc, że każdy
id
dodajesz, podpis typu skrajnego lewegoid
jest dwukrotnie większy.Pamiętaj, że typy są usuwane podczas kompilacji, więc zajmie to tylko pamięć w GHC. Nie zajmie pamięci w twoim programie.
źródło
id
jest powtarzanen
razy, przestrzeń tego typu jest proporcjonalna do2^n
. Typ wywnioskowany w kodzie Ryana wymagałby2^27
odniesień do jego zmiennej typu oprócz innej struktury potrzebnej do reprezentowania typu, która jest prawdopodobnie znacznie większa niż można by się spodziewać po większości typów.