Jaka jest różnica między typem a rodzajem?

26

Uczę się języka programowania Haskell i staram się owinąć głowę, jaka jest różnica między a typea a kind.

Jak rozumiem, a kind is a type of type. Na przykład a ford is a type of cari a car is a kind of vehicle.

Czy to dobry sposób, aby o tym pomyśleć?

Ponieważ sposób, w jaki mój mózg jest obecnie okablowany, a ford is a **type** of cartakże car is a **type** of vehicleprzez chwilę w tym samym czasie car is a **kind** of vehicle. Tj. Warunki typei kindsą wymienne.

Czy ktoś mógłby rzucić na to trochę światła?

Thomas Cook
źródło
6
Właśnie przyszedłem tutaj z postu na Stack Overflow, który doprowadził do tej dyskusji. Nie jestem pewien, czy mam kwalifikacje do udzielania szczegółowych odpowiedzi - ale zdecydowanie jesteś zbyt dosłowny w odniesieniu do terminów „typ” i „miły”, próbując powiązać je z ich znaczeniem w języku angielskim (gdzie w rzeczywistości są one synonimami ). Powinieneś traktować je jako warunki techniczne. „Typ” jest dobrze rozumiany przez wszystkich programistów, ponieważ zakładam, że jest on niezbędny w każdym języku, nawet w słabym typie, takim jak Javascript, „Rodzaj” jest terminem technicznym używanym w Haskell na określenie „rodzaju typu”. To naprawdę wszystko.
Robin Zigmond
2
@RobinZigmond: masz rację, ponieważ są to terminy techniczne, ale są one stosowane szerzej niż tylko w Haskell. Może link zwrotny do dyskusji o przepełnieniu stosu, która zrodziła to pytanie?
Andrej Bauer
@AndrejBauer Nigdy nie powiedziałem, że nie były używane poza Haskell, z pewnością „typ” jest używany w zasadzie w każdym języku, jak już powiedziałem. Tak naprawdę nigdy nie spotkałem „miłego” poza Haskell, ale Haskell jest jedynym funkcjonalnym językiem, jaki znam, i uważałem, aby nie powiedzieć, że termin ten nie jest używany gdzie indziej, tylko że jest używany w ten sposób w Haskell. (A link, jak
prosisz
Języki rodziny ML również mają swoje rodzaje, na przykład Standard ML i OCaml. Sądzę, że nie są jawnie ujawnione pod tym imieniem. Są manifestowane jako podpisy , a ich elementy nazywane są strukturami .
Andrej Bauer
1
Bardziej dokładna angielska analogia jest taka, że ​​Ford jest rodzajem samochodu, a samochód jest rodzajem pojazdów, ale zarówno typy samochodów, jak i typy pojazdów są tego samego rodzaju: rzeczowniki. Podczas gdy czerwony jest rodzajem koloru samochodu, a RPM jest rodzajem wskaźników wydajności samochodu i oba są tego samego rodzaju: przymiotniki.
slebetman

Odpowiedzi:

32

Tutaj „wartości”, „typy” i „rodzaje” mają znaczenie formalne, więc biorąc pod uwagę ich powszechne użycie w języku angielskim lub analogie do klasyfikacji samochodów, dotrzesz tylko do tej pory.

Moja odpowiedź dotyczy formalnego znaczenia tych terminów w kontekście Haskell; znaczenia te są oparte na (choć nie są tak naprawdę identyczne) znaczeniach używanych w matematycznej / CS „teorii typów”. Nie będzie to więc bardzo dobra odpowiedź „informatyczna”, ale powinna służyć jako całkiem dobra odpowiedź Haskella.

W języku Haskell (i innych językach) pomocne jest przypisanie typu do wyrażenia programu opisującego klasę wartości, jakie wyrażenie może posiadać. Zakładam, że widziałeś wystarczająco dużo przykładów, aby zrozumieć, dlaczego warto wiedzieć, że w wyrażeniu sqrt (a**2 + b**2)zmienne ai bzawsze będą wartościami typu, Doublea nie, powiedzmy, Stringi Boolodpowiednio. Zasadniczo posiadanie typów pomaga nam pisać wyrażenia / programy, które będą działać poprawnie w szerokim zakresie wartości .

Teraz możesz nie zdawać sobie sprawy, że typy Haskell, takie jak te, które pojawiają się w podpisach typów:

fmap :: Functor f => (a -> b) -> f a -> f b

tak naprawdę są napisane w podrzędnym języku Haskell. Tekst programu Functor f => (a -> b) -> f a -> f bjest - dosłownie - wyrażeniem typu napisanym w tym języku podrzędnym. Podjęzykiem obejmuje operatorów (np ->jest słuszną asocjacyjne operator infix w tym języku), zmienne (np f, ai b) oraz „Aplikacja” jednego wyrazu do drugiego typu (na przykład f ajest fstosowane do a).

Czy wspomniałem, jak w wielu językach pomocne było przypisywanie typów do wyrażeń programu w celu opisania klas wartości wyrażeń? Cóż, w tym podrzędnym języku typów wyrażenia oceniają na typy (a nie na wartości ), dlatego pomocne jest przypisywanie rodzajów do wyrażeń typu w celu opisania klas typów , które mogą reprezentować. Zasadniczo posiadanie rodzajów pomaga nam pisać wyrażenia typów, które będą działać poprawnie w szerokim zakresie typów .

Tak więc wartościtypu jako typy są do rodzajów i typów pomóc nam pisać wartość programów -level natomiast rodzaje pomóc nam pisać typu programów -level.

Jak wyglądają te rodzaje ? Rozważmy podpis typu:

id :: a -> a

Jeśli wyrażenie typu a -> ajest ważne, co niby od rodzaju powinniśmy pozwolić zmienna abyć? Cóż, wyrażenia typu:

Int -> Int
Bool -> Bool

wyglądać prawidłowy, więc typów Int i Boolsą oczywiście z prawej rodzaju . Ale nawet bardziej skomplikowane typy, takie jak:

[Double] -> [Double]
Maybe [(Double,Int)] -> Maybe [(Double,Int)]

wyglądać poprawnie. W rzeczywistości, ponieważ powinniśmy być w stanie wywoływać idfunkcje, nawet:

(a -> a) -> (a -> a)

wygląda w porządku. Więc Int, Bool, [Double], Maybe [(Double,Int)], a a -> awszystkie wyglądają jak typy z prawej rodzaju .

Innymi słowy, wygląda na to, że istnieje tylko jeden rodzaj , nazwijmy go *jak wieloznaczny uniks, a każdy typ ma ten sam rodzaj * , koniec historii.

Dobrze?

Cóż, niezupełnie. Okazuje się, że Maybesamo w sobie jest tak samo poprawnym wyrażeniem typu jak Maybe Int(w bardzo podobny sposób sqrt, samo w sobie, jest tak samo poprawnym wyrażeniem wartości jak sqrt 25). Jednak następujące wyrażenie typu jest nieprawidłowe:

Maybe -> Maybe

Ponieważ, gdy Maybejest wyrażeniem typu, nie stanowią swego rodzaju z rodzaju , które mogą mieć wartości. Tak, to w jaki sposób należy zdefiniować *- to rodzaj z typów , które mają wartości; zawiera „Complete” typy jak Doublei Maybe [(Double,Int)]ale nie obejmuje niekompletne, typy bezwartościowe podoba Either String. Dla uproszczenia nazywam te kompletne rodzaje *„konkretnymi typami”, chociaż terminologia ta nie jest uniwersalna, a „konkretne typy” mogą oznaczać coś zupełnie innego niż, powiedzmy, programista C ++.

Teraz w wyrażeniu typu a -> a, o ile typ ama rodzaj * (rodzaj konkretnych typów), wynik wyrażenia typu równieża -> a będzie miał rodzaj (tj. Rodzaj konkretnych typów). *

Więc co niby od typu jest Maybe? Cóż, Maybemożna go zastosować do rodzaju betonu, aby uzyskać inny rodzaj betonu. Tak, Maybewygląda jak mały jak rodzaj funkcji poziomu, że trwa typu o rodzaju * i zwraca typ z rodzaju * . Gdybyśmy mieli funkcję poziomu wartość, która odbyła się wartość od rodzaju Int i zwracana jest wartość o rodzaju Int , że damy mu rodzaj podpisu Int -> Int, więc przez analogię powinniśmy dać Maybesię rodzaj podpisu * -> *. GHCi zgadza się:

> :kind Maybe
Maybe :: * -> *

Wracam do:

fmap :: Functor f => (a -> b) -> f a -> f b

W podpisie tego typu zmienna fma rodzaj * -> *i zmienne aoraz bma rodzaj *; wbudowany operator ->ma rodzaj * -> * -> *(pobiera rodzaj *po lewej i jeden po prawej i zwraca również rodzaj *). Na podstawie tego i zasad wnioskowania rodzaju można wywnioskować, że a -> bjest to poprawny typ z rodzajem *, f aa f btakże są poprawne typy z rodzajem *i (a -> b) -> f a -> f bjest to poprawny typ rodzaju *.

Innymi słowy, kompilator może „sprawdzić rodzaj” wyrażenia typu, (a -> b) -> f a -> f baby sprawdzić, czy jest poprawny dla zmiennych typu właściwego rodzaju, w ten sam sposób, w jaki „sprawdza typ”, sqrt (a**2 + b**2)aby sprawdzić, czy jest poprawny dla zmiennych właściwego typu.

Powodem używania osobnych terminów „typy” i „rodzaje” (tj. Nie mówienie o „typach typów”) jest głównie po to, aby uniknąć zamieszania. Powyższe rodzaje wyglądają bardzo inaczej niż typy i przynajmniej na początku wydają się zachowywać zupełnie inaczej. (Na przykład, zajmuje trochę czasu, aby objąć głowę myślą, że każdy „normalny” typ ma ten sam rodzaj, *a taki nie a -> bjest .)** -> *

Niektóre z nich są również historyczne. W miarę ewolucji GHC Haskell różnice między wartościami, typami i rodzajami zaczęły się zacierać. W dzisiejszych czasach wartości można „promować” na typy, a typy i rodzaje są naprawdę takie same. Tak więc we współczesnym Haskell zarówno wartości mają typy, jak i typy ARE (prawie), a rodzaje typów to po prostu więcej typów.

@ user21820 poprosił o dodatkowe wyjaśnienie „typy i rodzaje są naprawdę takie same”. Żeby było trochę jaśniej, we współczesnym GHC Haskell (myślę, że od wersji 8.0.1) typy i rodzaje są traktowane jednakowo w większości kodu kompilatora. Kompilator dokłada starań, aby komunikaty o błędach rozróżniały „typy” i „rodzaje”, w zależności od tego, czy narzeka odpowiednio na typ wartości, czy typ.

Ponadto, jeśli żadne rozszerzenia nie są włączone, można je łatwo rozróżnić w języku powierzchniowym. Na przykład typy (wartości) mają reprezentację w składni (np. W sygnaturach typów), ale rodzaje (typów) są - jak sądzę - całkowicie niejawne i nie ma wyraźnej składni tam, gdzie się pojawiają.

Ale jeśli włączysz odpowiednie rozszerzenia, rozróżnienie między rodzajami i rodzajami w dużej mierze zniknie. Na przykład:

{-# LANGUAGE GADTs, TypeInType #-}
data Foo where
  Bar :: Bool -> * -> Foo

Tutaj Barjest (zarówno wartość, jak i) typ. Jako typ, jego rodzajem jest Bool -> * -> Foo, która jest funkcją na poziomie rodzaju , która przyjmuje rodzaj Bool(który jest typem, ale także rodzaj) i rodzaj rodzaju *i tworzy rodzaj Foo. Więc:

type MyBar = Bar True Int

poprawnie sprawdza rodzaj.

Jak wyjaśnia @AndrejBauer w swojej odpowiedzi, brak rozróżnienia typów i rodzajów jest niebezpieczny - posiadanie typu / rodzaju, *którego typ / rodzaj sam jest (co ma miejsce we współczesnym Haskell), prowadzi do paradoksów. Jednak system typów Haskell jest już pełen paradoksów z powodu braku rozwiązania, więc nie jest to uważane za coś wielkiego.

KA Buhr
źródło
Jeśli „typy i rodzaje są tak naprawdę takie same”, wówczas typ typejest po prostu typesam i nie byłoby takiej potrzeby kind. Czym dokładnie jest to rozróżnienie?
user21820
1
@ user21820, dodałem notatkę na końcu, która może rozwiązać ten problem. Krótka odpowiedź: tak naprawdę nie ma różnicy we współczesnym GHC Haskell .
KA Buhr
1
To świetna odpowiedź - wielkie dzięki za udostępnienie. Jest dobrze napisany i stopniowo wprowadza koncepcje - jako ktoś, kto nie pisał Haskell od kilku lat, jest to bardzo doceniane!
ultrafez
@KABuhr: Dzięki za ten dodany kawałek!
user21820
19

Jeśli wiesz o różnicy między zbiorami a klasami w teorii zbiorów, pomocne może być rozważenie tej sprawy jako Jeśli nie, możesz myśleć o rodzajach jako o typach „dużych” lub „wyższych”, których elementami mogą być typy lub mogą one w pewien sposób obejmować typy. Na przykład:

type:kind=set:class.

  • Bool jest typem
  • Type jest rodzajem, ponieważ jego elementami są typy
  • Bool -> Int jest typem
  • Bool -> Type jest rodzajem, ponieważ jego elementy są funkcjami zwracającymi typy
  • Bool * Int jest typem
  • Bool * Type jest rodzajem, ponieważ jego elementy są parami z jednym składnikiem typu

W teorii typów zwykle niepożądane jest posiadanie typu wszystkich typów (prowadzi to do pardoksów). Zamiast tego możemy mieć wszechświaty , które są typami zawierającymi inne, mniejsze typy. Na przykład możemy mieć serię wszechświatów , , , ... gdzie zawiera podstawowe rzeczy, takie jak , , , podczas gdy zawiera i i itd. Ogólnie zawieraU0U1U2U0BoolNatNatNatU1U0BoolU0U0U0Un+1Unjako element, a także wszystko inne, co możemy zbudować z i wszystkich rzeczy, które były przed nim, używając podstawowych operacji , itp.Un×

Wyjaśniam to wszystko, ponieważ często wystarczy tylko i , w którym to przypadku elementy są zwykle nazywane typami, a elementy nazywane są rodzajami . W terminologii Haskell najmniejszy wszechświat jest zapisany jako . Jest to zatem element , którego Haskell nie wymienia wprost.U0U1U0U 1 U 0U1U0**U_1

Andrej Bauer
źródło
2
Nie sądzę (GHC) Haskell ma jakąkolwiek koncepcję wszechświatów. Type :: Typejest aksjomatem. W tym przypadku rozróżnienie między „typem” a „rodzajem” jest całkowicie ludzkie. Truema typ Booli Boolma typ Type, który sam ma typ Type. Czasami nazywamy typ rodzajem, aby podkreślić, że jest to typ jednostki na poziomie typu, ale w Haskell wciąż jest to tylko typ. W systemie, w którym faktycznie istnieją wszechświaty, takim jak Coq, wówczas „typ” może odnosić się do jednego wszechświata, a „miły” do innego, ale wtedy zwykle chcemy nieskończenie wielu wszechświatów.
HTNW
1
To rozróżnienie to nie tylko „ludzki język”, to formalne rozróżnienie w podstawowym systemie typów. Całkiem możliwe jest posiadanie obu Type :: Typei rozróżnienie między rodzajami i rodzajami. Jaki fragment kodu demonstruje Type :: Typew Haskell?
Andrej Bauer
1
Powinienem też powiedzieć, że *w Haskell jest swego rodzaju wszechświat. Po prostu tego tak nie nazywają.
Andrej Bauer
3
@AndrejBauer Typez Data.Kindsi *powinny być synonimami. Początkowo mieliśmy tylko *prymityw, a obecnie jest wewnętrznie zdefiniowany jak GHC.Types.Typew module wewnętrznym GHC.Types, a z kolei zdefiniowany jako type Type = TYPE LiftedRep. Myślę, że TYPEto prawdziwy prymitywny, zapewniający rodzinę rodzajów (typy podnoszone, typy rozpakowane, ...). Większość „nieeleganckiej” złożoności polega tutaj na wspieraniu optymalizacji na niskim poziomie, a nie z przyczyn teoretycznych.
chi
1
Spróbuję podsumować. Jeżeli vjest to wartość, to ma typ: v :: T. Jeśli Tjest to rodzaj, to ma typ: T :: K. Rodzaj typu nazywany jest jego rodzajem. Typy, które wyglądają, TYPE repmogą być nazywane rodzajami, chociaż słowo to jest rzadkie. IFF T :: TYPE repjest Tmoże pojawić się na RHS od a ::. Słowo „miły” ma w tym niuans: Kin T :: Kjest rodzajem, ale nie jest w nim v :: K, chociaż jest taki sam K. Moglibyśmy zdefiniować, że „ Kjest rodzajem, jeśli jest to coś w rodzaju„ aka ”, rodzaje znajdują się na RHS ::„, ale to nie przechwytuje poprawnie użycia. Dlatego moja pozycja „ludzkiego wyróżnienia”.
HTNW
5

Wartość jest jak specyficzny czerwony 2011 Ford Mustang z 19,206 mil na to, że siedzi w podjazd.

Ta konkretna wartość, nieformalnie, może mieć wiele rodzajów : jest to Mustang i jest to Ford, i jest to samochód, i jest to pojazd, pośród wielu wielu innych typów, które można wymyślić (rodzaj „rzeczy” należący do ciebie ”lub rodzaj„ rzeczy, które są czerwone ”lub…).

(W Haskell, w przybliżeniu do pierwszego rzędu (GADT łamią tę właściwość, a magia wokół literałów liczb i rozszerzenie OverloadedStrings nieco ją zaciemniają), wartości mają jeden główny typ zamiast mnóstwa nieformalnych „typów”, które można podać stang. 42jest, dla celów tego wyjaśnienia Int,; w Haskell nie ma typu dla „liczb” lub „nawet liczb całkowitych” - lub raczej można by go utworzyć, ale byłby to typ rozłączny od Int).

Teraz „Mustang” może być podtypem „samochodu” - każda wartość, którą jest Mustang, jest również samochodem. Ale typ - lub, używając terminologii Haskella, rodzaj „Mustanga” nie jest „samochodem”. „Mustang” nie jest czymś, co można zaparkować na podjeździe lub wjechać. „Mustang” to rzeczownik, kategoria lub po prostu typ. Są to, nieformalnie, rodzaje „Mustanga”.

(Ponownie, Haskell rozpoznaje tylko jeden rodzaj dla każdej rzeczy na poziomie typu. Tak więc Intma życzliwość *, a żaden inny rodzaj. Nie Maybema życzliwości * -> *i żadnych innych rodzajów. Ale intuicja powinna nadal utrzymywać: 42jest Int, i możesz Intz nią robić różne rzeczy. ., jak dodawanie i odejmowanie Intsama nie jest Int, nie ma takich jak liczba Int + Intmoże nieformalnie usłyszeć ludzie mówią, że. Intto Num, przez które one oznaczają, że istnieje instancja z Numklasy typu dla typu Int-To nie to samo jak powiedzenie, że Intma rodzaj Num . Intma rodzaj „typu”, który w Haskell jest pisany *.)

Czy nie każdy nieformalny „typ” jest po prostu rzeczownikiem lub kategorią? Czy wszystkie typy mają ten sam rodzaj? Po co w ogóle mówić o rodzajach, jeśli są tak nudne?

W tym miejscu angielska analogia stanie się trochę nieprzyzwoita, ale proszę o wyrozumiałość: udawaj, że słowo „właściciel” w języku angielskim nie ma sensu w izolacji, bez opisu posiadanego przedmiotu. Udawaj, że gdyby ktoś nazwał cię „właścicielem”, nie miałoby to dla ciebie żadnego sensu; ale jeśli ktoś nazwał cię „właścicielem samochodu”, możesz zrozumieć, co mieli na myśli.

„Właściciel” nie ma tego samego rodzaju co „samochód”, ponieważ możesz mówić o samochodzie, ale nie możesz mówić o właścicielu w tej wymyślonej wersji języka angielskiego. Możesz mówić tylko o „właścicielu samochodu”. „Właściciel” tworzy coś w rodzaju „rzeczownika” tylko wtedy, gdy ma zastosowanie do czegoś, co ma już „rzeczownik”, na przykład „samochód”. Powiedzielibyśmy, że rodzajem „właściciela” jest „rzeczownik -> rzeczownik”. „Właściciel” jest jak funkcja, która bierze rzeczownik i tworzy z niego inny rzeczownik; ale to nie jest sam rzeczownik.

Pamiętaj, że „właściciel samochodu” nie jest podtypem „samochód”! To nie jest funkcja, która przyjmuje lub zwraca samochody! To po prostu zupełnie inny typ niż „samochód”. Opisuje wartości z dwoma rękami i dwiema nogami, które w pewnym momencie miały pewną ilość pieniędzy i zabrały je do salonu. Nie opisuje wartości, które mają cztery koła i malowanie. Pamiętaj też, że „właściciel samochodu” i „właściciel psa” są różnymi typami, a rzeczy, które możesz chcieć zrobić z jednym, mogą nie mieć zastosowania do drugiego.

(Podobnie, gdy mówimy, że Maybema to * -> *w Haskell, mamy na myśli, że nonsensowne (formalnie; nieformalnie robimy to cały czas) mówienie o posiadaniu „a Maybe”. Zamiast tego możemy mieć Maybe Inta Maybe String, ponieważ są to rzeczy miły *.)

Tak więc cały sens mówienia o rodzajach jest taki, abyśmy mogli sformalizować nasze rozumowanie wokół słów takich jak „właściciel” i wymusić, abyśmy zawsze przyjmowali wartości typów, które zostały „w pełni skonstruowane” i nie są nonsensowne.

użytkownik11228628
źródło
1
Nie twierdzę, że twoja analogia jest błędna, ale myślę, że może to powodować zamieszanie. Dijkstra ma kilka słów na temat analogii. Google „O okrucieństwie prawdziwego nauczania informatyki”.
Rafael Castro
Mam na myśli analogie samochodowe, a potem analogie samochodowe. Nie sądzę, że podkreślenie ukrytej struktury typów w języku naturalnym (który, oczywiście, rozciągnąłem się w drugiej połowie) jako sposób na wyjaśnienie formalnego systemu typów, jest tym samym rodzajem nauczania przez analogię jak mówienie o co program „chce” zrobić.
user11228628
1

Jak rozumiem, rodzaj jest rodzajem typu.

Zgadza się - zbadajmy, co to znaczy. Intlub Textsą typami konkretnymi, ale Maybe asą typem abstrakcyjnym . Nie stanie się konkretnym typem, dopóki nie zdecydujesz, jakiej konkretnej wartości chcesz dla akonkretnej zmiennej (lub wartości / wyrażenia / cokolwiek) np Maybe Text.

Mówimy, że Maybe ajest to konstruktor typów, ponieważ jest podobny do funkcji, która przyjmuje pojedynczy konkretny typ (np. Text) I zwraca konkretny typ ( Maybe Textw tym przypadku). Ale inne typy konstruktorów mogą przyjąć jeszcze więcej „parametrów wejściowych”, zanim zwrócą konkretny typ. np. Map k vmusi wziąć dwa konkretne typy (np. Inti Text), zanim będzie mógł zbudować konkretny typ ( Map Int Text).

Tak więc konstruktory typu Maybe ai List amają tę samą „sygnaturę”, którą oznaczamy jako * -> *(podobnie jak sygnatura funkcji Haskell), ponieważ jeśli podasz im jeden konkretny typ, wyplują konkretny typ. Nazywamy to „rodzajem” tego typu Maybei Listmamy ten sam rodzaj.

Mówi się, że typy betonowe są miłe *, a nasz przykład mapy jest miły, * -> * -> *ponieważ przyjmuje dwa typy betonu jako dane wejściowe, zanim będzie mógł wygenerować typ konkretny.

Widzisz, że chodzi głównie o liczbę „parametrów”, które przekazujemy konstruktorowi typów - ale zdaj sobie sprawę, że możemy również uzyskać konstruktory typów zagnieżdżone w konstruktorach typów, dzięki czemu możemy uzyskać rodzaj, który wygląda * -> (* -> *) -> *na przykład .

Jeśli jesteś programistą Scala / Java, to wyjaśnienie może również okazać się pomocne: https://www.atlassian.com/blog/archives/scala-types-of-a-higher-kind

Mark Lassau
źródło
To nie jest poprawne. W Haskell, rozróżniamy Maybe a, synonim forall a. Maybe a, polimorficzny typu rodzaju *i Maybe, monomorficzny rodzaj rodzaju * -> *.
b0fh