Haskell: teilweise faul ausgewertete Ergebnisse

Question

Ich habe einen sehr großen Entscheidungsbaum. Es wird wie folgt verwendet:

-- once per application start 
t :: Tree 
t = buildDecisionTree 
-- done several times 
makeDecision :: Something -> Decision 
makeDecision something = search t something 

Dieser Entscheidungsbaum ist viel zu groß, um in den Speicher zu passen. Aber dank der faulen Bewertung wird es nur teilweise ausgewertet.

Das Problem ist, dass es Szenarien gibt, in denen alle möglichen Entscheidungen versucht werden, wodurch der gesamte Baum evaluiert wird. Dies wird nicht beendet, sollte aber auch keinen Speicherüberlauf verursachen. Wenn dieser Prozess abgebrochen wird, nimmt die Speichernutzung nicht ab, da ein großer Teilbaum noch immer ausgewertet wird.

Eine Lösung wäre, den Baum jedes Mal neu zu bewerten, wenn makeDecision aufgerufen wird, aber dies würde die Vorteile von Caching-Entscheidungen verlieren und makeDecision erheblich verlangsamen.

Ich möchte einen Mittelweg gehen. Insbesondere ist es in meiner Anwendung sehr üblich, aufeinanderfolgende Entscheidungen mit einem gemeinsamen Pfadpräfix im Baum zu treffen. Also möchte ich den letzten benutzten Pfad zwischenspeichern, aber die anderen fallenlassen, was dazu führt, dass sie das nächste Mal, wenn sie benutzt werden, neu bewerten. Wie kann ich das in Haskell machen?

Answer 1

Es ist in reinem Haskell nicht möglich, siehe Frage Can a thunk be duplicated to improve memory performance? (wie von @shang hervorgehoben). Sie können dies jedoch mit IO tun.

Wir beginnen mit dem Modul heade und listen nur den Typ und die Funktionen auf, die dieses Modul (welches unsafePerformIO verwendet) sicher machen sollte. Es ist auch möglich, dies ohne unsafePerformIO zu tun, aber das würde bedeuten, dass der Benutzer mehr von seinem Code in IO behalten muss.

{-# LANGUAGE ExistentialQuantification #-} 
module ReEval (ReEval, newReEval, readReEval, resetReEval) where 

import Data.IORef 
import System.IO.Unsafe 

Wir beginnen mit einem Datentyp definieren, der einen Wert in eine Art und Weise gespeichert werden, die alle Sharing verhindert, indem die Funktion zu halten und das Argument voneinander entfernt, und nur die Funktion anwenden, wenn wir den Wert wollen. Beachten Sie, dass der von unsharedValuezurückgegebene Wert geteilt sein kann, aber nicht mit dem Rückgabewert von anderen Anrufungen (die Funktion unter der Annahme etwas nicht-trivial zu tun)

data Unshared a = forall b. Unshared (b -> a) b 

unsharedValue :: Unshared a -> a 
unsharedValue (Unshared f x) = f x 

Nun definieren wir unseren Datentyp rücksetzbaren Berechnungen . Wir müssen die Berechnung und den aktuellen Wert speichern. Letzteres ist in einem IORef gespeichert, wie wir es zurücksetzen möchten.

data ReEval a = ReEval { 
    calculation :: Unshared a, 
    currentValue :: IORef a 
    } 

Um einen Wert in einem ReEval Feld wickeln, müssen wir eine Funktion und ein Argument haben. Warum nicht einfach a -> ReEval a? Denn dann wäre es nicht möglich zu verhindern, dass der Parameter geteilt wird.

newReEval :: (b -> a) -> b -> ReEval a 
newReEval f x = unsafePerformIO $ do 
    let c = Unshared f x 
    ref <- newIORef (unsharedValue c) 
    return $ ReEval c ref 

Lesen ist einfach: den Wert aus dem IORef erhalten. Diese Verwendung von unsafePerformIO ist sicher, weil wir immer den Wert von unsharedValue c erhalten, obwohl eine andere "Kopie" davon.

readReEval :: ReEval a -> a 
readReEval r = unsafePerformIO $ readIORef (currentValue r) 

Und schließlich das Zurücksetzen. Ich habe es in der IO-Monade verlassen, nicht weil es weniger sicher wäre als die andere Funktion in unsafePerformIO gewickelt zu werden, aber weil dies der einfachste Weg ist, dem Benutzer die Kontrolle über zu geben, wenn das Zurücksetzen tatsächlich passiert.Sie möchten nicht riskieren, dass alle Ihre Anrufe zu resetReEval verzögert verzögert werden, bis Ihr Speicher abgelaufen ist oder sogar weg optimiert, da es keinen Rückgabewert zu verwenden gibt.

resetReEval :: ReEval a -> IO() 
resetReEval r = writeIORef (currentValue r) (unsharedValue (calculation r)) 

Dies ist das Ende des Moduls. Es folgt ein Beispielcode:

import Debug.Trace 
import ReEval 
main = do 
    let func a = trace ("func " ++ show a) negate a 
    let l = [ newReEval func n | n <- [1..5] ] 
    print (map readReEval l) 
    print (map readReEval l) 
    mapM_ resetReEval l 
    print (map readReEval l) 

Und hier kann man sehen, dass es das tut, was zu erwarten:

$ runhaskell test.hs 
func 1 
func 2 
func 3 
func 4 
func 5 
[-1,-2,-3,-4,-5] 
[-1,-2,-3,-4,-5] 
func 1 
func 2 
func 3 
func 4 
func 5 
[-1,-2,-3,-4,-5]