Jak dopasowywanie wzorców działa za kulisami w F #?

Question

Jestem całkowicie nowym użytkownikiem F # (i ogólnie programowania funkcjonalnego), ale widzę dopasowanie do wzorca używane wszędzie w przykładowym kodzie. Zastanawiam się na przykład, jak dopasowywanie wzorców faktycznie działa? Na przykład wyobrażam sobie, że działa tak samo, jak pętla for w innych językach i sprawdza dopasowania dla każdego elementu w kolekcji. Jest to prawdopodobnie dalekie od poprawności, jak to naprawdę działa za kulisami?

Answer 1

To zależy od tego, jaki rodzaj dopasowania do wzoru masz na myśli - jest to dość potężna konstrukcja i może być używana na wiele sposobów. Postaram się jednak wyjaśnić, jak dopasowywanie do wzorca działa na listach. Możesz napisać na przykład te wzory:

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) 

Lista F # jest rzeczywiście dyskryminowane związek zawierający dwa przypadki - [] reprezentujący pustą listę lub x::xs reprezentujący listę z pierwszego elementu x następnie kilka innych elementów. W języku C#, to może być przedstawiony następująco:

// 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; } 
} 

Wzory powyżej będzie kompilowany do następujących (używam pseudo-kodu, aby to prostsze):

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) 

jak można nie ma pętli. Podczas przetwarzania list w F #, używałbyś rekursji do implementacji pętli, ale dopasowywanie do wzorca jest używane na poszczególnych elementach (ConsList), które razem tworzą całą listę.

Wzorzec dopasowania na listach jest specyficznym przypadkiem dyskryminowanej unii który jest omawiany przez sepp2k. Istnieją inne konstrukcje, które mogą pojawiać się w dopasowywaniu wzorców, ale zasadniczo wszystkie z nich są kompilowane przy użyciu niektórych (skomplikowanych) instrukcji if.

Answer 2

Nie, nie zapętla się. Jeśli masz mecz wzór podobny do tego

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

to kompiluje się do czegoś jak ten pseudo kod:

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 

Jeśli Foo i Bar są konstruktorzy od typu algebraiczne danych (czyli typ zdefiniowany jak type FooBar = Foo int int | Bar int) operacje x is a Foo i x is a Bar są prostymi porównaniami. Jeśli są zdefiniowane przez active pattern, operacje są definiowane przez ten wzorzec.

Answer 3

W jaki sposób dopasowywanie wzorców rzeczywiście działa? To samo co pętla for?

To jest tak daleko od for pętli, jak można sobie wyobrazić: zamiast zapętlenie, mecz wzór jest skompilowany do sprawnego automatu. Istnieją dwa style automatu, które nazywam "drzewem decyzyjnym" i "stylem francuskim". Każdy styl oferuje różne zalety: drzewo decyzyjne sprawdza minimalną liczbę10 potrzebną do podjęcia decyzji, ale naiwna implementacja może wymagać wykładniczej przestrzeni kodu w najgorszym przypadku. Francuski styl oferuje inną kompromis w czasie i przestrzeni, z dobrymi, ale nie optymalnymi gwarancjami dla obu.

Ale absolutnie definitywna praca nad tym problemem to doskonała praca Luc Marangeta pod tytułem "Compiling Pattern Matching to Good Decisions Trees z ML Workshop 2008. Artykuł Luca w zasadzie pokazuje, jak uzyskać najlepsze z obu światów. Jeśli chcesz zastosować zabieg, który może być nieco bardziej dostępny dla amatora, pokornie polecam moją własną ofertę. When Do Match-Compilation Heuristics Matter?

Pisanie kompilatora dopasowanego do wzorca jest łatwe i przyjemne!

Answer 4

Jeśli skompilujesz swój kod F # do pliku .exe, a następnie spójrz na Reflector, możesz zobaczyć, co jest równoważnikiem C# w kodzie F #.

Użyłem tej metody, aby spojrzeć na przykłady F # całkiem sporo.