Suche Algorithmus zur Suche nach Argument zur Erfüllung der angegebenen Funktion

Question

Ich habe dieses spezielle Problem, für das ich noch keine Lösung haben. Ich denke, es würde helfen, wenn ich weiß, dass es einen verwandten Algorithmus gibt.

Der Algorithmus, den ich suche, ist einer, der hilft, ein Argument zu finden, das ein Ziel erfüllt, das von einer Funktion zurückgegeben wird.

Zum Beispiel a works for b wird bezeichnet als (a,b)

Given: [ (a,b); (b,c) ] 

Funktion works ihre Beziehung mit Boolesche Werte

let works a b -> true 
let works b c -> true 

Jetzt gegeben Ich versichere

[ (a, "x"); ("x", c) ] 

Wenn ich will, diese 2 Bindungen sind wahr, dann diese Funktion m ust wahr

let works a "x" -> true 
let works "x" c -> true 

Nun Ich versuche, eine Funktion/Algorithmus zu schreiben, die mir so zu erreichen "x" = b

hilft ich von denken Rückzieher, aber noch nicht wissen, wie es zu implementieren. Ich würde mich freuen, wenn mir jemand einen Hinweis geben könnte.

Als eine Randnotiz, implementiere ich den Algorithmus in F # mit funktionalen Programmierparadigma.

Answer 1

Sie haben richtig, dass Sie backward chaining brauchen und Jack ist richtig, dass Sie Unification brauchen, aber speziell brauchen Sie syntaktische Vereinheitlichung mit Rückwärtsverkettung.

Ihre Frage ist nicht neu, aber gründlicher beantwortet auf CS:StackExchange als How to implement a prolog interpreter in a purely functional language?

wurde Während dies Sie auf dem richtigen Weg stellen wird, auf die Probleme ab, die Sie lösen möchten, können Sie feststellen, dass dies nicht sein kann, so einfach wie es scheint.

EDIT

testete ich dein Beispiel auf einige F # Code arbeiten ich habe, und es funktioniert, aber ich kann an die Öffentlichkeit den Code nicht freigeben, sorry.

Für Ihr Beispiel kann es mit nur Vereinigung ohne Rückwärtsverkettung getan werden.

Sie müssen Fakten schaffen für

works(a,b). 
works(b,c). 

und einer Abfrage

works(a,X),works(X,c). 

mit der Antwort

sein

X = b 

Wenn Sie dies für mehr erweitern möchten als eine Person in der Mitte, dann müssen Sie Backwa verwenden Verkettung, weil Sie eine rekursive untergeordnete Regel erstellen müssen.

Sie müssen Fakten schaffen für

works(a,b). 
works(b,c). 
works(c,d). 

und Regeln

subordinate(X,Z) :- works(X,Z). 
subordinate(X,Z) :- works(X,Y), subordinate(Y,Z). 

und eine Abfrage

subordinate(a,X),subordinate(X,d). 

mit der Antwort

X = b,c 

sein 210

Sie werden auf haben die Typen, Vereinheitlichung und Rückwärtsverkettung Algorithmus erstellen. Sie können einen Parser und einen hübschen Drucker sowie eine Ebene auf einer REPL erstellen, dies wird jedoch nicht benötigt.

Die Fakten, Regeln und Abfragen sind zeigen in menschlicher Hinsicht, aber wenn Sie den Parser und ziemlich Drucker überspringen müssen Sie sie als AST codieren auf. h.

Die Großbuchstaben repräsentieren Prolog-Variablen. d.h. X Y Z
Die Kleinbuchstaben repräsentieren Prolog-Konstanten. Das funktioniert Problem ist nur eine Variation des klassischen Vorfahrenbeispiels. Siehe: Prolog/Recursive Rules

Answer 2

Der Algorithmus, den Sie beschreiben, ist Unification - es ist die Basis von Prolog, und es ist nicht schrecklich schwierig, in F # zu implementieren.

Ich würde empfehlen, die Handbook of Practical Logic and Automated Reasoning (Amazon, Safari Books) von John Harrison zu lesen; Abschnitt 3.9 behandelt den Vereinigungsalgorithmus. Zwei andere F # 'er und ich portierten den Code aus dem Buch zu F # letztes Jahr, wenn Sie einen Blick darauf werfen möchten: fsharp-logic-examples.

Ihre Beschreibung des Problems gegeben, könnten Sie wahrscheinlich mit einigen einfachen Constraint Logic Programming (CLP) lösen, aber AFAIK eine CLP-Bibliothek für F # noch niemand ist implementiert. miniKanren und cKanren sind zwei beliebte, einfache Beispiele für solche Systeme, und ich bezweifle, dass sie viel Zeit brauchen, um nach F # zu portieren, wenn Sie daran interessiert wären.