Loại chứng minh thể hiện của gia đình có thể được chứng minh không?

Question

Đầu tiên, tôi bắt đầu với một số công cụ số tự nhiên cấp điển hình.

{-# LANGUAGE KindSignatures #-} 
{-# LANGUAGE DataKinds #-} 
{-# LANGUAGE GADTs #-} 
{-# LANGUAGE TypeFamilies #-} 

data Nat = Z | S Nat 

type family Plus (n :: Nat) (m :: Nat) :: Nat 
type instance Plus Z m = m 
type instance Plus (S n) m = S (Plus n m) 

Vì vậy, tôi muốn tạo kiểu dữ liệu đại diện cho lưới n chiều. (Một khái quát về những gì được tìm thấy ở Evaluating cellular automata is comonadic.)

data U (n :: Nat) x where 
    Point  :: x       -> U Z  x 
    Dimension :: [U n x] -> U n x -> [U n x] -> U (S n) x 

Ý tưởng là loại U num x là loại một num lưới ba chiều của x s, đó là "tập trung" vào một điểm cụ thể trong lưới .

Vì vậy, tôi muốn thực hiện điều này một comonad, và tôi nhận thấy rằng có chức năng này có khả năng hữu ích tôi có thể làm:

ufold :: (x -> U m r) -> U n x -> U (Plus n m) r 
ufold f (Point x) = f x 
ufold f (Dimension ls mid rs) = 
    Dimension (map (ufold f) ls) (ufold f mid) (map (ufold f) rs) 

Bây giờ chúng ta có thể thực hiện một "khía cạnh tham gia" có thể biến một lưới n-chiều của m-chiều lưới thành một lưới (ba +) chiều, trong điều khoản của tổ hợp này. Điều này sẽ có ích khi xử lý kết quả của cojoin sẽ tạo ra lưới của lưới.

dimJoin :: U n (U m x) -> U (Plus n m) x 
dimJoin = ufold id 

Cho đến nay rất tốt. Tôi cũng nhận thấy rằng phiên bản Functor có thể được viết theo số ufold.

instance Functor (U n) where 
    fmap f = ufold (\x -> Point (f x)) 

Tuy nhiên, điều này dẫn đến lỗi loại.

Couldn't match type `n' with `Plus n 'Z' 

Nhưng nếu chúng ta roi lên một số mì ống sao chép thì lỗi loại sẽ biến mất.

instance Functor (U n) where 
    fmap f (Point x) = Point (f x) 
    fmap f (Dimension ls mid rs) = 
    Dimension (map (fmap f) ls) (fmap f mid) (map (fmap f) rs) 

Tôi ghét mùi vị của mì ống sao chép, vì vậy câu hỏi của tôi là như vậy. Tôi làm cách nào để thông báo cho hệ thống loại Plus n Z bằng n? Và bắt là điều này: bạn không thể thực hiện thay đổi đối với các thể loại gia đình kiểu sẽ gây ra dimJoin để tạo ra lỗi loại tương tự.

Answer 1

Những gì bạn cần là một mệnh đề loại bình đẳng đẹp:

{-# LANGUAGE KindSignatures #-} 
{-# LANGUAGE DataKinds #-} 
{-# LANGUAGE PolyKinds #-} 
{-# LANGUAGE GADTs #-} 
{-# LANGUAGE TypeFamilies #-} 
{-# LANGUAGE TypeOperators #-} 

data Nat = Z | S Nat 

type family Plus (n :: Nat) (m :: Nat) :: Nat 
type instance Plus Z m = m 
type instance Plus (S n) m = S (Plus n m) 

data (:=) :: k -> k -> * where 
    Refl :: a := a 

data Natural (n :: Nat) where 
    Zero :: Natural Z 
    Suc :: Natural n -> Natural (S n) 

plusZero :: Natural n -> n := (n `Plus` Z) 
plusZero Zero = Refl 
plusZero (Suc n) | Refl <- plusZero n = Refl 

này cho phép bạn để chứng minh điều độc đoán về các loại của bạn và mang lại cho rằng kiến ​​thức vào phạm vi cục bộ bằng mô hình kết hợp trên Refl.

Một điều khó chịu là bằng chứng plusZero yêu cầu cảm ứng tự nhiên được đề cập, bạn sẽ không thể thực hiện theo mặc định (vì nó không tồn tại khi chạy). Tuy nhiên, một chiếc máy đánh chữ để tạo ra các nhân chứng Natural sẽ dễ dàng.

Một tùy chọn khác cho trường hợp cụ thể của bạn có thể chỉ là đảo ngược đối số sang cộng với định nghĩa loại để bạn có được Z ở bên trái và nó giảm tự động. Nó thường là một bước đầu tiên tốt để đảm bảo các loại của bạn đơn giản như bạn có thể tạo ra chúng, nhưng sau đó bạn sẽ thường cần sự bình đẳng theo mệnh đề cho những thứ phức tạp hơn, bất kể.