Unterschiede zwischen Mustererkennung und Vereinheitlichung?

Question

Ich dachte, ich verstehe, wie Mustervergleich wie in Scala und Haskell unterscheidet sich von Vereinheitlichung in Prolog gefunden, aber meine Missverständnisse von Prolog ist groß. Was sind einige einfache Probleme, die durch das eine lösbar sind? Danke

Answer 1

Einfache Aussage: Musterabgleich ist Einweg, Vereinigung ist Zweiwege. Das heißt, in Prolog kann die rechte Seite (die Gegenseite) ungebundene Variablen enthalten. Zum Beispiel, wenn Sie zwei ungebundene Variablen X und Y, wird dies funktionieren:

X = Y, 
X = 5, 
%% Y = 5 now as well 

In Erlang (das Pattern-Matching mit Syntax der Nähe von Prolog verwendet), die Linie X = Y einen Fehler erzeugen: variable 'Y' is unbound. Beachten Sie, dass X nicht gebunden ist, ist in Ordnung: Es soll Muster-Matched sein.

Dies kann nützlich sein, wenn Sie mit teilweise definierten Werten arbeiten möchten. Ein sehr gutes Beispiel ist difference lists.

Dies ermöglicht auch die Verwendung des Prolog-Prädikats in mehreren Modi. Z.B. in Scala/Haskell/Erlang, wenn Sie 1) finden wollen A ++ B, 2) lösen Sie die Gleichung A ++ X == B, oder 3) lösen Sie die Gleichung X ++ A == B für gegebene Listen A und B, müssen Sie 3 separate Funktionen schreiben; In Prolog werden alle diese Jobs (und mehr!) von einem Prädikat ausgeführt.

Answer 2

Die folgenden in Scala würde nicht kompilieren, wie es erste Fall Branch versucht, die Variable x zweimal zu deklarieren.

(1, 1) match{ 
    case (x, x) => println("equals") 
    case _  => println("not equals") 
} 

Wenn Scala Vereinigung anstelle von Pattern-Matching dies gelingen würde und print "ist gleich", während

(1, 2) match{ 
    case (x, x) => println("equals") 
    case _  => println("not equals") 
} 

"ungleich" drucken. Dies liegt daran, dass die Vereinigung fehlschlagen würde, wenn versucht wird, die Variable x sowohl an 1 als auch an 2 zu binden.

Answer 3

In Prolog, können Sie [3] bis [1,2] wie folgt anhängen:

?- append([1,2], [3], Z). 
Z = [1, 2, 3]. 

Die nette Sache über die Vereinigung ist, dass Sie den gleichen Code (die interne Definition von 'Append' verwenden können), sondern stattdessen das zweite Argument finden benötigt, um das Ergebnis aus dem ersten Argumente zu erhalten:

?- append([1,2], Y, [1,2,3]). 
Y = [3]. 

vielmehr durch das Schreiben „tun dies, dann tun, dass“ als Codierung, Sie Code in Prolog sagen, was Sie wissen. Prolog behandelt die Fakten, die Sie ihm geben, als Gleichungen. Bei der Vereinheitlichung können Sie diese Gleichungen verwenden und nach Variablen suchen, deren Werte Sie noch nicht kennen, unabhängig davon, ob sie sich auf der rechten oder der linken Seite befinden.

So können Sie zum Beispiel einen Planer in Prolog schreiben, und Sie können es "vorwärts" laufen lassen, ihm einen Plan geben und es seine Ergebnisse vorhersagen lassen; oder Sie können es "rückwärts" ausführen, indem Sie ihm eine Reihe von Ergebnissen geben und einen Plan erstellen lassen. Sie könnten sogar beide Methoden gleichzeitig ausführen (wenn Sie beim Codieren vorsichtig waren), indem Sie eine Reihe von Zielen und eine Reihe von Einschränkungen für den Plan angeben, so dass Sie sagen können: "Finden Sie einen Plan, um zur Arbeit zu gelangen, die nicht involviert ist mit der U-Bahn."

Answer 4

Ich denke, es ist nützlich, um die Konzepte zu formalisieren, statt in eine bestimmte Sprache suchen. Matching und Vereinigung sind grundlegende Konzepte, die als Musteranpassung und Prolog in mehreren Kontexten verwendet werden.

• Ein Begriff s Spielen t, genau dann, wenn es eine Substitution phi so daß phi (n) = t
• ein Begriff s vereinheitlicht mit einer Laufzeit t, genau dann, wenn es eine Substitution derart ist, daß phi (n) = phi (t)

Um ein Beispiel zu geben, untersuchen wir die Begriffe s = f (Y, a) und t = f (a, X) wo X, Y sind Variablen und a ist eine Konstante. s stimmt nicht mit t überein, weil wir die Konstante a nicht allgemein quantifizieren können. Es gibt jedoch einen Unifikator für s und t: phi = {X \ a, Y \ a}