Việc sử dụng GADT thực tế trên thế giới

Question

Có tài nguyên nào tốt về việc sử dụng thực tế loại dữ liệu đại số tổng quát không?

Ví dụ được đưa ra trong haskell wikibook quá ngắn để cho tôi cái nhìn sâu sắc về khả năng thực sự của GADT.

Cảm ơn

Answer 1

Tôi đã tìm thấy đơn "Prompt" (từ gói "MonadPrompt") là một công cụ rất hữu ích ở một số nơi (cùng với đơn vị "Chương trình" tương đương từ gói "hoạt động". Kết hợp với GADT Có một bài báo khá hay trong số Monad Reader issue 15 được gọi là "Cuộc phiêu lưu trong ba Monads" có giới thiệu tốt về đơn nguyên Prompt cùng với một số Các mẫu GADT thực tế

Answer 2

Đây là câu trả lời ngắn nhưng hãy tham khảo Haskell Wikibook. Nó hướng dẫn bạn mặc dù một GADT cho một cây biểu thức được đánh máy tốt, đó là một ví dụ khá điển hình: http://en.wikibooks.org/wiki/Haskell/GADT

GADT cũng được sử dụng để thực hiện bình đẳng loại: http://hackage.haskell.org/package/type-equality. Tôi không thể tìm thấy giấy phù hợp để tham khảo cho điều này một cách tự nhiên - kỹ thuật này đã trở nên thành công trong văn hóa dân gian. Nó được sử dụng khá tốt, tuy nhiên, trong các công cụ vô giá trị của Oleg. Xem, ví dụ: phần biên soạn đã nhập vào GADT. http://okmij.org/ftp/tagless-final/#tc-GADT

Answer 3

Tôi thích ví dụ này trong the GHC manual. Đây là một bản demo nhanh về ý tưởng GADT cốt lõi: bạn có thể nhúng hệ thống kiểu của ngôn ngữ mà bạn đang thao tác vào hệ thống kiểu của Haskell. và buộc họ phải bảo tồn, rằng các cây cú pháp tương ứng với các chương trình được đánh máy tốt.

Khi chúng tôi xác định Term, chúng tôi chọn loại nào không quan trọng. Chúng tôi có thể viết

data Term a where 
    ... 
    IsZero :: Term Char -> Term Char 

hoặc

... 
    IsZero :: Term a -> Term b 

và định nghĩa của Term vẫn sẽ đi qua.

Chỉ một lần chúng tôi muốn tính toán trênTerm, chẳng hạn như trong việc xác định eval, các loại đó quan trọng. Chúng ta cần phải có

... 
    IsZero :: Term Int -> Term Bool 

vì chúng ta cần phải gọi đệ quy của chúng tôi để eval để trả lại một Int, và chúng tôi muốn lần lượt trả về một Bool.

Answer 4

GADT có thể cung cấp cho bạn bảo đảm thực thi loại mạnh mẽ hơn so với ADT thông thường. Ví dụ, bạn có thể buộc một cây nhị phân để được cân bằng về mức độ hệ thống kiểu, giống như trong this implementation của 2-3 trees:

{-# LANGUAGE GADTs #-} 

data Zero 
data Succ s = Succ s 

data Node s a where 
    Leaf2 :: a -> Node Zero a 
    Leaf3 :: a -> a -> Node Zero a 
    Node2 :: Node s a -> a -> Node s a -> Node (Succ s) a 
    Node3 :: Node s a -> a -> Node s a -> a -> Node s a -> Node (Succ s) a 

Mỗi nút có độ sâu loại mã hóa nơi mà tất cả lá của nó cư trú. Cây sau đó là hoặc cây trống, giá trị đơn hoặc một nút có chiều sâu không xác định, một lần nữa bằng GADT.

data BTree a where 
    Root0 :: BTree a 
    Root1 :: a -> BTree a 
    RootN :: Node s a -> BTree a 

Hệ thống kiểu đảm bảo với bạn rằng chỉ các nút cân bằng mới có thể được xây dựng. Điều này có nghĩa là khi triển khai các hoạt động như insert trên các cây như vậy, hãy kiểm tra loại mã chỉ khi kết quả của nó luôn là cây cân bằng.

Answer 5

GADT là các ước tính gần đúng của các gia đình quy nạp từ các ngôn ngữ được đánh máy phụ thuộc — vì vậy, hãy bắt đầu ở đó thay thế.

Gia đình quy nạp là phương pháp giới thiệu kiểu dữ liệu cốt lõi bằng ngôn ngữ được nhập phụ thuộc. Ví dụ, trong Agda bạn xác định các số tự nhiên như thế này

data Nat : Set where 
    zero : Nat 
    succ : Nat -> Nat 

mà không phải là rất ưa thích, đó là về cơ bản chỉ là những điều tương tự như định nghĩa Haskell

data Nat = Zero | Succ Nat 

và thực sự trong GADT cú pháp Haskell biểu mẫu thậm chí còn tương tự hơn

{-# LANGUAGE GADTs #-} 

data Nat where 
    Zero :: Nat 
    Succ :: Nat -> Nat 

Vì vậy, lúc đầu đỏ mặt bạn có thể nghĩ GADT chỉ là cú pháp bổ sung gọn gàng. Đó chỉ là đỉnh của tảng băng trôi.

---

Agda có khả năng thể hiện tất cả các loại không quen thuộc và lạ đối với người lập trình Haskell. Một cách đơn giản là loại tập hợp hữu hạn. Điều này loại được viết như Fin 3 và đại diện cho đặt của số {0, 1, 2}. Tương tự, Fin 5 đại diện cho tập hợp các số {0,1,2,3,4}.

Điều này khá kỳ lạ vào thời điểm này. Đầu tiên, chúng tôi đang đề cập đến một loại có số thường là thông số "loại". Thứ hai, không rõ ý nghĩa của nó đối với Fin n để đại diện cho tập hợp {0,1...n}. Trong Agda thực chúng tôi muốn làm điều gì đó mạnh mẽ hơn, nhưng nó cũng đủ để nói rằng chúng ta có thể định nghĩa một hàm contains

contains : Nat -> Fin n -> Bool 
contains i f = ? 

Bây giờ đây là kỳ lạ một lần nữa bởi vì "tự nhiên" định nghĩa của contains sẽ là một cái gì đó giống như i < n, nhưng n là một giá trị chỉ tồn tại trong loại Fin n và chúng tôi không thể vượt qua phân chia đó dễ dàng như vậy. Trong khi nó chỉ ra rằng định nghĩa gần như không đơn giản, đây chính là sức mạnh mà các gia đình quy nạp có trong các ngôn ngữ được đánh máy phụ thuộc - chúng giới thiệu các giá trị phụ thuộc vào kiểu và loại của chúng phụ thuộc vào giá trị của chúng.

---

Chúng tôi có thể kiểm tra xem nó là gì về số Fin cung cấp cho nó thuộc tính bằng cách xem định nghĩa của nó.

data Fin : Nat -> Set where 
    zerof : (n : Nat) -> Fin (succ n) 
    succf : (n : Nat) -> (i : Fin n) -> Fin (succ n) 

việc này cần một chút công việc để hiểu, ví dụ như cho phép thử tạo giá trị loại Fin 2. Có một số cách để làm điều này (trên thực tế, chúng ta sẽ thấy rằng có đúng 2)

zerof 1   : Fin 2 
zerof 2   : Fin 3 -- nope! 
zerof 0   : Fin 1 -- nope! 
succf 1 (zerof 0) : Fin 2 

Điều này cho phép chúng tôi thấy rằng có hai người dân và cũng chứng tỏ một chút kiểu tính toán sẽ xảy ra như thế nào. Cụ thể, các bit (n : Nat) trong loại zerof phản ánh giá trị thực tến tối đa vào loại cho phép chúng tôi tạo thành Fin (n+1) cho bất kỳ n : Nat nào.Sau đó, chúng tôi sử dụng các ứng dụng lặp đi lặp lại của succf để tăng giá trị Fin của chúng tôi vào chỉ mục chính xác kiểu gia đình (số tự nhiên lập chỉ mục Fin).

Điều gì cung cấp những khả năng này? Trong tất cả sự trung thực, có nhiều sự khác biệt giữa một gia đình cảm ứng được đánh máy phụ thuộc và một Haskell ADT thông thường, nhưng chúng ta có thể tập trung vào một cách chính xác nhất có liên quan đến việc hiểu GADT.

Trong GADT và gia đình quy nạp, bạn sẽ có cơ hội để chỉ định loại chính xác loại của các nhà thầu của bạn. Điều này có thể nhàm chán

data Nat where 
    Zero :: Nat 
    Succ :: Nat -> Nat 

Hoặc, nếu chúng ta có một, loại lập chỉ mục linh hoạt hơn chúng ta có thể lựa chọn, loại trở lại thú vị hơn khác nhau

data Typed t where 
    TyInt :: Int    -> Typed Int 
    TyChar :: Char    -> Typed Char 
    TyUnit ::      Typed() 
    TyProd :: Typed a -> Typed b -> Typed (a, b) 
    ... 

Đặc biệt, chúng ta đang lạm dụng khả năng thay đổi kiểu trả về dựa trên hàm tạo cụ thể được sử dụng. Điều này cho phép chúng tôi phản ánh một số thông tin giá trị vào loại và tạo ra được nhập rõ ràng hơn (có sợi).

---

Vậy chúng ta có thể làm gì với chúng? Vâng, với một chút mỡ khuỷu tay, chúng tôi có thể produce Fin in Haskell. Ngắn gọn nó đòi hỏi rằng chúng ta định nghĩa một khái niệm về bẩm trong các loại

data Z 
data S a = S a 

> undefined :: S (S (S Z)) -- 3 

... sau đó một GADT để phản ánh giá trị thành các loại ...

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

... sau đó chúng ta có thể sử dụng các để xây dựng Fin giống như chúng tôi đã làm trong Agda ...

data Fin n where 
    ZeroF :: Nat n -> Fin (S n) 
    SuccF :: Nat n -> Fin n -> Fin (S n) 

Và cuối cùng chúng ta có thể xây dựng một cách chính xác hai giá trị của Fin (S (S Z))

*Fin> :t ZeroF (Succ Zero) 
ZeroF (Succ Zero) :: Fin (S (S Z)) 

*Fin> :t SuccF (Succ Zero) (ZeroF Zero) 
SuccF (Succ Zero) (ZeroF Zero) :: Fin (S (S Z)) 

Nhưng lưu ý rằng chúng tôi đã mất rất nhiều sự tiện lợi trong các gia đình quy nạp. Ví dụ, chúng ta không thể sử dụng các chữ số thông thường trong các kiểu của chúng ta (mặc dù đó chỉ là một mẹo trong Agda), chúng ta cần tạo một "kiểu nat" riêng biệt và "giá trị nat" và sử dụng GADT để liên kết chúng với nhau, và chúng tôi cũng tìm thấy, trong thời gian, trong khi toán học cấp loại là đau đớn trong Agda nó có thể được thực hiện. Trong Haskell nó vô cùng đau đớn và thường không thể.

Ví dụ, nó có thể xác định một quan niệm weaken trong Agda của Fin loại

weaken : (n <= m) -> Fin n -> Fin m 
weaken = ... 

nơi mà chúng tôi cung cấp một giá trị đầu tiên rất thú vị, một bằng chứng cho thấy n <= m cho phép chúng tôi để nhúng "một giá trị nhỏ hơn n" vào tập hợp "giá trị nhỏ hơn m". Chúng ta có thể làm tương tự trong Haskell, về mặt kỹ thuật, nhưng nó đòi hỏi sự lạm dụng nặng nề của loại prolog.

---

Vì vậy, GADT giống với các ngôn ngữ quy nạp trong các ngôn ngữ phụ thuộc yếu hơn và nhỏ hơn. Tại sao chúng ta lại muốn chúng ở Haskell ngay từ đầu?Về cơ bản vì không phải tất cả các loại bất biến đòi hỏi toàn bộ sức mạnh của các gia đình quy nạp để thể hiện và GADT chọn một sự thỏa hiệp cụ thể giữa tính biểu cảm, khả năng thực hiện trong Haskell và suy luận kiểu.

Một số ví dụ về biểu thức GADT hữu ích là Red-Black Trees which cannot have the Red-Black property invalidated hoặc simply-typed lambda calculus embedded as HOAS piggy-backing off the Haskell type system.

Trong thực tế, bạn cũng thường thấy GADT sử dụng cho ngữ cảnh tiềm ẩn tiềm ẩn của chúng. Ví dụ, loại

data Foo where 
    Bar :: a -> Foo 

ngầm ẩn biến a loại sử dụng hiện sinh lượng

> :t Bar 4 :: Foo 

trong một cách mà đôi khi thuận tiện. Nếu bạn xem kỹ ví dụ HOAS từ Wikipedia, hãy sử dụng tham số này cho thông số loại a trong hàm tạo App. Để diễn đạt tuyên bố đó mà không có GADT sẽ là một mớ hỗn độn của các ngữ cảnh hiện hữu, nhưng cú pháp GADT làm cho nó trở nên tự nhiên.