Wie funktioniert die Mustererkennung hinter den Kulissen in F #?

Question

Ich bin völlig neu in F # (und funktionale Programmierung im Allgemeinen), aber ich sehe Mustervergleich überall im Beispielcode verwendet. Ich frage mich zum Beispiel, wie Mustererkennung tatsächlich funktioniert? Zum Beispiel stelle ich mir vor, dass es genauso funktioniert wie eine for-Schleife in anderen Sprachen und nach Übereinstimmungen für jedes Element in einer Sammlung sucht. Das ist wahrscheinlich nicht richtig, wie funktioniert es eigentlich hinter den Kulissen?

Answer 1

Es hängt davon ab, welche Art von Musterabgleich meinst du - es ist ziemlich mächtig Konstrukt und kann auf vielerlei Arten verwendet werden. Ich werde jedoch versuchen zu erklären, wie die Mustererkennung in Listen funktioniert. Sie können diese Muster zum Beispiel schreiben:

match l with 
| [1; 2; 3] -> // specific list of 3 elements 
| 1::rest -> // list starting with 1 followed by more elements 
| x::xs ->  // non-empty list with element 'x' followed by a list 
| [] ->   // empty list (no elements) 

Die # Liste F ist eigentlich eine diskriminierte Vereinigung, die zwei Fälle - [] eine leere Liste oder x::xs den eine Liste mit erstem Elemente darstellt x von einigen anderen Elementen gefolgt.

// Represents any list 
abstract class List<T> { } 
// Case '[]' representing an empty list 
class EmptyList<T> : List<T> { } 
// Case 'x::xs' representing list with element followed by other list 
class ConsList<T> : List<T> { 
    public T Value { get; set; } 
    public List<T> Rest { get; set; } 
} 

Die Muster der folgenden zusammengestellt würden oben (ich bin mit Pseudo-Code, um diese einfacher zu machen): In C#, könnte dies wie folgt dargestellt werden

if (l is ConsList) && (l.Value == 1) && 
    (l.Rest is ConsList) && (l.Rest.Value == 2) && 
    (l.Rest.Rest is ConsList) && (l.Rest.Rest.Value == 3) && 
    (l.Rest.Rest.Rest is EmptyList) then 
    // specific list of 3 elements 
else if (l is ConsList) && (l.Value == 1) then 
    var rest = l.Rest; 
    // list starting with 1 followed by more elements 
else if (l is ConsList) then 
    var x = l.Value, xs = l.Rest; 
    // non-empty list with element 'x' followed by a list 
else if (l is EmptyList) then 
    // empty list (no elements) 

Wie Sie können Sehen Sie, es gibt keine Schleife. Wenn Sie Listen in F # verarbeiten, würden Sie die Rekursion verwenden, um Schleifen zu implementieren, aber die Mustererkennung wird für einzelne Elemente (ConsList) verwendet, die zusammen die gesamte Liste bilden.

Muster auf Listen entspricht ist ein Sonderfall der diskriminiert Union die durch sepp2k diskutiert wird. Es gibt andere Konstrukte, die im Mustervergleich erscheinen können, aber im Wesentlichen werden alle von ihnen unter Verwendung einer (komplizierten) if Anweisung kompiliert.

Answer 2

Nein, es ist keine Schleife. Wenn Sie ein Muster Spiel wie dies

match x with 
| Foo a b -> a + b 
| Bar c -> c 

haben kompiliert diese wie dieser Pseudo-Code, um etwas nach unten:

if (x is a Foo) 
    let a = (first element of x) in 
    let b = (second element of x) in 
    a+b 
else if (x is a Bar) 
    let c = (first element of x) in 
    c 

Wenn Foo und Bar sind Konstrukteure von einem algebraischen Datentyp (dh eine Art definiert wie type FooBar = Foo int int | Bar int) Die Operationen x is a Foo und x is a Bar sind einfache Vergleiche. Wenn sie durch eine active pattern definiert sind, werden die Operationen von diesem Muster definiert.

Answer 3

Wie funktioniert die Mustererkennung? Das gleiche wie eine for Schleife?

Es ist ungefähr so ​​weit von einer for Schleife, wie man sich vorstellen kann: statt Looping, ist ein Muster Spiel zu einem effizienten Automaten zusammengestellt. Es gibt zwei Arten von Automaten, die ich den "Entscheidungsbaum" und den "französischen Stil" nenne. Jeder Stil bietet verschiedene Vorteile: Der Entscheidungsbaum prüft die Anzahl der Werte, die für eine Entscheidung erforderlich sind, aber eine naive Implementierung kann im schlimmsten Fall exponentiellen Code-Speicherplatz erfordern. Der französische Stil bietet einen anderen Zeit-Raum-Kompromiss, mit guten, aber nicht optimalen Garantien für beide.

Aber die absolut definitive Arbeit zu diesem Problem ist Luc Marangets ausgezeichnetes Papier "Compiling Pattern Matching to Good Decisions Trees vom ML Workshop 2008. Lucs Papier zeigt im Grunde, wie man das Beste aus beiden Welten herausholt. Wenn Sie eine Behandlung wünschen, die für den Amateur etwas zugänglicher sein kann, empfehle ich demnächst mein eigenes Angebot. When Do Match-Compilation Heuristics Matter?

Das Schreiben eines Pattern-Match-Compilers ist einfach und macht Spaß!

Answer 4

Wenn Sie Ihren F # -Code zu einer .exe kompilieren dann schauen Sie sich mit Reflector Sie können sehen, was das C# "Äquivalent" des F # -Codes ist.

Ich habe diese Methode verwendet, um F # -Beispiele ein wenig zu betrachten.