Gebunden die Laufzeit einer Berechnung in Haskell

Question

Ich schreibe eine Spiel-AI in Haskell, und ich möchte den Spielstatusbaum für eine bestimmte Zeit suchen (dh ich möchte immer AI 3 Sekunden dauern, um es zu machen Entscheidung darüber, welche Bewegung zu machen)

Wie kann ich das in einer reinen Sprache wie Haskell tun? Ich erwarte, dass ich etwas in Threads und ähnliches tauchen muss, aber ich würde es vorziehen, das so weit wie möglich zu minimieren.

Answer 1

Eine Idee: Kombinieren Sie timeout (vorgeschlagen von @MathematicalOrchid) mit änderbaren Variablen aus SafeSemaphore Zwischenwert zu speichern, jedes Mal, wenn Ihr Prozess ein Teilergebnis berechnet:

import Control.Monad 
import Control.Concurrent.MSampleVar 
import System.Timeout 

fac :: Integer -> Integer 
fac 0 = 1 
fac n = n * fac (n - 1) 

tmo :: Int -> ((a -> IO()) -> IO()) -> IO (Maybe a) 
tmo ms f = do 
    mvar <- newSV Nothing 
    timeout ms (f (writeSV mvar . (Just $!))) 
    readSV mvar 

longComp :: (Integer -> IO()) -> IO() 
longComp save = let loop n = save (fac n) >> loop (n + 1) 
       in loop 0 

main :: IO() 
main = tmo 10000 longComp >>= print 

Die Funktion tmo wird als erstes Argument übergeben eine IO Aktion, mit der Zwischenergebnisse gespeichert werden können. Wenn es eine Zeitüberschreitung erhält, wird das letzte gespeicherte Ergebnis zurückgegeben. Das Ergebnis wird in WHNF konvertiert, sodass die tatsächliche Berechnung in dem Thread erfolgt, der das Ergebnis speichert, und nicht in dem Prozess, der es verarbeitet, wenn es von tmo zurückgegeben wird.

In dieser Variante muss die an tmo übergebene Funktion ihre Ausgabe speichern, sie kann sie nicht zurückgeben. Aber es wäre einfach, es zu ändern, so dass seine Signatur (a -> IO()) -> IO a wäre.

Wenn Sie die Dinge reiner halten wollen, würde ich vorschlagen, Ihre eigene Monade zu erstellen, die diese Idee kapselt, ohne IO herauszulassen.

---

Update: Beachten Sie, dass:

Es gibt keine Garantie dafür, dass die Ausnahme sofort ausgeliefert werden, obwohl die Laufzeit zu gewährleisten, wird sich bemühen, dass willkürliche Verzögerungen nicht auftreten.In GHC kann eine Ausnahme nur ausgelöst werden, wenn ein Thread einen sicheren Punkt erreicht, wo ein sicherer Punkt ist wo Speicherzuweisung auftritt. Einige Schleifen nicht führen keine Speicherzuweisung innerhalb der Schleife und daher kann nicht durch eine throwTo unterbrochen werden.

(aus der Dokumentation von throwTo). Im obigen Beispiel belegt fac keinen Speicher und wird daher bei großen Nummern nicht sofort unterbrochen.

Update: Ich habe eine kleine Bibliothek basierend auf diesen Ideen erstellt, die Monaden für Berechnungen definiert, die Teilergebnisse zurückgeben können, bevor die letzte zurückgegeben wird oder bei einer Zeitüberschreitung. Siehe https://github.com/ppetr/timeout-with-results

Answer 2

Da das Ergebnis, das Sie suchen, von der Zeit abhängt, wird dies zwangsläufig unreinen Code enthalten.

Es ist wie System.Timeout aus dem base Paket sieht bietet die Möglichkeit, eine E/A-Berechnung bis einigen Timeout laufen (pro dem Kommentar von leftaroundabout.) Also alles, was Sie tun müssen, ist eine IO Berechnung schreiben, die das gewünschte Ergebnis liefert‘ Re interessiert. Aber ... der schwierige Teil ist die IO Aktion tatsächlich compute das Ergebnis, nicht nur ein unevaluiertes Ergebnis zurückgeben. Dafür denken Sie Sie brauchen evaluate von Control.Exception.

Answer 3

System.Timeout ist der Weg zu gehen. Es hat eine sehr saubere Schnittstelle, die sich überhaupt nicht anfühlt, als würden Sie mit Threads herumspielen.

das Spiel Raum Suche klingt wie eine reine Berechnung und System.Timeout läuft IO Aktionen, so dass Sie den Wert in return, wickeln müssen und den Code streng genug zu bewerten, dass timeout nicht sofort eine Antwort glauben zurückgegeben wurde sobald es nach WHNF bewertet wurde.

Es gibt ein Beispiel here von dem, wie der Code von einem ähnlichen Problem aussehen könnte, das ich hatte.