Làm thế nào để phù hợp với mô hình làm việc đằng sau hậu trường trong F #?

Question

Tôi hoàn toàn mới đối với F # (và lập trình hàm nói chung) nhưng tôi thấy kết hợp mẫu được sử dụng ở mọi nơi trong mã mẫu. Tôi tự hỏi ví dụ làm thế nào mô hình phù hợp với thực sự hoạt động? Ví dụ, tôi tưởng tượng nó hoạt động giống như vòng lặp for trong các ngôn ngữ khác và kiểm tra các kết quả phù hợp trên mỗi mục trong một bộ sưu tập. Điều này có lẽ là xa chính xác, làm thế nào nó thực sự làm việc đằng sau hậu trường?

Answer 1

Nó phụ thuộc vào loại kết hợp mẫu nào bạn muốn nói - nó có cấu trúc khá mạnh và có thể được sử dụng theo mọi cách. Tuy nhiên, tôi sẽ cố gắng giải thích cách khớp mẫu hoạt động trên danh sách. Bạn có thể viết ví dụ những mẫu:

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) 

Chiếc F # danh sách thực sự là một sự kết hợp kỳ thị có chứa hai trường hợp - [] đại diện cho một danh sách rỗng hoặc x::xs đại diện cho một danh sách với phần tử đầu tiên x sau bởi một số yếu tố khác. Trong C#, điều này có thể được biểu diễn như thế này:

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

Các mô hình trên sẽ được biên dịch như sau (tôi đang sử dụng pseudo-code để làm đơn giản này):

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) 

Như bạn có thể thấy, không có vòng lặp liên quan. Khi xử lý danh sách trong F #, bạn sẽ sử dụng đệ quy để thực hiện vòng lặp, nhưng khớp mẫu được sử dụng trên các phần tử riêng lẻ (ConsList) cùng nhau tạo toàn bộ danh sách.

Kết hợp mẫu trên danh sách là trường hợp cụ thể của công đoàn phân biệt được thảo luận bởi sepp2k. Có các cấu trúc khác có thể xuất hiện trong kết hợp mẫu, nhưng về cơ bản tất cả chúng được biên dịch bằng cách sử dụng câu lệnh if phức tạp (phức tạp).

Answer 2

Không, nó không lặp lại. Nếu bạn có một mô hình phù hợp như thế này

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

này biên dịch xuống một cái gì đó giống như mã giả này:

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 

Nếu Foo và Bar là nhà xây dựng từ một kiểu dữ liệu đại số (ví dụ: một loại được xác định như type FooBar = Foo int int | Bar int) các hoạt động x is a Foo và x is a Bar là các so sánh đơn giản. Nếu chúng được xác định bởi một active pattern, các hoạt động được xác định bởi mẫu đó.

Answer 3

Cách đối sánh mẫu thực sự hoạt động? Giống như một vòng lặp for?

Đó là về như xa một vòng lặp for như bạn có thể tưởng tượng: thay vì vòng lặp, một mô hình phù hợp là biên soạn để một automaton hiệu quả. Có hai kiểu automaton, cái mà tôi gọi là "cây quyết định" và "kiểu Pháp". Mỗi kiểu có các ưu điểm khác nhau: cây quyết định kiểm tra số lượng tối thiểu cần thiết để đưa ra quyết định, nhưng việc triển khai ngây thơ có thể yêu cầu không gian mã theo cấp số nhân trong trường hợp xấu nhất. Phong cách Pháp cung cấp một sự cân bằng không gian thời gian khác nhau, với sự đảm bảo tốt nhưng không tối ưu cho cả hai.

Nhưng công việc hoàn toàn dứt khoát về vấn đề này là giấy tuyệt vời của Luc Maranget "Compiling Pattern Matching to Good Decisions Trees từ Hội thảo ML 2008. Giấy của Luc về cơ bản cho thấy làm thế nào để có được tốt nhất của cả hai thế giới. Nếu bạn muốn điều trị có thể dễ tiếp cận hơn với người chuyên nghiệp, tôi khiêm tốn đề nghị cung cấp của riêng tôi When Do Match-Compilation Heuristics Matter?

Viết trình biên dịch khớp mẫu thật dễ dàng và thú vị!

Answer 4

Nếu bạn biên dịch mã F # thành .exe thì hãy xem Reflector bạn có thể xem C# "tương đương" của mã F #.

Tôi đã sử dụng phương pháp này để xem xét các ví dụ về F # một chút.