Tại sao GHC phàn nàn về các mẫu không đầy đủ?

Question

Khi tôi biên dịch đoạn mã sau với GHC (sử dụng -Wall cờ):

module Main where 

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show) 

insert :: (Ord a) => a -> Tree a -> Tree a 
insert x EmptyTree = Node x EmptyTree EmptyTree 
insert x (Node a left right) 
    | x == a = Node a left right 
    | x < a = Node a (insert x left) right 
    | x > a = Node a left (insert x right) 

main :: IO() 
main = do 
    let nums = [1..10]::[Int] 
    print . foldr insert EmptyTree $ nums 

GHC phàn nàn rằng mô hình phù hợp trong insert là không đầy đủ:

test.hs|6| 1: 
||  Warning: Pattern match(es) are non-exhaustive 
||    In an equation for `insert': Patterns not matched: _ (Node _ _ _) 

Tại sao GHC ban hành cảnh báo này? Nó là khá rõ ràng rằng mô hình GHC than phiền về được xử lý trong insert x (Node a left right).

Answer 1

Riccardo là chính xác, GHC không suy luận rằng các vệ sĩ của bạn không thể sai lầm. Vì vậy, chấp nhận câu trả lời của mình xin vui lòng.

Tôi sẽ phân tích và nói về phong cách mã hóa.

động lực của bạn không sử dụng otherwise có thể là nó trông khó coi:

insert :: (Ord a) => a -> Tree a -> Tree a 
insert x EmptyTree = Node x EmptyTree EmptyTree 
insert x (Node a left right) 
    | x == a = Node a left right 
    | x < a  = Node a (insert x left) right 
    | otherwise = Node a left (insert x right) 

Nhìn vào mã này, một độc giả của con người phải xác nhận với bản thân rằng bảo vệ chính thức chấp nhận một cách chính xác những trường hợp x > a.

Chúng tôi thay vì có thể viết nó như thế này:

insert :: (Ord a) => a -> Tree a -> Tree a 
insert x EmptyTree = Node x EmptyTree EmptyTree 
insert x (Node a left right) = case x `compare` a of 
    EQ -> Node a left right 
    LT -> Node a (insert x left) right 
    GT -> Node a left (insert x right) 

Loại Ordering trả về bởi compare chỉ có ba giá trị EQ, LT, và GT, vì vậy GHC thể xác nhận rằng bạn đã bao phủ tất cả các khả năng, và một người đọc của con người có thể dễ dàng thấy rằng bạn đã bao phủ chúng một cách chính xác.

Đây cũng là mã hiệu quả hơn: chúng tôi gọi compare một lần, thay vì gọi == và sau đó có thể gọi số <.

Bây giờ tôi sẽ nghiên cứu thêm và nói về sự lười biếng.

Bạn đã có lẽ cũng viết một chức năng tương tự như sau:

contains :: (Ord a) => a -> Tree a -> Bool 
contains _ EmptyTree = False 
contains x (Node a left right) = case x `compare` a of 
    EQ -> True 
    ... 

Khi x == a, bạn cần phải biết rằng cây sử dụng constructor Node, và rằng số đầu tiên của nó là bằng x. Bạn không cần phải biết một trong hai subtrees là gì.

Nhưng bây giờ hãy nhìn lại định nghĩa của tôi về số insert ở trên. Khi cây được đưa ra là Node, nó luôn trả về một số Node, đối số đầu tiên của nó luôn là a. Nhưng nó không tuyên bố rằng lên phía trước: thay vào đó nó đánh giá x `compare` a.

Chúng ta có thể viết lại insert để thực hiện việc so sánh như trễ càng tốt:

insert :: (Ord a) => a -> Tree a -> Tree a 
insert x EmptyTree = Node x EmptyTree EmptyTree 
insert x (Node a left right) = Node a newLeft newRight 
    where comparison = x `compare` a 
     newLeft = if comparison == LT then insert x left else left 
     newRight = if comparison == GT then insert x right else right 

Bây giờ chúng ta quay trở lại các bit Node a càng sớm càng tốt --- ngay cả khi so sánh ném một lỗi! --- và chúng tôi vẫn thực hiện so sánh một lần nhiều nhất.

Answer 2

GHC không thể suy luận xem ba vệ sĩ của bạn trong số insert x (Node a left right) có bao gồm tất cả các trường hợp có thể xảy ra hay không và do đó sẽ không có nội dung nào được liên kết với insert x (Node a left right). Hãy thử thay thế điều kiện cuối cùng x > a bằng otherwise (đồng bộ hóa cho True). Tuy nhiên, trong trường hợp cụ thể này, đúng là các vệ sĩ không bao gồm tất cả các trường hợp, hãy xem ví dụ về các số tăng gấp đôi của augusts.

Answer 3

Đó là do khớp mẫu không hoàn chỉnh. Không có gì đảm bảo rằng một trong số x==a, x<a hoặc giữ x>a. Ví dụ: nếu loại là Double và x là NaN thì không có loại nào trong số đó là True.