Haskell: các ví dụ không rõ ràng về các phụ thuộc chức năng

Question

Ví dụ về các phụ thuộc chức năng mà tôi đã thấy khi lập bản đồ container -> element và arguments -> result (như trong Mult Matrix Vector Vector). Họ dường như được thể hiện tốt hơn với các chức năng kiểu. Trong lý thuyết cơ sở dữ liệu, các mối quan hệ phức tạp hơn được coi là không có dạng này (như a -> b, b -> a).

Có các ví dụ về cách sử dụng FD trong Haskell không thể được viết bằng cách sử dụng các chức năng loại không?

Answer 1

Như Heinrich Apfelmus đã nói MPTC + FunDeps và TF đơn thuần là tương đương. Sự khác biệt phát sinh khi chúng được kết hợp với các phần mở rộng khác đặc biệt với các trường hợp trùng lặp. TF không rõ ràng khi được phép chồng chéo trong khi FunDep cho phép chồng chéo. Ví dụ: dễ dàng thực hiện loại bình đẳng với FunDeps:

data HTrue 
data HFalse 

class TypeEq a b eq | a b -> eq 
instance    TypeEq a a HTrue 
instance eq ~ HFalse => TypeEq a b eq 

Điểm chính ở đây là trùng lặp. Về nguyên tắc nó có thể thực hiện bình đẳng loại mà không chồng chéo nhưng nó sẽ yêu cầu hỗ trợ trình biên dịch. Cách tiếp cận đó được mô tả bởi Oleg tại đây: http://okmij.org/ftp/Haskell/typeEQ.html

P.S. Đã có lengthy discussion trên danh sách gửi thư của haskell-prime về chủ đề này.

Answer 2

Khi Manuel Chakravarty explains, các chức năng loại và phụ thuộc chức năng có cùng biểu cảm, bạn có thể dịch một công thức này sang dạng khác. Chúng chỉ bắt đầu khác khi bạn xem xét tương tác với các phần mở rộng ngôn ngữ khác như GADT hoặc UndecidableInstances. Tôi thu thập các loại gia đình hiện đang được ưa chuộng để thực hiện trong GHC vì sự tương tác của chúng với GADT và các loại tồn tại đơn giản hơn rất nhiều.