GADT cho danh sách đa hình

Question

Tôi đang phân tích một vài báo cáo của mẫu

v1 = expression1 
v2 = expression2 
... 

Tôi đang sử dụng các đơn nguyên nhà nước và nhà nước của tôi phải là một cặp (String, expr a), tôi thực sự nhấn mạnh vào có biểu thức đã nhập. Tôi cố gắng để thực hiện tiểu bang như [PPair] nơi tôi xác định PPair bởi GADT:

data PPair where 
    PPair :: (String, Expr a) -> PPair 

Khi dòng này thông qua trình biên dịch, tôi cảm thấy rằng tôi đang làm một cái gì đó thực sự thực sự sai lầm. Tôi đè nén ý nghĩ và tiếp tục viết mã. Khi tôi đến viết code đó sẽ trích xuất các giá trị của biến từ Nhà nước, tôi nhận ra vấn đề:

evalVar k ((PPair (kk, v)):s) = if k == kk then v else evalVar k s 

tôi nhận được:

Inferred type is less polymorphic than expected 

mà là khá mong đợi. Làm cách nào để khắc phục sự cố này? Tôi biết tôi có thể giải quyết nó bằng cách phá vỡ các loại trên tất cả các loại ứng cử viên một, nhưng là không có cách neater?

Answer 1

Vấn đề là không có khả năng loại evalVar có thể có:

evalVar :: String -> [PPair] -> Expr ? 

Bạn không thể nói ? là a, bởi vì khi đó bạn đang xác nhận giá trị trả về của bạn làm việc cho bất kỳ giá trị của a. Những gì bạn có thể làm, tuy nhiên, là quấn lên "một Expr với một loại không rõ" vào kiểu dữ liệu riêng của mình:

data SomeExpr where 
    SomeExpr :: Expr a -> SomeExpr 

hay tương đương, với RankNTypes hơn GADTs:

data SomeExpr = forall a. SomeExpr (Expr a) 

Đây là được gọi là định lượng hiện có. Sau đó bạn có thể viết lại PPair sử dụng SomeExpr:

data PPair = PPair String SomeExpr 

và evalVar hoạt động ra: (. Tất nhiên, bạn có thể chỉ cần sử dụng một [(String,SomeExpr)] thay vào đó, và các tiêu chuẩn lookup chức năng)

evalVar k (PPair kk v : xs) 
    | k == kk = v 
    | otherwise = evalVar k xs 

Nói chung, mặc dù, cố gắng để giữ cho các biểu thức hoàn toàn gõ ở cấp độ Haskell như thế này có lẽ là một bài tập trong vô ích; một ngôn ngữ phụ thuộc kiểu như Agda sẽ không gặp rắc rối với nó, nhưng có thể bạn sẽ kết thúc chạy vào một cái gì đó Haskell không thể làm một cách nhanh chóng, hoặc làm suy yếu mọi thứ đến độ an toàn biên dịch mà bạn mong muốn bị mất.

Đó không phải là để nói rằng nó không bao giờ hoạt động, tất nhiên; các ngôn ngữ đã nhập là một trong những ví dụ thúc đẩy cho GADT. Nhưng nó có thể không hoạt động tốt như bạn muốn, và có thể bạn sẽ gặp rắc rối nếu ngôn ngữ của bạn có bất kỳ tính năng hệ thống kiểu không tầm thường nào như đa hình.

Nếu bạn thực sự muốn tiếp tục nhập, thì tôi sẽ sử dụng cấu trúc phong phú hơn các chuỗi để đặt tên biến; có một loại Var a mang rõ kiểu dữ liệu, như thế này:

data PPair where 
    PPair :: Var a -> Expr a -> PPair 

evalVar :: Var a -> [PPair] -> Maybe (Expr a) 

Cách tốt nhất để đạt được một cái gì đó tương tự như sau sẽ được sử dụng gói vault; bạn có thể xây dựng Key s từ ST và IO và sử dụng Vault làm vùng chứa không đồng nhất. Về cơ bản nó giống như một số Map trong đó các khóa giữ loại giá trị tương ứng. Cụ thể, tôi khuyên bạn nên xác định Var a là Key (Expr a) và sử dụng Vault thay vì [PPair] của mình. (Tiết lộ đầy đủ: Tôi đã làm việc trên gói vault.)

Tất nhiên, bạn vẫn phải ánh xạ các tên biến cho các giá trị Key, nhưng bạn có thể tạo tất cả các quyền Key s sau khi phân tích cú pháp và thực hiện những người xung quanh thay vì dây. (Tuy nhiên, có một chút công việc để chuyển từ tên Var sang tên biến tương ứng với chiến lược này; bạn có thể làm điều đó với danh sách các tồn tại, nhưng giải pháp quá dài để đưa vào câu trả lời này.)

(Nhân tiện, bạn có thể có nhiều đối số cho một hàm tạo dữ liệu với GADT, giống như các loại thông thường: data PPair where PPair :: String -> Expr a -> PPair.)