Mã hóa không có mã hóa cuối cùng của các loại đệ quy hai loại

Question

Tôi đang cố gắng diễn tả một cặp kiểu dữ liệu đệ quy hai chiều trong mã hóa final-tagless.

tôi có thể viết:

{-# LANGUAGE NoMonomorphismRestriction #-} 
{-# LANGUAGE ExplicitForAll #-} 
module Test where 

    class ExprSYM repr where 
    expr :: forall proc. (ProcSYM proc) => proc Int -> repr 

    class ProcSYM repr where 
    varProc :: forall a. String -> repr a 
    intProc :: String -> repr Int 
    subjectOf :: forall expr. (ExprSYM expr) => expr -> repr Int 

    myProc = intProc "proc A." 

Tuy nhiên, khi tôi viết:

myExpr = expr myProc 

tôi nhận được lỗi sau:

Could not deduce (Test.ProcSYM proc0) 
    arising from a use of ‘Test.expr’ 
from the context (Test.ExprSYM repr) 
    bound by the inferred type of 
      Test.myExpr :: Test.ExprSYM repr => repr 
    at src/Test.hs:16:3-22 
The type variable ‘proc0’ is ambiguous 
In the expression: Test.expr Test.myProc 
In an equation for ‘Test.myExpr’: 
    Test.myExpr = Test.expr Test.myProc 

Có bất kỳ mã hóa như vậy đòi hỏi việc sử dụng các phụ thuộc chức năng (hoặc tương đương) để loại bỏ ràng buộc giữa hai loại representation es?

Nếu có, tôi sẽ viết điều này bằng cách nào?

Answer 1

Hãy bắt đầu bằng cách nhìn vào loại myProc

myProc :: ProcSYM repr => repr Int 
myProc = intProc "proc A." 

này nói, forall loại repr nơi ProcSYM repr, tôi là một giá trị của loại repr Int. Nếu chúng tôi có nhiều lần triển khai ProcSYM, đây là một giá trị đa hình trong tất cả chúng. Ví dụ: nếu chúng tôi đã gắn thẻ tương ứng GADTProcSYM' với ví dụ ProcSYM, thì có thể sử dụng myProc làm giá trị ProcSYM'.

{-# LANGUAGE GADTs #-} 

data ProcSYM' a where 
    VarProc :: String -> ProcSYM' a 
    IntProc :: String -> ProcSYM' a 

instance ProcSYM ProcSYM' where 
    varProc = VarProc 
    intProc = IntProc 

myProc' :: ProcSYM' Int 
myProc' = myProc 

Các ProcSym repr hạn chế trong myProc :: ProcSYM repr => repr Int đang cung cấp một cách để xây dựng repr s, đó là chính xác những gì myProc làm. Không có vấn đề gì ProcSym repr bạn muốn, nó có thể xây dựng một repr Int.

Hạn chế ProcSYM proc trong loại expr :: forall proc. (ProcSYM proc) => proc Int -> repr là loại vô nghĩa. Ràng buộc ProcSYM proc một lần nữa cung cấp phương tiện để xây dựng proc s. Không thể giúp chúng tôi nhìn vào bên trong hoặc deconstruct a proc Int. Không có cách nào để xem bên trong proc Int s, chúng tôi cũng không có đối số proc Int và thay vào đó đọc expr :: repr.

Loại forall proc. ProcSYM proc => proc Int (kiểu myProc) mặt khác, hứa hẹn, bất kể bạn xây dựng proc s, tôi có thể cung cấp giá trị kiểu đó. Bạn muốn vượt qua myProc như là đối số đầu tiên expr, bằng chứng là

myExpr = expr myProc 

Đi qua trong một giá trị đa hình thuộc loại này mà không chọn một bê tông proc đòi hỏi RankNTypes.

class ExprSYM repr where 
    expr :: (forall proc. ProcSYM proc => proc Int) -> repr 

Các ví dụ cho ExprSYM có thể chọn từ điển ProcSYM để vượt qua thành đối số đầu tiên. Điều này cho phép thực hiện expr để hủy cấu trúc proc Int. Chúng tôi sẽ chứng minh điều này bằng cách hoàn thành một ví dụ với GADTs để xem điều này đang làm gì. Chúng tôi cũng sẽ thực hiện thay đổi tương tự đối với loại subjectOf.

{-# LANGUAGE StandaloneDeriving #-} 
{-# LANGUAGE RankNTypes #-} 
{-# LANGUAGE GADTs #-} 
module Test where 

class ExprSYM repr where 
    expr :: (forall proc. ProcSYM proc => proc Int) -> repr 

class ProcSYM repr where 
    varProc :: forall a. String -> repr a 
    intProc :: String -> repr Int 
    subjectOf :: (forall expr. ExprSYM expr => expr) -> repr Int 

-- Tagged representation for ExprSYM 
data ExprSYM' where 
    Expr :: ProcSYM' Int -> ExprSYM' 
deriving instance Show ExprSYM' 

instance ExprSYM ExprSYM' where 
    expr x = Expr x -- chooses that the ProcSYM proc => proc Int must be ProcSYM' Int 

-- Tagged representation for ProcSYM 
data ProcSYM' a where 
    VarProc :: String -> ProcSYM' a 
    IntProc :: String -> ProcSYM' a 
    SubjectOf :: ExprSYM' -> ProcSYM' Int 

deriving instance Show (ProcSYM' a) 

instance ProcSYM ProcSYM' where 
    varProc = VarProc 
    intProc = IntProc 
    subjectOf x = SubjectOf x -- chooses that the ExprSYM repr => repr must be ExprSYM' 

-- myProc and myExpr with explicit type signatures 
myProc :: ProcSYM repr => repr Int 
myProc = intProc "proc A." 

myExpr :: ExprSYM repr => repr 
myExpr = expr myProc 

main = print (myExpr :: ExprSYM') 

Kết quả này là cây cú pháp trừu tượng cho myExpr. Chúng ta có thể thấy rằng nếu việc triển khai expr muốn phá hủy giá trị ProcSYM proc => proc Int thì có thể (và trong trường hợp này) đã cung cấp một từ điển ProcSYM để xây dựng các giá trị mà nó biết cách giải mã. Chúng ta có thể thấy điều này trong hàm tạo IntProc trong giá trị được hiển thị.

Expr (IntProc "proc A.")