Apa perbedaan antara ADT, GADT, dan tipe induktif?

Mungkin ada yang bisa menjelaskan perbedaan antara:

Datatypes aljabar (yang saya kenal)
Datatypes Aljabar Umum (apa yang membuat mereka digeneralisasikan?)
Jenis Induktif (mis. Coq)

(Terutama tipe induktif.) Terima kasih.

lo.logic pl.programming-languages type-theory dependent-type ninjagecko
sumber

Jawaban:

Tipe data aljabar memungkinkan Anda mendefinisikan tipe secara rekursif. Konkretnya, misalkan kita memiliki tipe data

d Sebuah t Sebuah l saya s t = N saya l | C Hai n s Hai f N \times l saya s t

$\mathsf{data\;list = Nil \;\;|\;\; Cons\;of\;\mathbb{N} \times list}$

Apa artinya ini adalah bahwa adalah himpunan terkecil dihasilkan oleh dan operator. Kita dapat memformalkan ini dengan mendefinisikan operator $\mathsf{list}$ $\mathsf{Nil}$ $\mathsf{Cons}$ $F(X)$

F (X) == {N saya l} \cup {C Hai n s (n, x) | n \in N \land x \in X}

$F(X) == \{ \mathsf{Nil} \} \cup \{ \mathsf{Cons}(n, x) \;|\; n \in \mathbb{N} \land x \in X \}$

dan kemudian mendefinisikan sebagai $\mathsf{list}$

l saya s t = ⋃_{saya \in N} F^{saya} (\emptyset)

$\mathsf{list} = \bigcup_{i \in \mathbb{N}} F^i(\emptyset)$

Sebuah umum ADT adalah apa yang kita dapatkan ketika menentukan jenis operator yang secara rekursif. Sebagai contoh, kita dapat mendefinisikan konstruktor tipe berikut:

b kamu s h Sebuah = L. e Sebuah f Hai f Sebuah | N e s t Hai f b kamu s h (Sebuah \times Sebuah)

$\mathsf{bush}\;a = \mathsf{Leaf\;of\;}a \;\;|\;\; \mathsf{Nest\;of\;bush}(a \times a)$

Tipe ini berarti bahwa elemen adalah tuple dari s panjang untuk beberapa , karena setiap kali kita pergi ke konstruktor jenis argumen dipasangkan dengan dirinya sendiri. Jadi kita dapat mendefinisikan operator yang ingin kita gunakan sebagai: $\mathsf{bush\;}a$ $a$ $2^n$ $n$ $\mathsf{Nest}$

F (R) = λ X . {L. e Sebuah f (x) | x \in X} \cup {N e s t (v) | v \in R (X)}

$F(R) = \lambda X.\; \{ \mathsf{Leaf}(x) \;|\; x \in X\} \cup \{ \mathsf{Nest}(v) \;|\; v \in R(X) \}$

Tipe induktif dalam Coq pada dasarnya adalah GADT, di mana indeks operator tipe tidak terbatas pada tipe lain (seperti dalam, misalnya, Haskell), tetapi juga dapat diindeks oleh nilai -nilai teori tipe. Ini memungkinkan Anda memberikan tipe untuk daftar panjang indeks, dan sebagainya.

Neel Krishnaswami
sumber

Terima kasih. Bukankah itu hanya berarti, bahwa "tipe induktif" sepenuhnya identik dengan "tipe dependen"?

ninjagecko

@Neel: Saya belum pernah melihat tipe seperti bushdisebut GADT. Saya telah melihat mereka disebut tipe bersarang atau tidak biasa.

jbapple

Jenis bersarang adalah kasus khusus dari GADT. Fitur penting dari GADT adalah bahwa itu adalah definisi rekursif pada jenis yang lebih tinggi. (Perubahan pada rhs pada dasarnya adalah gula sintaksis untuk menambahkan kesetaraan tipe sebagai komponen konstruktor.)

Neel Krishnaswami

@ninjagecko: "Tipe induktif" adalah tipe yang diberi semantik sebagai titik paling tidak tetap dari konstruktor. Tidak semua tipe dapat dideskripsikan dengan cara ini (fungsi tidak bisa, dan tidak ada tipe yang tak terbatas seperti stream). Tipe dependen menggambarkan tipe yang memungkinkan term program muncul di dalamnya (yaitu, tipe dapat "bergantung pada" istilah). Karena Coq adalah teori tipe dependen, tipe induktif yang Anda gunakan dapat Anda tentukan juga tergantung. Tetapi teori tipe non-dependen dapat mendukung tipe induktif juga, dan tipe induktif itu tidak akan bergantung.

Neel Krishnaswami

@NeelKrishnaswami: Apakah Anda akan berbaik hati untuk mengklarifikasi jawaban Anda dengan menyebutkan elemen "beberapa terkecil pertama" dari jenis bush a? Dalam contoh ini, apakah itu Nest Leaf(a) Leaf(a) Leaf(a) Leaf(a), atau Nest ((Nest Leaf(a) Leaf(a)) (Nest Leaf(a) Leaf(a)))sebagai salah satu contoh set?

ninjagecko

Pertimbangkan tipe data aljabar seperti:

data List a = Nil | Cons a (List a)

Jenis pengembalian setiap konstruktor dalam tipe data semuanya sama: Nildan Conskeduanya kembali List a. Jika kami mengizinkan konstruktor untuk mengembalikan jenis yang berbeda, kami memiliki GADT :

data Empty -- this is an empty data declaration; Empty has no constructors
data NonEmpty

data NullableList a t where
    Vacant :: NullableList a Empty
    Occupied :: a -> NullableList a b -> NullableList a NonEmpty

Occupiedmemiliki tipe a -> NullableList a b -> NullableList a NonEmpty, sementara Consmemiliki tipe a -> List a -> List a. Penting untuk dicatat bahwa itu NonEmptyadalah tipe, bukan istilah. Contoh lain:

data Zero
data Succ n

data SizedList a t where
    Alone :: SizedList a Zero
    WithFriends :: a -> SizedList a n -> SizedList a (Succ n)

Tipe induktif dalam bahasa pemrograman yang memiliki tipe dependen memungkinkan tipe kembalinya konstruktor bergantung pada nilai (bukan hanya tipe) dari argumen.

Inductive Parity := Even | Odd.

Definition flipParity (x:Parity) : Parity :=
  match x with
    | Even => Odd
    | Odd => Even
  end.

Fixpoint getParity (x:nat) : Parity :=
  match x with
    | 0 => Even
    | S n => flipParity (getParity n)
  end.

(*
A ParityNatList (Some P) is a list in which each member
is a natural number with parity P.
*)

Inductive ParityNatList : option Parity -> Type :=
  Nil : forall P, ParityNatList P
| Cons : forall (x:nat) (P:option Parity), 
  ParityNatList P -> ParityNatList 
  (match P, getParity x with
     | Some Even, Even => Some Even
     | Some Odd, Odd => Some Odd
     | _, _ => None
   end).

Catatan tambahan: GHC memiliki mekanisme untuk memperlakukan konstruktor nilai sebagai konstruktor tipe . Ini tidak sama dengan tipe induktif dependen yang dimiliki Coq, tetapi agak mengurangi beban sintaksis GADT, dan ini dapat menyebabkan pesan kesalahan yang lebih baik.

jbapple
sumber

Terima kasih. "Tipe induktif dalam bahasa pemrograman yang memiliki tipe dependen" Lalu, bagaimana tipe induktif akan terlihat seperti dalam bahasa tanpa tipe dependen, dan dapatkah Anda memiliki tipe dependen non-induktif (tetapi mirip GADT)?

ninjagecko