Warum verbraucht Haskells Funktion "nichts tun" id viel Speicher?

112

Haskell hat eine Identitätsfunktion, die die Eingabe unverändert zurückgibt. Die Definition ist einfach:

id :: a -> a
id x = x

Zum Spaß sollte dies also Folgendes ausgeben 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

Nach einigen Sekunden (und laut Task-Manager ca. 2 GB Speicher) schlägt die Kompilierung mit fehl ghc: out of memory. Ebenso sagt der Dolmetscher ghci: out of memory.

Da ides sich um eine ziemlich einfache Funktion handelt, würde ich nicht erwarten, dass sie zur Laufzeit oder zur Kompilierungszeit eine Speicherbelastung darstellt. Wofür wird der gesamte Speicher verwendet?

haskell ghc Ryan
quelle
11
Sie möchten diese ids komponieren . Führen Sie in VIM mit dem Cursor auf die Definition von fFolgendes aus : :s/id id/id . id ./g.
Tobias Brandt

Antworten:

135

Wir kennen die Art von id,

id :: a -> a

Und wenn wir uns darauf spezialisieren id id, hat die linke Kopie von id:

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

Und dann , wenn Sie diese spezialisieren wieder für die ganz links idin id id id, erhalten Sie:

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

Sie sehen also, dass bei jedem idHinzufügen die Typensignatur ganz links iddoppelt so groß ist.

Beachten Sie, dass Typen während der Kompilierung gelöscht werden, sodass nur Speicher in GHC belegt wird. Es nimmt keinen Speicherplatz in Ihrem Programm ein.

Dietrich Epp
quelle
Ich erinnere mich, dass Okasaki in ähnliche Schwierigkeiten geriet, als er einen in Haskell eingebetteten RPN-Rechner schrieb.
Feuer
3
Die Frage ist vielleicht, ob GHC einen Weg finden sollte, mit solchen Dingen eleganter umzugehen. Insbesondere ist der Typ sehr groß, wenn er vollständig ausgeschrieben ist, aber es gibt eine enorme Menge an Duplikaten - könnte das Teilen verwendet werden, um solche Dinge zu komprimieren? Gibt es eine effiziente Möglichkeit, sie zu verarbeiten?
Feuer
5
@dfeuer Fragen Sie nach dem Typ in ghci. An der Geschwindigkeit der Antwort erkennen Sie, dass die entsprechende Freigabe erfolgen muss. Ich vermute, dass diese Freigabe - aus offensichtlichen Gründen - verloren geht, wenn Sie in eine andere Zwischendarstellung (z. B. Kern) übersetzen.
Daniel Wagner
4
Dies bedeutet, dass bei idwiederholten Wiederholungen nder Raum seines Typs proportional zu ist 2^n. Der in Ryans Code abgeleitete Typ würde 2^27zusätzlich zu der anderen Struktur, die zur Darstellung des Typs erforderlich ist, Verweise auf seine Typvariable benötigen, die wahrscheinlich viel größer ist, als Sie es von den meisten Typen erwarten würden.
David
58
Die naive Typinferenz ist doppelt exponentiell. Wenn Sie die Typausdrücke geschickt verwenden, können Sie sie auf nur exponentiell reduzieren. Aber egal was Sie tun, es wird einige ziemlich einfache Ausdrücke geben, die die Typprüfung explodieren lassen. Glücklicherweise treten diese in der praktischen Programmierung nicht auf.
August