Wann ist Memo automatisch in GHC Haskell?

Question

Ich kann nicht herausfinden, warum m1 offenbar memoized während m2 nicht in der folgenden ist:

m1  = ((filter odd [1..]) !!) 

m2 n = ((filter odd [1..]) !! n) 

m1 10000000 etwa 1,5 Sekunden auf dem ersten Anruf entgegennimmt, und einen Bruchteil der bei nachfolgenden Aufrufen (vermutlich es speichert die Liste), während m2 10000000 immer die gleiche Zeit benötigt (Neuaufbau der Liste bei jedem Aufruf). Irgendeine Idee was ist los? Gibt es Faustregeln darüber, ob und wann GHC eine Funktion memoziert? Vielen Dank.

Answer 1

GHC speichert keine Funktionen.

Es berechnet jedoch jeden gegebenen Ausdruck im Code höchstens einmal pro Zeit, dass sein umgebender Lambda-Ausdruck eingegeben wird, oder höchstens einmal, wenn es auf oberster Ebene ist. Bestimmen, wo die Lambda-Ausdrücke sind, kann ein wenig schwierig sein, wenn Sie syntaktischen Zucker verwenden wie in Ihrem Beispiel, also lassen Sie sich wandeln diese in äquivalenter entzuckert Syntax:

m1' = (!!) (filter odd [1..])    -- NB: See below! 
m2' = \n -> (!!) (filter odd [1..]) n 

(Hinweis: Der Bericht Haskell 98 beschreibt tatsächlich einen linken Operator Abschnitt wie (a %) gleich \b -> (%) a b, aber GHC desugars es (%) a. diese technisch unterschiedlich sind, weil sie von seq unterschieden werden können. ich glaube, ich könnte eine GHC Trac Ticket über diese Erklärungen abgegeben haben.)

dies gegeben, können Sie sehe, dass in m1' der Ausdruck filter odd [1..] nicht enthalten ist i n jeder Lambda-Ausdruck, so wird er nur einmal pro Lauf des Programms berechnet, während in m2', jedes Mal berechnet wird, wenn der Lambda-Ausdruck eingegeben wird, d. h. bei jedem Aufruf von m2'. Das erklärt den Zeitunterschied, den Sie sehen.

Tatsächlich teilen einige Versionen von GHC mit bestimmten Optimierungsoptionen mehr Werte als die obige Beschreibung angibt. Dies kann in manchen Situationen problematisch sein. Betrachten wir zum Beispiel die Funktion

f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x]) 

GHC könnte feststellen, dass y nicht auf x abhängt und schreiben Sie die Funktion

f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x]) 

In diesem Fall ist die neue Version viel weniger effizient, weil es haben um ungefähr 1 GB aus dem Speicher zu lesen, wo y gespeichert ist, während die ursprüngliche Version in konstantem Raum laufen und in den Cache des Prozessors passen würde. Tatsächlich ist die Funktion f unter GHC 6.12.1 fast doppelt so schnell, wenn ohne Optimierungen kompiliert wird, als es mit -O2 kompiliert wird.

Answer 2

m1 wird nur einmal berechnet, da es sich um eine konstante Anwendungsform handelt, während m2 keine CAF ist und daher für jede Auswertung berechnet wird.

Siehe GHC Wiki auf CAFs: http://www.haskell.org/haskellwiki/Constant_applicative_form

Answer 3

Es gibt einen entscheidenden Unterschied zwischen den beiden Formen: die Monomorphie Beschränkung auf m1 gilt aber nicht m2, weil m2 Argumente explizit gegeben hat. Der Typ von m2 ist also allgemein, aber m1 ist spezifisch.Die Typen sie zugeordnet sind:

m1 :: Int -> Integer 
m2 :: (Integral a) => Int -> a 

meist Haskell Compiler und Interpreter (alle von ihnen, dass ich eigentlich wissen) nicht polymorphen Strukturen memoize, so m2 interne Liste jedes Mal neu erstellt wird es genannt wird, wobei m1 die nicht .

Answer 4

Ich bin nicht sicher, weil ich Haskell ziemlich neu bin, aber es scheint, dass es ist, dass die zweite Funktion parametrisiert ist und die erste nicht ist. Die Natur der Funktion ist, dass das Ergebnis vom Eingabewert und im funktionalen Paradigma abhängt, insbesondere hängt es nur von der Eingabe ab. Offensichtliche Implikation ist, dass eine Funktion ohne Parameter immer und immer wieder den gleichen Wert zurückgibt, egal was passiert.

Aparently gibt es einen Optimierungsmechanismus im GHC-Compiler, der diese Tatsache nutzt, um den Wert einer solchen Funktion nur einmal für die gesamte Programmlaufzeit zu berechnen. Es macht es zwar ruhig, tut es aber trotzdem. Ich bemerkte es mich, wenn ich die folgende Funktion geschrieben:

primes = filter isPrime [2..] 
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n] 
     where f `divides` n = (n `mod` f) == 0 

Dann ist es zu testen, ich eintrat GHCI und schrieb: primes !! 1000. Es dauerte ein paar Sekunden, aber schließlich bekam ich die Antwort: 7927. Dann rief ich primes !! 1001 an und bekam sofort die Antwort. Gleichermaßen bekam ich in einem Augenblick das Ergebnis für take 1000 primes, weil Haskell die gesamte tausendelementige Liste berechnen musste, um das 1001ste Element vorher zurückzugeben.

Also, wenn Sie Ihre Funktion so schreiben können, dass es keine Parameter braucht, wollen Sie es wahrscheinlich. ;)