Egzystencjalne vs. powszechnie kwantyfikowane typy w Haskell
Jaka dokładnie jest różnica między nimi? Myślę, że rozumiem jak działają typy egzystencjalne, są jak posiadanie klasy bazowej w OO bez sposobu na obniżenie obsady. Czym różnią się typy uniwersalne?
1 answers
Termin" uniwersalny "i" egzystencjalny " pochodzi tutaj od podobnie nazwanych kwantyfikatorów w logice predykatu.
Kwantyfikacja uniwersalna jest zwykle zapisywana jako ∀, które można odczytać jako "dla wszystkich" i oznacza mniej więcej to, jak to brzmi: w logicznym stwierdzeniu przypominającym "∀x...."cokolwiek jest na miejscu"..."jest prawdziwe dla wszystkich możliwych "x", które można wybrać z dowolnego zestawu rzeczy jest obliczana.
Egzystencjalny kwantyfikacja jest zwykle zapisywana jako∃, co można odczytać jako "istnieje" i oznacza, że w logicznym stwierdzeniu przypominającym " ∃x...."cokolwiek jest na miejscu"..."jest prawdą dla jakiegoś nieokreślonego" x " wziętego ze zbioru rzeczy wymiernych.
W Haskell, rzeczy są kwantyfikowane przez są typy (ignorując niektóre rozszerzenia językowe, co najmniej), nasze logiczne stwierdzenia są również typy, i zamiast być" prawdziwe "myślimy o" może być wdrożone".
Tak więc typ uniwersalny jak forall a. a -> a oznacza, że dla każdego możliwego typu " a " możemy zaimplementować funkcję, której typem jest a -> a. I rzeczywiście możemy:
id :: forall a. a -> a
id x = x
Ponieważ a jest powszechnie kwantyfikowane, nic o tym nie wiemy i dlatego nie możemy w żaden sposób zbadać argumentu. Więc id jest jedyną możliwą funkcją tego typu(1).
W Haskell, uniwersalna kwantyfikacja jest "domyślna" --dowolne zmienne typu w sygnaturze są w sposób niejawny powszechnie określany, dlatego typ id jest zwykle zapisywany jako po prostu a -> a. Jest to również znany jako polimorfizm parametryczny, często nazywany po prostu "polimorfizmem" w Haskell, a w niektórych innych językach (np. C#) znany jako "generics".
An egzystencjalnie kwantyfikowany typ jak exists a. a -> a oznacza, że dla jakiegoś konkretnego typu "a", możemy zaimplementować funkcję, której typem jest a -> a. Każda funkcja będzie działać, więc wybieram jeden:
func :: exists a. a -> a
func True = False
func False = True
...co jest oczywiście funkcją " not " na booleanach. Ale haczyk polega na tym, że nie możemy użyć jako takiego, ponieważ wszystko, co wiemy o typie "a", to to, że istnieje. Wszelkie informacje o , który typ może być został odrzucony, co oznacza, że nie możemy zastosować func do żadnych wartości.
Więc co możemy zrobić z func? Wiemy, że jest to funkcja o tym samym typie dla wejścia i wyjścia, więc możemy na przykład skomponować ją samą ze sobą. Zasadniczo jedyne rzeczy, które możesz zrobić z czymś, co ma typ egzystencjalny, to rzeczy, które możesz zrobić w oparciu o nieistniejące części tego typu. Podobnie, biorąc pod uwagę coś typu exists a. [a], możemy znaleźć jego długość, połączyć go z sobą, lub upuścić niektóre elementy, lub cokolwiek innego możemy zrobić z dowolną listą.
exists powyżej jest całkowicie fikcyjny, niestety): ponieważ rzeczy z typami egzystencjalnie kwantyfikowanymi mogą być używane tylko z operacjami, które mają powszechnie kwantyfikowane typy, możemy zapisać Typ exists a. a jako forall r. (forall a. a -> r) -> r--innymi słowy, dla wszystkich typów wyników r, biorąc pod uwagę funkcję, która dla wszystkich typów a przyjmuje argument typu a i zwraca wartość typu r, możemy uzyskać wynik typu r.}.
Jeśli nie jest dla Ciebie jasne, dlaczego są one prawie równoważne, zauważ, że ogólny typ nie jest powszechnie kwantyfikowany dla a -- raczej przyjmuje argument, który sam w sobie jest powszechnie kwantyfikowany dla a, który może następnie użyć z dowolnym wybranym typem.
Na marginesie, podczas gdy Haskell nie ma pojęcia podtypu w zwykłym znaczeniu, możemy traktować kwantyfikatory jako wyrażające formę podtypu, z hierarchią przechodzącą od uniwersalnej do konkretnej do egzystencjalnej. Coś typu forall a. a może być zamienione na dowolny inny typ, więc może być postrzegany jako podtyp wszystkiego; z drugiej strony, każdy typ może być konwertowany na typ exists a. a, co czyni go typem nadrzędnym wszystkiego. Oczywiście, pierwszy jest niemożliwy (nie ma wartości typu forall a. a z wyjątkiem błędów), a drugi jest bezużyteczny( nie można nic zrobić z typem exists a. a), ale analogia działa przynajmniej na papierze. :]
Zauważ, że równoważność między typem egzystencjalnym a uniwersalnym argumentem ilościowym działa dla tego samego powód, że wariancja obraca się dla wejść funkcji.
Tak więc, podstawową ideą jest z grubsza to, że powszechnie ilościowo typy opisują rzeczy, które działają tak samo dla każdego typu, podczas gdy typy egzystencjalne opisują rzeczy, które działają z określonym, ale nieznanym typem.
1: cóż, nie do końca-tylko wtedy, gdy ignorujemy funkcje, które powodują błędy, takie jak notId x = undefined, włączając w to funkcje, które nigdy się nie kończą, takie jak loopForever x = loopForever x.
2: GHC. Bez rozszerzenia, Haskell ma tylko Ukryte kwantyfikatory uniwersalne i nie ma realnego sposobu mówienia o typach egzystencjalnych w ogóle.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-01-13 02:10:52