Khó hiểu về suy luận kiểu Haskell

Question

Tôi vừa bắt đầu học Haskell. Vì Haskell được nhập tĩnh và có suy luận kiểu đa hình, loại chức năng nhận dạng là

id :: a -> a 

id đề xuất có thể lấy bất kỳ loại nào làm tham số và tự trả về. Nó hoạt động tốt khi tôi thử:

a = (id 1, id True) 

Tôi giả sử rằng lúc biên dịch, id đầu tiên là Num a :: a -> a và id thứ hai là Bool -> Bool. Khi tôi cố gắng đoạn mã sau, nó mang lại một lỗi:

foo f a b = (f a, f b) 
result = foo id 1 True 

Nó cho thấy loại một phải cùng một loại b, vì nó hoạt động tốt với

result = foo id 1 2 

Nhưng là đúng là loại tham số của id có thể được đa hình, sao cho a và b có thể là loại khác nhau?

Answer 1

Được rồi, đây là một góc ma quái kỳ lạ của hệ thống kiểu Haskell. Vấn đề ở đây là có hai cách để suy luận chức năng của bạn foo.

-- rank 1 
foo :: forall a b. (a -> b) -> a -> a -> (b, b) 
foo f a b = (f a, f b) 

-- rank 2 
foo' :: (forall a. a -> a) -> a -> b -> (a, b) 
foo' f a b = (f a, f b) 

Loại thứ hai là loại bạn muốn, nhưng loại thứ nhất là loại bạn muốn. Loại thứ hai, như amalloy đã chỉ ra, là một loại hạng 2 (chúng ta sẽ bỏ qua ý nghĩa của hai phương pháp này nhưng đọc phần giới thiệu trong "Practical type inference for arbitrary-rank types" nếu bạn muốn giải thích tốt về các cấp bậc - không được đưa ra bởi bản chất của tập tin PDF khi bắt đầu được viết rõ ràng và rõ ràng).

Chúng tôi sẽ hoãn định nghĩa các loại xếp hạng cao hơn hiện tại và chỉ nói rằng vấn đề là GHC không thể suy ra loại xếp hạng 2. Trích dẫn bài báo:

Complete type inference is known to be undecidable for higher-rank (impredicative) type systems, but in practice programmers are more than willing to add type annotations to guide the type inference engine, and to document their code....

Kfoury and Wells show that typeability is decidable for rank ≤ 2, and undecidable for all ranks ≥ 3 (Kfoury & Wells, 1994). For the rank-2 fragment, the same paper gives a type inference algorithm. This inference algorithm is somewhat subtle, does not interact well with user-supplied type annotations, and has not, to our knowledge, been implemented in a production compiler.

Có nghĩa là không thể có thuật toán luôn dẫn đến quyết định có hoặc không chính xác. Vì vậy, có bạn có nó: không thể suy ra một loại cấp bậc 3 hoặc cao hơn, và nó quá gosh-darn-khó để suy ra loại hạng 2.

Bây giờ, quay lại xếp hạng 2. (forall a. a -> a) là thứ giúp xếp hạng 2. There's already an excellent Stack Overflow question about what the forall keyword means vì vậy tôi sẽ giới thiệu bạn đến đó, nhưng về cơ bản nó có nghĩa là bạn có thể gọi f a và f b trong biểu thức (f a, f b) khi có a và b thể loại khác nhau, đó là những gì bạn muốn ở nơi đầu tiên, trước khi tất cả mớ hỗn độn nóng bỏng này.

Điều cuối cùng: Lý do bạn thường không thấy forall s trong GHCi là bất kỳ forall giây nào trên phạm vi ngoài cùng đều bị tắt. Vì vậy, forall a b. (a -> b) -> a -> a -> (b, b) tương đương với (a -> b) -> a -> a -> (b, b).

Nhìn chung đây là điểm đau của ngôn ngữ được giải thích kém.

(Hat tip để @amalloy trong các ý kiến.)