Ich implementiere ein Tic-Tac-Toe-Spiel für n * n board in Haskell und ich muss alle Board-Konfigurationen generieren, die ich vom nächsten Zug bekomme.
Ich habe Board wie folgt definiert:
%Vor% Ich kann feststellen, ob die gegebene Board-Konfiguration für Spieler x gewinnt, also habe ich
Aber ich habe keine Ahnung, wie man alle Board-Konfigurationen generiert, die der Spieler x als nächsten Zug machen kann.
Ich verstehe, dass ich alle Zellen durchlaufen muss und überprüfe, ob die Zelle leer ist, dann kann ich hier eine Markierung setzen und eine neue Konfiguration zurückgeben. Wenn ich bereits die Konfiguration gewinne, dann gibt es keine nächste Bewegung, und ich muss eine leere Liste zurückgeben
Ich habe einen Code wie folgt:
%Vor%Wie kann ich das tun, indem ich list monad benutze? Danke für die Hilfe!
mit
%Vor%(Dies ist eine optimierte Version von this ), alle möglichen nächsten Boards sind
%Vor% wobei who eine von X oder O ist, oder natürlich.
Dies ist nichts anderes als ein Filter, um das Leergut zu behalten, und eine Karte über diejenigen, die gleichzeitig gefiltert wurden. Es ist noch einfacher mit List Comprehensions,
%Vor% Die Funktion picks wählt alle möglichen Zellen nacheinander in den verketteten Zeilen aus, wobei auch ein Präfix und ein Suffix beibehalten werden. chunksOf n baut die Karte aus einer langen Reihe von Zellen in Blöcken von n -Zellen in einer Reihe neu auf. Der Gesamteffekt ist also eine Liste aller möglichen Boards, in denen E durch who ersetzt wurde.
Effizienter picks würde seine Präfixe ( sy ) in umgekehrter Reihenfolge erstellen; Erstellen einer Liste von sogenannten "Reißverschlüssen". Beim Wiederaufbau müssten sie entsprechend umgekehrt werden.
edit: Wie das Listenverständnis zeigt, könnte es in erster Linie mit do notation geschrieben worden sein:
%Vor% In do notization wird ein Musterkonflikt in einen Aufruf von fail übersetzt, was in list monad dazu führt, dass ein Element übersprungen wird, während die Berechnung als Ganzes ohne Fehler fortgesetzt wird.
edit2: Ein Data.List -basierter Code, der es in einem Durchlauf über die Eingabe macht, ist
Danke an גגעד בבקן für die Diskussion.
Wenn wir uns die Typ-Signatur für >>= ansehen, sehen wir, dass es
Wenn Sie Ihre nxt -Funktion "verketten" möchten, muss die gesamte Typ-Signatur für die Bindung lauten:
Damit nxt den Typ Board -> [Board] haben muss. Jetzt müssen wir uns fragen, was genau nxt macht: Es braucht ein Board und gibt alle möglichen Züge vom aktuellen Board zurück. Zufälligerweise ist der Typ für nxt genau das, was >>= benötigt: Board -> [Board] . Aber warte. Woher wissen wir, wer an der Reihe ist? Wie Sie es bereits getan haben, können wir die aktuelle Markierung als Parameter übergeben, aber dies ändert auch die Typensignatur: Cell -> Board -> [Board] . Können wir diese Funktion noch verketten? Ja, das können wir. Mit partieller Anwendung können wir bereits den nächsten Marker platzieren, indem wir ihn bereits übergeben und dann die resultierende Funktion binden:
Jetzt müssen wir nur noch jedes Feld durchlaufen und prüfen, ob es leer ist. Wenn es so ist, ersetzen wir es durch unsere Markierung und durchqueren die anderen Felder. :
%Vor%Jetzt können Sie Moves wie folgt ketten:
%Vor%Ich würde empfehlen, die Simulationsfunktion und die tatsächliche Bewegungserfassungsfunktion für größere Verwendungszwecke zu trennen. So könntest du beispielsweise einfach eine Funktion schreiben, die alle Boards zurückgibt, die für eine bestimmte Größe und einen bestimmten Spieler gewinnen:
%Vor%Ich überlasse es Ihnen, den Spielteil als Übung zu implementieren.
Die anderen Antworten deckten die einfachen Lösungen ab. Hier stelle ich eine lens Lösung vor, da sie für die Aufgabe gut geeignet ist.
Mit lens können wir die folgenden zwei Dinge separat spezifizieren:
Wir möchten auf die leeren Zellen des Boards als Ziele hinweisen. Traversal' Board Cell gibt an, dass die Gesamtdatenstruktur den Typ Board hat, während die Ziele den Typ Cell aufweisen.
Jetzt können wir eine Vielzahl von Operationen mit emptyCells durchführen.
Wir können auch next mit emptyCells und der holesOf Funktion sauber implementieren. holesOf emptyCells gibt eine Liste von "Löchern" des Boards zurück. Jedes Loch enthält im Wesentlichen ein Cell und eine Funktion, die ein Cell Argument übernimmt und ein neues Board mit dem gelieferten Cell in eine bestimmte Position zurückgibt.
Leider sind die Löcher eher abstrakt implementiert, und holesOf emptyCells hat einen uninformativen Board ->[Control.Lens.Internal.Context.Pretext (->) Cell Cell Board] -Typ. Wir sollten uns daran erinnern, dass Control.Comonad.Store eine Schnittstelle zum Arbeiten mit Löchern bietet. pos gibt das Fokuselement eines Lochs zurück (hier ist es ein Cell ), während peek ein neues Element in das Loch einfügt und die resultierende Datenstruktur zurückgibt.
Für nxt x board müssen wir x an jeder Stelle mit einer leeren Zelle verbinden. In diesem Sinne wird nxt einfach zu: