Wie kann man das Zurückverfolgen in Scala stoppen?

Während Scala Option hier arbeiten wird, wie zwei andere Antworten darauf hingewiesen haben, wäre ein idiomatischerer funktioneller Ansatz, eine "faule Liste" zu verwenden - oder eine Stream , in Scala - um die Menge der Lösungen darzustellen.

Ich habe selbst Code geschrieben, zum Beispiel:

Nun nehme ich an, dass ich eine Board -Klasse habe, die Node[Board] erweitert und eine Implementierung der children -Methode hat, die alle gültigen Boards mit einem zusätzlichen Stück zurückgibt. Angenommen, es hat auch andere nützliche Dinge, wie eine size -Methode, ein Begleitobjekt mit empty , etc.

Ich kann dann Folgendes schreiben, um ein Stream der Lösungen zu erhalten:

A Stream ist faul und wertet nur seinen Kopf aus, also haben wir gerade erst den Baum weit genug durchsucht, um die erste Lösung zu finden. Wir können diese Lösung mit head erhalten:

Oder was auch immer. Aber ich kann auch andere Ergebnisse bekommen, wenn ich sie will:

Dies durchsucht gerade genug des Baums, um die zehnte Lösung zu finden, und stoppt dann.

Der große Vorteil von Stream gegenüber dem Option Ansatz ist, dass ich zusätzliche Ergebnisse erzielen kann, wenn ich sie brauche, ohne dafür mehr zu bezahlen.

Hier ist ein einfacher Fall mit einer Tiefensuche, die stoppt, wenn sie findet, wonach sie sucht. Es verwendet Option , wie in Chris Ks Antwort erwähnt.

Verwendung:

Der Baum t sieht wie

So können wir nach einem Element suchen und die Knoten, die es besucht, verfolgen:

Beachten Sie, dass wir keine weiteren Knoten mehr besuchen, nachdem wir gefunden haben, wonach wir suchen.

Unter der Annahme, dass Sie eine rekursive Suchfunktion verwenden, sollte Ihre Funktion entweder ein Ergebnis (d. h. Positionierung der Königinnen) oder einen Hinweis, dass für diesen Zweig kein Ergebnis gefunden wurde, zurückgeben. Scala hat wahrscheinlich eine Option / vielleicht Typ, die Sie verwenden können. Dieser Hinweis gilt gleichermaßen für jede funktionale Sprache.