Wykorzystanie rzeczywistego świata GADT

Question

Czy istnieje jakiś dobry zasób na prawdziwe wykorzystanie uogólnionego typu danych algebraicznych?

Przykład podany w haskell wikibook jest zbyt krótki, aby dać mi wgląd w rzeczywiste możliwości GADT.

Dzięki

Answer 1

Znalazłem Monadę "Monit" (z pakietu "MonadPrompt") bardzo przydatne narzędzie w kilku miejscach (wraz z odpowiednikiem "Program" monada z pakietu "operacyjnego" .W połączeniu z GADTs (który jest w jaki sposób miał być używany), pozwala na tworzenie języków wbudowanych bardzo tanio i bardzo elastycznie. "W" Monad Reader issue 15 "w" Przygodach w trzech monadach "był całkiem niezły artykuł, który miał dobre wprowadzenie do monitu Prompt wraz z niektórymi realistyczne GADTs

Answer 2

Jest to krótka odpowiedź, ale zapoznać się z Haskell Wikibook. Przechodzi przez GADT dla dobrze wypisanego drzewa wyrażeń, które jest dość kanonicznym przykładem: http://en.wikibooks.org/wiki/Haskell/GADT

GADT służą również do implementacji równości typu: http://hackage.haskell.org/package/type-equality. Nie mogę znaleźć odpowiedniego papieru, który mógłby się do tego odnieść - ta technika trafiła już do folkloru. Jest on jednak dość dobrze wykorzystywany w typowych bez tagów Olega. Zobacz, np. sekcja dotycząca wpisanej kompilacji do GADT. http://okmij.org/ftp/tagless-final/#tc-GADT

Answer 3

Podobał mi się przykład z the GHC manual. Jest to szybkie pokazanie podstawowego pomysłu GADT: możesz osadzić system typów języka, którym manipulujesz, w systemie typu Haskella, dzięki czemu twoje funkcje Haskella będą zakładać, i zmusza je do zachowania, że ​​drzewa składniowe odpowiadają dobrze napisanym programom.

Kiedy definiujemy Term, nie ma znaczenia, jakie typy wybieramy. Moglibyśmy napisać

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

lub

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

i definicja Term nadal przechodzą.

To tylko raz chcemy obliczeniowych naTerm, tak jak w definiowaniu eval, że typy znaczenia. Musimy

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

ponieważ musimy naszą rekurencyjne wywołanie eval do zwracania Int i chcemy z kolei zwracają Bool.

Answer 4

GADT mogą dawać ci silniejsze gwarancje na typ niż zwykłe ADT. Na przykład, można wymusić binarne drzewo być zrównoważony na poziomie systemu typu, jak w this implementation z 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 

Każdy węzeł ma typ kodowane głębokości, gdzie wszystkie jego liście pobytu. Drzewo jest wtedy albo puste drzewo, wartość singleton, albo węzeł o nieokreślonej głębokości, ponownie przy użyciu GADTs.

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

System typów gwarantuje, że można zbudować tylko zbalansowane węzły. Oznacza to, że podczas wykonywania operacji takich jak insert na takich drzewach, Twój typ kodu sprawdza tylko wtedy, gdy jego wynik jest zawsze zrównoważonym drzewem.

Answer 5

GADT to słabe przybliżenia rodzin indukcyjnych z języków zależnych, więc zacznijmy od tego.

Rodziny indukcyjne są podstawową metodą wprowadzania typów danych w języku zależnym. Na przykład, w Agda zdefiniowaniu liczby naturalne jak ten

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

który nie jest bardzo fantazyjne, to w zasadzie tylko samo jak definicja Haskell

data Nat = Zero | Succ Nat 

i rzeczywiście w GADT Składnia Haskell formularz jest jeszcze bardziej podobny

{-# LANGUAGE GADTs #-} 

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

Tak więc, na pierwszy rzut oka może się wydawać, że GADT to po prostu schludna, dodatkowa składnia. To tylko wierzchołek góry lodowej.

---

Agda może reprezentować wszelkiego rodzaju typy nieznane i dziwne programistom Haskella. Prosty to rodzaj skończonych zbiorów. Ten typu jest napisany jak Fin 3 i reprezentuje zestaw o numerze o numerach {0, 1, 2}. Podobnie, Fin 5 reprezentuje zbiór liczb {0,1,2,3,4}.

To powinno być dość dziwne w tym momencie. Po pierwsze, mamy na myśli typ, który ma zwykły numer jako parametr "typ". Po drugie, nie jest jasne, co to oznacza, że ​​Fin n reprezentuje zestaw {0,1...n}. W prawdziwym Agda chcielibyśmy zrobić coś mocniejszego, ale wystarczy powiedzieć, że możemy zdefiniować contains funkcję

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

Teraz jest to dziwne, bo znowu „naturalna” definicja contains byłoby coś i < n, ale n jest wartością, która istnieje tylko w typie Fin n i nie powinniśmy być w stanie tak łatwo przekroczyć tego podziału. O ile okazuje się, że definicja nie jest tak prosta, jest to właśnie siła, jaką mają rodziny indukcyjne w zależnych od siebie językach - wprowadzają wartości zależne od ich typów i typów zależnych od ich wartości.

---

Możemy sprawdzić, co to jest o Fin, która nadaje mu tę właściwość, patrząc na jej definicję.

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

zajmuje to trochę pracy, aby zrozumieć, tak przykładem spróbujmy konstruowania wartości typu Fin 2. Istnieje kilka sposobów, aby to zrobić (w rzeczywistości, dowiemy, że nie są dokładnie 2)

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

To pozwala nam zobaczyć, że istnieją dwa mieszkańców, a także pokazuje, trochę jak rodzaj obliczeń dzieje. W szczególności bit (n : Nat) w typie zerof odzwierciedla rzeczywistą wartość o wartościn w typie umożliwiającym utworzenie Fin (n+1) dla dowolnego n : Nat.Następnie używamy powtórnych aplikacji succf, aby zwiększyć nasze wartości Fin do odpowiedniego indeksu rodziny typów (liczba naturalna, która indeksuje Fin).

Co zapewnia te umiejętności? Szczerze mówiąc, istnieje wiele różnic między zależnie wpisaną rodziną indukcyjną a zwykłym ADT Haskella, ale możemy skupić się na tym, który jest najbardziej odpowiedni dla zrozumienia GADT.

W GADTach i rodzinach indukcyjnych można określić dokładny typ konstruktorów dla konkretnego. Może to być nudne

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

Lub, jeśli mamy bardziej elastyczny, indeksowane typ możemy wybrać inne, bardziej interesujące typy powrotne

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

W szczególności jesteśmy nadużywa zdolność do modyfikowania typ zwracany oparty na używanym konstrukcie wartości , konkretnym. To pozwala nam odzwierciedlić niektóre informacje o wartościach w typie i uzyskać bardziej precyzyjnie sprecyzowane (fibered).

---

Co możemy z nimi zrobić? Cóż, z odrobiną smaru kolanowego możemy produce Fin in Haskell. Zwięźle to wymaga od nas zdefiniowania pojęcia Naturals typów

data Z 
data S a = S a 

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

... potem GADT aby odzwierciedlały wartości aż do tych typów ...

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

... wtedy możemy z nich korzystać budować Fin podobnie jak to miało miejsce w Agda ...

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

I wreszcie możemy skonstruować dokładnie dwie wartości 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)) 

Ale zauważ, że straciliśmy dużo wygody w stosunku do rodzin indukcyjnych. Na przykład, nie możemy używać zwykłych liczbowych literałów w naszych typach (chociaż to technicznie tylko sztuczka w Agdzie), musimy stworzyć osobny "typ nat" i "value nat" i użyć GADT, aby połączyć je ze sobą, Z czasem odkryjemy, że matematyka na poziomie typu jest bolesna w Agdzie. W Haskell jest to niezwykle bolesne i często nie może.

Na przykład, możliwe jest zdefiniowanie weaken pojęcie w Agda za Fin typu

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

gdzie zapewniamy bardzo ciekawy pierwszą wartość, dowód, że n <= m co pozwala nam umieścić „wartość mniejszą niż n” w zestawie "wartości mniejszych niż m". Możemy zrobić to samo w Haskell, technicznie, ale wymaga to dużego nadużywania prologu klasy.

---

Więc GADTs to podobieństwo rodzin indukcyjnych w sposób zależny wpisywanych języków, które są słabsze i nieporadnego. Dlaczego w pierwszej kolejności chcemy ich w Haskell?

Zasadniczo nie wszystkie niezmienniki typu wymagają pełnej mocy rodzin indukcyjnych do wyrażania, a GADTy wybierają konkretny kompromis między ekspresyjnością, możliwościami zastosowania w Haskell i wnioskiem typu.

Niektóre przykłady użytecznych wyrażeń GADT to Red-Black Trees which cannot have the Red-Black property invalidated lub simply-typed lambda calculus embedded as HOAS piggy-backing off the Haskell type system.

W praktyce często widzisz, że GADT używają ich domniemanych kontekstów egzystencjalnych. Na przykład, typ

data Foo where 
    Bar :: a -> Foo 

domyślnie ukrywa zmienną a typu przy użyciu kwantyfikator egzystencjalny

> :t Bar 4 :: Foo 

w sposób, który jest czasem wygodne. Jeśli przyjrzysz się uważnie przykładowi HOAS z Wikipedii, użyjesz tego dla parametru typu a w konstruktorze App. Wyrażenie tego stwierdzenia bez GADT byłoby bałaganem kontekstów egzystencjalnych, ale składnia GADT czyni je naturalnym.