Ý nghĩa của mẫu chồng lên nhau trong Haskell

Question

Sự hiểu biết hiện tại của tôi về chồng chéo mẫu trong Haskell là 2 mẫu được coi là chồng chéo nếu một số giá trị đối số được truyền cho hàm có thể được khớp với nhiều mẫu.

Given:

last :: [a] -> a 
last [x] = x 
last (_ : xs) = last xs 

đi qua các giá trị tham số [1] sẽ phù hợp với cả hai mô hình đầu tiên [x] và mô hình thứ 2 (_: xs) - do đó sẽ có nghĩa là chức năng đã chồng chéo mẫu mặc dù cả hai mẫu có thể được khớp.

Điều làm cho điều này gây nhầm lẫn là mặc dù các mẫu (theo định nghĩa trên) chồng lên nhau, GHC không hiển thị bất kỳ cảnh báo nào về việc chúng trùng lặp.

Lùi lại mô hình 2 trận đấu trong last chức năng không hiển thị các cảnh báo chồng chéo:

last :: [a] -> a 
last (_ : xs) = last xs 
last [x] = x 

Cảnh báo:

src\OverlappingPatterns.hs:6:1: Warning: 
    Pattern match(es) are overlapped 
    In an equation for `last': last [x] = ... 

Nó gần như GHC consideres các mô hình chồng chéo nếu một mô hình trước đó làm cho nó không thể phù hợp với một mô hình xảy ra sau đó.

Cách chính xác để xác định xem một hàm có mẫu chồng chéo hay không?

---

Cập nhật

Tôi đang tìm kiếm các nghĩa được sử dụng trong fp101x nhiên.

Theo định nghĩa được sử dụng trong fp101x chức năng sau có overlapping patterns:

last :: [a] -> a 
last [x] = x 
last (_ : xs) = last xs 

Đây là mâu thuẫn với định nghĩa của GHC mà không xem xét nó có bất kỳ mô hình chồng chéo.

Không có định nghĩa đúng về những gì có nghĩa là trong ngữ cảnh khóa học fp101x, không thể giải quyết bài tập đó. Và định nghĩa được sử dụng không phải là định nghĩa của GHC.

Answer 1

Câu hỏi được cập nhật làm rõ OP muốn có định nghĩa chính thức về các mẫu trùng lặp. Ở đây "chồng chéo" có nghĩa là được sử dụng bởi GHC khi nó phát ra cảnh báo của nó: có nghĩa là, khi nó phát hiện ra một nhánh không thể truy cập được vì mẫu của nó không khớp với bất kỳ thứ gì chưa được xử lý bởi nhánh trước đó.

Một định nghĩa chính thức có thể thực sự tuân theo trực giác đó. Tức là, đối với bất kỳ mẫu nào p, trước tiên, bạn có thể xác định tập hợp các giá trị (ký hiệu) [[p]] khớp với p. (Đối với điều này, điều quan trọng là phải biết loại của các biến liên quan đến p -. [[p]] phụ thuộc vào một loại môi trường Gamma) Sau đó, người ta có thể nói rằng trong chuỗi các mẫu

q0 q1 ... qn p 

mô hình p là chồng chéo iff [[p]], như một bộ, được bao gồm trong [[q0]] union ... union [[qn]].

Định nghĩa trên hầu như không hoạt động, mặc dù - nó không ngay lập tức dẫn đến một thuật toán để kiểm tra trùng lặp. Thật vậy, tính toán [[p]] là không khả thi vì nó là một tập vô hạn, nói chung.

Để xác định thuật toán, tôi sẽ cố gắng xác định đại diện cho tập hợp cụm từ "chưa được đối sánh" theo bất kỳ mẫu nào q0 .. qn. Ví dụ: giả sử chúng tôi làm việc với danh sách các boolean:

Remaining: _ (that is, any list) 

q0 = [] 
Remaining: _:_ (any non empty list) 

q1 = (True:xs) 
Remaining: False:_ 

p = (True:False:ys) 
Remaining: False:_ 

Ở đây, bộ "còn lại" không thay đổi, do đó mẫu cuối cùng bị chồng chéo.

Một ví dụ khác:

Remaining: _ 

q0 = True:[] 
Remaining: [] , False:_ , True:_:_ 

q1 = False:xs 
Remaining: [], True:_:_ 

q2 = True:False:xs 
Remaining: [], True:True:_ 

q3 = [] 
Remaining: True:True:_ 

p = True:xs 
Remaining: nothing -- not overlapping (and exhaustive as well!) 

Như bạn có thể thấy, trong mỗi bước chúng tôi phù hợp với mỗi người trong số các mẫu "còn lại" với mô hình trong tầm tay. Điều này tạo ra một tập mới các mẫu còn lại (có thể không có). Bộ sưu tập của tất cả các mẫu này tạo thành bộ còn lại mới.

Đối với điều này, lưu ý rằng điều quan trọng là phải biết danh sách các hàm tạo cho mỗi loại. Điều này là do khi kết hợp với True, bạn phải biết còn lại một trường hợp False khác. Tương tự, nếu bạn đối sánh với [], còn lại _:_ trường hợp khác. Nói chung, khi kết hợp với constructor K, tất cả các hàm tạo khác cùng loại vẫn giữ nguyên.

Các ví dụ trên chưa phải là một thuật toán, nhưng chúng có thể giúp bạn bắt đầu, hy vọng.

Tất nhiên điều này bỏ qua các nhân viên bảo vệ trường hợp (làm cho chồng chéo không thể xác định), bảo vệ mẫu, GADT (có thể tinh chỉnh thêm bộ còn lại theo những cách khá tinh tế).

Answer 2

Tôi nghĩ điều này là trong trường hợp đầu tiên, không phải tất cả các kết quả phù hợp của [x] sẽ khớp nhau (_: xs). Trong trường hợp thứ hai, ngược lại là đúng (không có kết hợp nào (_: xs) sẽ rơi qua [x]). Vì vậy, chồng chéo thực sự có nghĩa là có một mẫu không thể truy cập được.

Đây là những gì tài liệu GHC đã nói về nó:

By default, the compiler will warn you if a set of patterns are either incomplete (i.e., you're only matching on a subset of an algebraic data type's constructors), or overlapping, i.e.,

f :: String -> Int 
f []  = 0 
f (_:xs) = 1 
f "2" = 2 

where the last pattern match in `f' won't ever be reached, as the second pattern overlaps it. More often than not, redundant patterns is a programmer mistake/error, so this option is enabled by default.

Maybe "mẫu unreachable" sẽ là một lựa chọn tốt hơn các từ.

Answer 3

I am looking for the overlapping pattern definition used in fp101x course.

"Patterns mà không dựa vào thứ tự mà chúng được kết hợp là gọi là rời nhau hoặc không chồng chéo."(Từ "Lập trình trong Haskell" Graham Hutton)

Vì vậy, ví dụ này sẽ không chồng chéo

foldr :: (a → b → b) → b → [a] → b 
foldr v [] = v 
foldr f v (x : xs) = f x (foldr f v xs) 

Bởi vì bạn có thể thay đổi thứ tự của mô hình khớp như thế này:

foldr :: (a → b → b) → b → [a] → b 
foldr f v (x : xs) = f x (foldr f v xs) 
foldr v [] = v 

Và tại đây bạn không thể:

last :: [a] -> a 
last [x] = x 
last (_ : xs) = last xs 

Vì vậy, cuối cùng)) là chồng chéo.

Answer 4

Tôi khuyên bạn nên sử dụng logic lý luận kết hợp với thông điệp trình biên dịch và kết quả kiểm tra sẽ là cách tốt hơn để hiểu liệu hàm có chồng chéo hay không. Như hai ví dụ, đầu tiên đã được liệt kê, thực sự dẫn đến một cảnh báo trình biên dịch.

-- The first definition should work as expected. 
last1 :: [a] -> a 
last1 [x] = x 
last1 (_:xs) = last xs 

in the second case if we swap the last two lines around then a compiler error which states. Program error: pattern match failure: init1 [] results

last :: [a] -> a 
last (_:xs) = last xs 
last [x] = x 

này phù hợp với logic của đi qua một danh sách singleton mà có thể phù hợp trong cả hai mô hình, và trong trường hợp này dòng tại thứ hai.

last (_:xs) = last xs 

sẽ khớp trong cả hai trường hợp. Nếu sau đó chúng tôi chuyển sang ví dụ thứ hai

-- The first definition should work as expected 
drop :: Int -> [a] -> [a] 
drop 0 xs = xs 
drop n [] = [] 
drop n (_:xs) = drop1 (n - 1) xs 

In the second case if we again swap the last line with the first line then we don't get a compiler error but we also don't get the results we expect. Main> drop 1 [1,2,3] returns an empty list []

drop :: Int -> [a] -> [a] 
drop n (_:xs) = drop1 (n - 1) xs 
drop 0 xs = xs 
drop n [] = [] 

Nói tóm lại tôi nghĩ rằng đây là lý do tại sao lập luận (như phản đối một định nghĩa chính thức) để xác định mô hình chồng chéo hoạt động ok.