Tên liên kết trong chữ ký loại sử dụng DataKind

Question

Vì vậy, cuối cùng tôi đã tìm thấy một tác vụ mà tôi có thể sử dụng phần mở rộng DataKinds mới (sử dụng ghc 7.4.1). Đây là Vec Tôi đang sử dụng:

data Nat = Z | S Nat deriving (Eq, Show) 

data Vec :: Nat -> * -> * where 
    Nil :: Vec Z a 
    Cons :: a -> Vec n a -> Vec (S n) a 

Bây giờ, để thuận tiện tôi muốn thực hiện fromList. Về cơ bản không có vấn đề với đệ quy đơn giản/fold - nhưng tôi không thể tìm ra cách để cho nó đúng loại. Để tham khảo, đây là phiên bản Agda:

fromList : ∀ {a} {A : Set a} → (xs : List A) → Vec A (List.length xs) 

My Haskell cách tiếp cận, sử dụng cú pháp tôi thấy here:

fromList :: (ls :: [a]) -> Vec (length ls) a 
fromList [] = Nil 
fromList (x:xs) = Cons x (fromList xs) 

này mang lại cho tôi một parse error on input 'a'. Cú pháp tôi tìm thấy có chính xác không, hoặc họ đã thay đổi nó chưa? Tôi cũng đã thêm một số tiện ích mở rộng khác có trong mã trong liên kết, điều này không giúp được gì (hiện tại tôi có GADTs, DataKinds, KindSignatures, TypeOperators, TypeFamilies, UndecidableInstances).

nghi ngờ khác của tôi là tôi chỉ không thể ràng buộc kiểu đa hình, nhưng thử nghiệm của tôi cho điều này:

bla :: (n :: Nat) -> a -> Vec (S n) a 
bla = undefined 

thất bại, quá, với Kind mis-match Expected kind 'ArgKind', but 'n' has kind 'Nat' (thật sự không biết điều đó có nghĩa).

Có ai có thể giúp tôi với phiên bản làm việc của fromList và cũng làm rõ các vấn đề khác không? Thật không may, DataKinds không được tài liệu rất tốt và dường như giả định rằng tất cả mọi người sử dụng nó có kiến ​​thức lý thuyết loại sâu sắc.

Answer 1

Haskell, không giống như Agda, không có loại phụ thuộc, vì vậy không có cách nào để thực hiện chính xác những gì bạn muốn. Các kiểu không thể được tham số hóa theo giá trị, vì Haskell thực thi một sự phân biệt pha giữa thời gian chạy và thời gian biên dịch. Cách DataKinds hoạt động khái niệm thực sự thực sự đơn giản: các kiểu dữ liệu được quảng cáo cho các loại (loại kiểu) và trình tạo dữ liệu được quảng bá cho các loại.

fromList :: (ls :: [a]) -> Vec (length ls) a 

có một vài vấn đề: (ls :: [a]) không thực sự có ý nghĩa (ít nhất là khi bạn chỉ giả mạo các loại phụ thuộc với chương trình khuyến mãi), và length là một loại biến thay vì một loại chức năng. Những gì bạn muốn nói là

fromList :: [a] -> Vec ??? a 

trong đó ??? là độ dài của danh sách. Vấn đề là bạn không có cách nào nhận được độ dài của danh sách tại thời gian biên dịch ... vì vậy chúng tôi có thể thử

fromList :: [a] -> Vec len a 

nhưng điều này là sai, vì nó nói rằng fromList có thể trả về một danh sách của bất kỳ chiều dài. Thay vào đó, điều chúng tôi muốn nói là

fromList :: exists len. [a] -> Vec len a 

nhưng Haskell không hỗ trợ điều này. Thay vào đó

data VecAnyLength a where 
    VecAnyLength :: Vec len a -> VecAnyLength a 

cons a (VecAnyLength v) = VecAnyLength (Cons a v) 

fromList :: [a] -> VecAnyLength a 
fromList []  = VecAnyLength Nil 
fromList (x:xs) = cons x (fromList xs) 

bạn thực sự có thể sử dụng một VecAnyLength bởi mô hình kết hợp, và do đó nhận được một giá trị (địa phương) psuedo-lệ thuộc gõ.

tương tự,

bla :: (n :: Nat) -> a -> Vec (S n) a 

không làm việc vì chức năng Haskell chỉ có thể đưa đối số của loại *. Thay vào đó bạn có thể thử

data HNat :: Nat -> * where 
    Zero :: HNat Z 
    Succ :: HNat n -> HNat (S n) 

bla :: HNat n -> a -> Ven (S n) a 

mà thậm chí còn định nghĩa

bla Zero a  = Cons a Nil 
bla (Succ n) a = Cons a (bla n a) 

Answer 2

Bạn có thể sử dụng một số phép thuật typeclass đây (xem HList để biết thêm):

{-# LANGUAGE GADTs, KindSignatures, DataKinds, FlexibleInstances 
    , NoMonomorphismRestriction, FlexibleContexts #-} 

data Nat = Z | S Nat deriving (Eq, Show) 

data Vec :: Nat -> * -> * where 
    Nil :: Vec Z a 
    Cons :: a -> Vec n a -> Vec (S n) a 

instance Show (Vec Z a) where 
    show Nil = "." 

instance (Show a, Show (Vec m a)) => Show (Vec (S m) a) where 
    show (Cons x xs) = show x ++ " " ++ show xs 

class FromList m where 
    fromList :: [a] -> Vec m a 

instance FromList Z where 
    fromList [] = Nil 

instance FromList n => FromList (S n) where 
    fromList (x:xs) = Cons x $ fromList xs 

t5 = fromList [1, 2, 3, 4, 5] 

nhưng điều này không thực sự giải quyết vấn đề :

> :t t5 
t5 :: (Num a, FromList m) => Vec m a 

Danh sách được hình thành trong thời gian chạy, thời gian của họ không được biết đến tại thời gian biên dịch, vì vậy trình biên dịch không thể suy ra kiểu cho t5, nó phải được xác định một cách rõ ràng:

*Main> t5 

<interactive>:99:1: 
    Ambiguous type variable `m0' in the constraint: 
     (FromList m0) arising from a use of `t5' 
    Probable fix: add a type signature that fixes these type variable(s) 
    In the expression: t5 
    In an equation for `it': it = t5 
*Main> t5 :: Vec 'Z Int 
*** Exception: /tmp/d.hs:20:3-19: Non-exhaustive patterns in function fromList 

*Main> t5 :: Vec ('S ('S ('S 'Z))) Int 
1 2 3 *** Exception: /tmp/d.hs:20:3-19: Non-exhaustive patterns in function fromList 

*Main> t5 :: Vec ('S ('S ('S ('S ('S 'Z))))) Int 
1 2 3 4 5 . 
*Main> t5 :: Vec ('S ('S ('S ('S ('S ('S ('S 'Z))))))) Int 
1 2 3 4 5 *** Exception: /tmp/d.hs:23:3-40: Non-exhaustive patterns in function fromList 

Ngôn ngữ với các loại phụ thuộc có bản đồ từ về các loại, loại có thể được hình thành động trong thời gian chạy quá, do đó, vấn đề này không tồn tại.