Lý thuyết loại: loại các loại

Question

Tôi đã đọc rất nhiều điều thú vị về các loại loại, loại cao cấp hơn, v.v. Theo mặc định Haskell hỗ trợ hai loại loại:

• loại đơn giản: *
• Loại constructor: * → *

GHC của mở rộng ngôn ngữ mới nhất ConstraintKinds thêm một loại mới:

• Loại tham số ràng buộc: Constraint

Ngoài ra sau khi đọc this mailing list nó trở nên rõ ràng rằng một loại loại có thể tồn tại, nhưng nó không được hỗ trợ bởi GHC (nhưng hỗ trợ như vậy được thực hiện trong NET):

• Hộp Bọc loại: #

Tôi đã tìm hiểu về polymorphic kinds và tôi nghĩ rằng tôi hiểu ý tưởng. Ngoài ra Haskell hỗ trợ định lượng một cách rõ ràng.

Vì vậy, câu hỏi của tôi là:

• làm bất kỳ loại khác của các loại tồn tại?
• Có bất kỳ tính năng ngôn ngữ khác được đánh dấu lại nào không?
• subkinding có nghĩa là gì? Nó được triển khai/hữu ích ở đâu?
• Có hệ thống kiểu nào ở trên cùng của kinds, như kinds là hệ thống kiểu ở trên cùng của types không? (chỉ quan tâm)

Answer 1

Vâng, các loại khác tồn tại. Trang Intermediate Types mô tả các loại khác được sử dụng trong GHC (bao gồm cả các loại không có hộp và một số loại phức tạp hơn nữa). Ngôn ngữ Ωmega có các loại cao cấp hơn với phần mở rộng hợp lý tối đa, cho phép các loại người dùng xác định (và các loại, và cao hơn). This page đề xuất một loại mở rộng hệ thống cho GHC cho phép người dùng xác định các loại trong Haskell, cũng như một ví dụ tốt về lý do tại sao chúng hữu ích.

Là một trích đoạn ngắn, giả sử bạn muốn có một kiểu danh sách trong đó có một chú thích loại cấp độ dài của danh sách, như thế này:

data Zero 
data Succ n 

data List :: * -> * -> * where 
    Nil :: List a Zero 
    Cons :: a -> List a n -> List a (Succ n) 

Mục đích là các đối số kiểu cuối cùng chỉ nên Zero hoặc Succ n, trong đó n chỉ một lần nữa là Zero hoặc Succ n. Tóm lại, bạn cần giới thiệu một loại mới, được gọi là Nat chỉ chứa hai loại Zero và Succ n. Sau đó, List datatype có thể bày tỏ rằng đối số cuối cùng không phải là một *, nhưng một Nat, như

data List :: * -> Nat -> * where 
    Nil :: List a Zero 
    Cons :: a -> List a n -> List a (Succ n) 

này sẽ cho phép kiểm tra kiểu được nhiều hơn nữa phân biệt trong những gì nó chấp nhận, cũng như làm cho loại cấp lập trình nhiều ý nghĩa hơn.

Answer 2

Giống như các loại được phân loại theo loại, loại được phân loại theo loại.

Ωmega programming language có hệ thống loại với các loại người dùng có thể xác định ở mọi cấp độ. (Vì vậy, nói wiki của nó. Tôi nghĩ rằng nó đề cập đến các loại và các cấp trên, nhưng tôi không chắc chắn.)

Answer 3

Đã có đề xuất nâng loại ở cấp loại và giá trị vào cấp loại. Nhưng tôi không biết nếu điều đó đã được thực hiện (hoặc nếu nó bao giờ sẽ đạt "giờ vàng")

Xét đoạn mã sau:

data Z 
data S a 

data Vec (a :: *) (b :: *) where 
    VNil :: Vec Z a 
    VCons :: a -> Vec l a -> Vec (S l) a 

Đây là một Vector có nó chiều mã hóa trong các kiểu. Chúng tôi đang sử dụng Z và S để tạo ra số tự nhiên.Đó là loại tốt đẹp nhưng chúng ta không thể "đánh dấu" nếu chúng ta sử dụng đúng loại khi tạo ra một Vec (chúng ta có thể vô tình chuyển đổi chiều dài một kiểu nội dung) và chúng ta cũng cần tạo kiểu S và Z, điều bất tiện nếu chúng ta định nghĩa các con số tự nhiên như vậy:

data Nat = Z | S Nat 

với đề xuất này bạn có thể viết một cái gì đó như thế này:

data Nat = Z | S Nat 

data Vec (a :: Nat) (b :: *) where            
    VNil :: Vec Z a 
    VCons :: a -> Vec l a -> Vec (S l) a 

này sẽ nâng Nat vào mức độ tử tế và S và Z vào mức loại nếu cần thiết. Vì vậy, Nat là một loại khác và sống trên cùng một mức độ như *.

Dưới đây là phần trình bày của Brent Yorgey

Typed type-level functional programming in GHC