Làm thế nào để bạn chứng minh rằng một hàm duy nhất cho kiểu của nó?

Question

id là chức năng duy nhất của loại a -> a và fst chức năng duy nhất của loại (a,b) -> a. Trong những trường hợp đơn giản này, điều này khá đơn giản để xem. Nhưng nói chung, làm thế nào bạn sẽ đi về chứng minh điều này? Điều gì sẽ xảy ra nếu có nhiều chức năng có thể có cùng loại?

Cách khác, với kiểu của hàm, bạn lấy hàm duy nhất (nếu điều này đúng) của loại đó như thế nào?

Chỉnh sửa: Tôi đặc biệt quan tâm đến những gì sẽ xảy ra khi chúng tôi bắt đầu thêm các ràng buộc vào các loại.

Answer 1

Kết quả bạn đang tìm kiếm nguồn gốc từ tham số Reynolds ', và được hiển thị nổi tiếng nhất bởi Wadler trong theorems for free.

Cách thanh lịch nhất để chứng minh các kết quả tham số cơ bản mà tôi đã thấy sử dụng khái niệm "Loại Singleton". Về cơ bản, đưa ra bất kỳ ADT

data Nat = Zero | Succ Nat 

có tồn tại một gia đình được lập chỉ mục (còn được gọi là GADT)

data SNat n where 
    SZero :: SNat Zero 
    SSucc :: SNat n -> SNat (Succ n) 

và chúng tôi có thể cung cấp một ngữ nghĩa ngôn ngữ của mình bằng cách "xóa" tất cả các loại đến một untyped ngôn ngữ như vậy mà Nat và SNat xóa cùng một điều. Sau đó, theo các quy tắc gõ của ngôn ngữ

id (x :: SNat n) :: SNat n 

SNat n đã chỉ có một cư dân (singleton của nó), vì ngữ nghĩa được đưa ra bởi tẩy xoá, chức năng có thể không sử dụng các loại lập luận của họ, do đó giá trị chỉ được trả lại từ id trên bất kỳ Nat là số bạn đã cung cấp. Lập luận cơ bản này có thể được mở rộng để chứng minh hầu hết các kết quả tham số và được Karl Crary sử dụng trong A Simple Proof Technique for Parametricity Results mặc dù bản trình bày mà tôi có ở đây được lấy cảm hứng từ Stone and Harper