Chứng minh id bản đồ = id trong idris?

Question

Tôi chỉ mới bắt đầu chơi với idris và định lý chứng minh nói chung. Tôi có thể làm theo hầu hết các ví dụ về bằng chứng về các sự kiện cơ bản trên internet, vì vậy tôi muốn thử một cái gì đó tùy ý bằng của riêng tôi. Vì vậy, tôi muốn viết một thuật ngữ bằng chứng cho các tài sản cơ bản sau đây của bản đồ:

map : (a -> b) -> List a -> List b 
prf : map id = id 

trực giác, tôi có thể tưởng tượng như thế nào chứng minh nên làm việc: Tham dự một danh sách l tùy ý và phân tích các khả năng đồ id l. Khi l trống rỗng, nó hiển nhiên; khi l là không trống, nó dựa trên khái niệm rằng ứng dụng chức năng giữ được sự bình đẳng. Vì vậy, tôi có thể làm một cái gì đó như thế này:

prf' : (l : List a) -> map id l = id l 

Nó giống như một tuyên bố tất cả. Làm thế nào tôi có thể biến nó thành một bằng chứng về sự bình đẳng của các chức năng liên quan?

Answer 1

Bạn không thể. Lý thuyết loại của Idris (như Coq's và Agda's) không hỗ trợ tính mở rộng chung. Với hai hàm f và g rằng "hành động giống nhau", bạn sẽ không bao giờ có thể chứng minh Not (f = g), nhưng bạn sẽ chỉ có thể chứng minh f = g nếu f và g được xác định tương tự, tối đa alpha và eta tương đương. Thật không may, mọi thứ chỉ trở nên tồi tệ hơn khi bạn xem xét các hàm bậc cao hơn; có một định lý về điều đó trong thư viện chuẩn Coq, nhưng tôi dường như không thể tìm thấy hoặc nhớ nó ngay bây giờ.