В чем разница между типом и видом?

26

Я изучаю язык программирования Haskell и пытаюсь понять, в чем разница между a typeи a kind.

Как я понимаю a kind is a type of type. Например, a ford is a type of carи a car is a kind of vehicle.

Это хороший способ думать об этом?

Потому что, как мой мозг в настоящее время подключен, а ford is a **type** of car, в car is a **type** of vehicleто же время, а car is a **kind** of vehicle. Т.е. условия typeи kindвзаимозаменяемы.

Может ли кто-нибудь пролить свет на это?

Томас Кук
источник
6
Я только что пришел сюда из сообщения о переполнении стека, которое привело к этой дискуссии. Я не уверен, что могу ответить подробно, но вы определенно слишком буквально относитесь к терминам «тип» и «вид», пытаясь связать их с их значением на английском языке (где на самом деле они являются синонимами ). Вы должны относиться к ним как к техническим терминам. Я предполагаю, что «тип» понятен всем программистам, потому что эта концепция жизненно важна для каждого языка, даже для слабо типизированных, таких как Javascript. «Вид» - это технический термин, используемый в Haskell для «типа типа». Это действительно все, что нужно сделать.
Робин Зигмонд
2
@RobinZigmond: вы правы в том, что это технические термины, но они используются более широко, чем просто в Haskell. Может быть, обратная ссылка на обсуждение Stack Overflow, которое породило этот вопрос?
Андрей Бауэр
@AndrejBauer Я никогда не говорил, что они не использовались за пределами Haskell, безусловно, «тип» используется практически во всех языках, как я уже сказал. На самом деле я никогда не встречал «добрых» за пределами Haskell, но тогда Haskell - единственный функциональный язык, который я знаю вообще, и я был осторожен, чтобы не сказать, что этот термин не используется в другом месте, просто он используется таким образом в Haskell. (И ссылка, как вы просите, здесь )
Робин Зигмонд
Языки семейства ML также имеют разновидности, например, Standard ML и OCaml. Я думаю, что они явно не представлены этим именем. Они проявляются как подписи , а их элементы называются структурами .
Андрей Бауэр
1
Более точная английская аналогия - «Форд» - это тип автомобиля, а «автомобиль» - это тип транспортных средств, но и типы автомобилей, и типы транспортных средств относятся к одному и тому же виду: существительные. Принимая во внимание, что красный - это цвет автомобиля, а RPM - это тип показателей эффективности автомобиля, и оба они одного типа: прилагательные.
Slebetman

Ответы:

32

Здесь «значения», «типы» и «виды» имеют формальное значение, поэтому рассмотрение их общего использования на английском языке или аналогии с классификацией автомобилей только поможет вам.

Мой ответ относится к формальным значениям этих терминов в контексте Хаскелла; эти значения основаны (хотя на самом деле не идентичны) значениям, используемым в математической / CS "теории типов". Таким образом, это не будет очень хорошим ответом «информатики», но он должен послужить довольно хорошим ответом на Haskell.

В Haskell (и других языках) полезно назначить тип программному выражению, который описывает класс значений , которые разрешено иметь выражению. Здесь я предполагаю, что вы видели достаточно примеров, чтобы понять, почему было бы полезно знать, что в выражении sqrt (a**2 + b**2)переменные aи bвсегда будут значениями типа, Doubleа не, скажем, Stringи Boolсоответственно. По сути, наличие типов помогает нам в написании выражений / программ, которые будут корректно работать в широком диапазоне значений .

Теперь, что вы, возможно, не поняли, - это то, что типы Haskell, такие как те, которые появляются в сигнатурах типов:

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

на самом деле написаны на подъязыке Haskell на уровне типов. Текст программы Functor f => (a -> b) -> f a -> f b- в буквальном смысле - выражение типа, написанное на этом подъязыке. Подъязык входят операторы (например, ->является правым ассоциативным инфиксный оператор на этом языке), переменные (например, f, a, и b), и «приложение» одного выражения типа к другому (например, f aэто fприменяется к a).

Я упоминал, как во многих языках было полезно назначать типы программным выражениям для описания классов значений выражений? Что ж, в этом подъязыке на уровне типов выражения оцениваются по типам (а не по значениям ), и в итоге оказывается полезным назначать виды выражениям типов для описания классов типов, которые им разрешено представлять. По сути, наличие видов помогает нам в написании выражений типов, которые будут корректно работать с широким диапазоном типов .

Таким образом, значения относятся к типам, а типы - к видам , а типы помогают нам писать программы уровня значения, а виды помогают нам писать программы типа уровня .

Как выглядят эти виды ? Хорошо, рассмотрим тип подписи:

id :: a -> a

Если выражение типа a -> aдолжна быть действительными, какой вид из типов , мы должны позволить переменным aбыть? Ну, типа выражения:

Int -> Int
Bool -> Bool

выглядят корректно, поэтому типы Int и Bool, очевидно, правильного вида . Но даже более сложные типы, такие как:

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

смотри правильно. Фактически, поскольку мы должны иметь возможность вызывать idфункции, даже:

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

выглядит хорошо. Таким образом, Int, Bool, [Double], Maybe [(Double,Int)], и a -> aвсе выглядят как типы правого вида .

Другими словами, похоже, что есть только один вид , давайте назовем его *подстановочным знаком Unix, и у каждого типа будет свой вид * , конец истории.

Правильно?

Ну, не совсем. Оказывается, что Maybeсамо по себе так же верно выражение типа, как и Maybe Int(почти так же sqrt, как само по себе, так же верно выражение значения, как и sqrt 25). Однако следующее выражение типа недопустимо:

Maybe -> Maybe

Потому что, в то время как Maybeэто выражение типа, он не представляет вид из типа , который может иметь значение. Итак, вот как мы должны определить *- это вид из типов , которые имеют значение; он включает в себя «полные» типы, такие как Doubleили, Maybe [(Double,Int)]но исключает неполные, бесполезные типы, такие как Either String. Для простоты я буду называть эти полные типы вида *«конкретными типами», хотя эта терминология не универсальна, и «конкретные типы» могут означать нечто совсем иное, скажем, для программиста C ++.

Теперь в выражении типа a -> a, пока тип aимеет тип * (тип конкретных типов), результат выражения типа такжеa -> a будет иметь тип (т. Е. Тип конкретных типов). *

Итак, что вид из типа является Maybe? Ну, Maybeможет быть применен к конкретному типу, чтобы получить другой конкретный тип. Так, Maybeвыглядит как маленькая , как функция типа уровня , который принимает вид из рода * и возвращает тип из вида * . Если бы мы имели функцию на уровень значения, принявшее значение из типа Int и возвращающее значение из типа Int , мы бы дать ему тип подпись Int -> Int, поэтому по аналогии мы должны дать Maybeна любезную подпись * -> *. GHCi соглашается:

> :kind Maybe
Maybe :: * -> *

Возвращаясь к:

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

В сигнатуре этого типа переменная fимеет вид, * -> *переменные aи bвид *; встроенный оператор ->имеет вид * -> * -> *(он принимает тип вида *слева и один справа и возвращает тип также типа *). Из этого и правил вывода вида можно сделать вывод, что a -> bэто допустимый тип с типом *, f aа f bтакже допустимые типы с типом *и (a -> b) -> f a -> f bдопустимый тип типа *.

Другими словами, компилятор может «проверять вид» выражения типа, (a -> b) -> f a -> f bчтобы убедиться, что он действителен для переменных типа правильного типа, так же, как он «проверяет тип», sqrt (a**2 + b**2)чтобы убедиться, что он действителен для переменных правильного типа.

Причина использования отдельных терминов для «типов» и «видов» (т. Е. Не говорить о «типах») состоит в основном во избежание путаницы. Эти виды выше вид очень отличается от типов и, по крайней мере , на первый, кажется, ведут себя совершенно по- разному. (Например, требуется некоторое время, чтобы понять, что каждый «нормальный» тип имеет одинаковый тип, *а тип a -> b- *нет * -> *.)

Часть этого также историческая. По мере развития GHC Haskell различия между значениями, типами и типами начали стираться. В наши дни значения можно «преобразовать» в типы, а типы и типы - это одно и то же. Таким образом, в современном Haskell значения имеют как типы, так и типы ARE (почти), а типы - просто больше типов.

Пользователь @ user21820 попросил дать дополнительное объяснение: «типы и типы - это одно и то же». Чтобы быть более понятным, в современном GHC Haskell (я думаю, начиная с версии 8.0.1) типы и виды обрабатываются одинаково в большей части кода компилятора. Компилятор прилагает некоторые усилия в сообщениях об ошибках, чтобы различать «типы» и «виды», в зависимости от того, жалуется ли он на тип значения или тип типа соответственно.

Кроме того, если расширения не включены, они легко различимы на языке поверхности. Например, типы (значений) имеют представление в синтаксисе (например, в сигнатурах типов), но виды (типов) являются - я думаю - полностью неявными, и нет явного синтаксиса, где они появляются.

Но если вы включите соответствующие расширения, различие между типами и видами в значительной степени исчезнет. Например:

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

Здесь Barесть (и значение, и) тип. Как тип, его тип есть Bool -> * -> Foo, который является функцией уровня типа, которая принимает тип типа Bool(который является типом, но также и типом) и типом типа *и производит тип типа Foo. Так:

type MyBar = Bar True Int

правильно проверок.

Как объясняет @AndrejBauer в своем ответе, эта неспособность различать типы и виды небезопасна - наличие типа / типа *, тип / тип которого сам является (что имеет место в современном Haskell), приводит к парадоксам. Тем не менее, система типов Хаскелла уже полна парадоксов из-за отсутствия завершения, так что это не считается большой проблемой.

К. А. Бур
источник
Если «типы и виды действительно одно и то же», то тип type- это просто typeсам по себе, и в этом не было бы никакой необходимости kind. Так в чем же различие?
user21820
1
@ user21820, я добавил в конец заметку, которая может решить эту проблему. Короткий ответ: в современном GHC Haskell нет никаких различий .
К. А. Бур
1
Это отличный ответ - большое спасибо за обмен. Это хорошо написано и вводит понятия постепенно - как кто-то, кто не писал на Haskell в течение нескольких лет, это очень ценится!
Ультрафез
@KABuhr: Спасибо за это немного!
user21820
19

TYпе:КяNdзнак равноsеT:сLass,

  • Bool это тип
  • Type это вид, потому что его элементы являются типами
  • Bool -> Int это тип
  • Bool -> Type это вид, потому что его элементы являются функциями, которые возвращают типы
  • Bool * Int это тип
  • Bool * Type это вид, потому что его элементы являются парами с одним компонентом типа

U0U1U2U0BoolNatNatNatU1U0BoolU0U0U0Un+1UnUn×

U0U1U0U1U0**U_1

Андрей Бауэр
источник
2
Я не думаю, что (GHC) у Haskell есть какая-то концепция вселенных. Type :: Typeэто аксиома. В этом случае различие между «типом» и «видом» полностью в человеческом языке. Trueимеет тип, Boolи Boolимеет тип Type, который сам имеет тип Type. Иногда мы называем тип видом, чтобы подчеркнуть, что это тип сущности уровня типа, но в Haskell это все еще просто тип. В системе, где фактически существуют вселенные, такие как Coq, тогда «тип» может относиться к одной вселенной и «добр» к другой, но тогда мы обычно хотим бесконечно много вселенных.
HTNW
1
Различие - это не просто «человеческий язык», это формальное различие в базовой системе типов. Вполне возможно иметь и то, Type :: Typeи другое, и различие между типами и видами. Кроме того, какой фрагмент кода демонстрирует Type :: Typeв Haskell?
Андрей Бауэр
1
Я также должен сказать, что *в Haskell есть своего рода вселенная. Они просто так этого не называют.
Андрей Бауэр
3
@AndrejBauer Typeот Data.Kindsи *должно быть синонимами. Изначально у нас был только *примитив, а в настоящее время это внутренне определяется как GHC.Types.Typeво внутреннем модуле GHC.Types, а в свою очередь определяется как type Type = TYPE LiftedRep. Я думаю, что TYPEэто настоящий примитив, обеспечивающий семейство видов (поднятые типы, распакованные типы, ...). Большая часть «не элегантной» сложности здесь заключается в поддержке некоторых низкоуровневых оптимизаций, а не по фактическим теоретическим причинам типа.
Чи
1
Я постараюсь подвести итог. Если vэто значение, то оно имеет вид: v :: T. Если Tэто тип, то она имеет вид: T :: K. Тип типа называется его родом. Типы, которые выглядят так, TYPE repмогут называться сортировками, хотя это слово встречается редко. Если T :: TYPE repэто Tразрешено появляться на RHS a ::. У слова «добрый» есть свой нюанс: « Kв» T :: K- это «добрый», но не «в» v :: K, хотя и тот же K. Мы могли бы определить « Kэто вид, если его вид является своего рода« ака », виды на RHS of ::», но это неправильно отражает использование. Поэтому моя позиция "человеческого различия".
HTNW
5

Значение , как специфический красный 2011 Ford Mustang с 19,206 миль на нем , что вы сидели в дороге.

Эта неформальная ценность может иметь много типов : это Мустанг, и это Форд, и это автомобиль, и это автомобиль, среди многих других типов, которые вы могли бы составить (тип «вещей»). принадлежащие вам ", или тип" красные вещи ", или ...).

(В Haskell, в приближении первого порядка (GADT нарушают это свойство, а магия вокруг числовых литералов и расширение OverloadedStrings немного затеняет его), значения имеют один главный тип вместо множества неформальных «типов», которые вы можете дать stang. 42, для целей этого объяснения, an Int; в Haskell нет типа для «чисел» или «даже целых чисел», или, скорее, вы можете создать его, но это будет непересекающийся тип из Int.)

Теперь, "Мустанг" может быть подтипом "автомобиля" - каждая ценность, которая является Мустангом, является также автомобилем. Но тип - или, если использовать терминологию Хаскелла, тип «Мустанг» - это не «автомобиль». «Мустанг» - это не то, что вы можете припарковать на подъездной дороге или покататься по нему. «Мустанг» - это существительное, категория, или просто тип. Это, неофициально, виды "Мустанга".

(Опять же, Haskell распознает только один вид для каждой вещи на уровне типа. Так что Intесть добрый *, и никаких других видов. MaybeЕсть добрый * -> *, и никаких других видов. Но интуиция все еще должна держаться: 42есть Int, и вы можете делать Intс ней все . , как сложение и вычитание Intсам по себе не является Int, нет такого числа , как Int + IntВы можете неформально слышать , как люди говорят , что. Intэто Num, по которым они понимают , что есть экземпляр из Numкласса типа для типа Int-Эты не то же самое как говорят, что Intимеет добрые Num . Intимеет добрый «тип», который пишется на Хаскеле *.)

Так не каждый ли неформальный «тип» - это просто существительное или категория? Все ли типы имеют одинаковый вид? Зачем вообще говорить о видах, если они такие скучные?

Вот где английская аналогия станет немного странной, но потерпите меня: сделайте вид, что слово «владелец» в английском языке не имеет смысла в отдельности, без описания принадлежащей вещи. Притворись, что если бы кто-то назвал тебя «владельцем», это не имело бы никакого смысла для тебя; но если бы кто-то назвал вас «владельцем машины», вы могли бы понять, что они имели в виду.

«Владелец» не похож на «автомобиль», потому что вы можете говорить об автомобиле, но вы не можете говорить о владельце в этой вымышленной версии английского языка. Можно говорить только о «владельце машины». «Владелец» создает нечто вроде «существительное» только в том случае, если оно применяется к чему-то, что уже имеет «существительное», например, «машина». Мы бы сказали, что тип «владелец» это «существительное -> существительное». «Владелец» подобен функции, которая берет существительное и производит из него другое существительное; но это не само существительное.

Обратите внимание, что «владелец автомобиля» не является подтипом «автомобиля»! Это не функция, которая принимает или возвращает автомобили! Это просто совершенно отдельный тип от "автомобиля". В нем описываются ценности с двумя руками и двумя ногами, которые в определенный момент имели определенную сумму денег, и доставили эти деньги в дилерский центр. Он не описывает значения с четырьмя колесами и окраской. Также обратите внимание, что «владелец автомобиля» и «владелец собаки» относятся к разным типам, и то, что вы, возможно, захотите сделать с одним, может быть неприменимо к другому.

(Аналогично, когда мы говорим, что в Haskell это Maybeимеет вид * -> *, мы имеем в виду, что бессмысленно (формально; неофициально мы делаем это все время) говорить о наличии «a Maybe». Вместо этого мы можем иметь a Maybe Intили a Maybe String, поскольку это вещи добрый *.)

Таким образом, весь смысл разговора о видах вообще состоит в том, чтобы мы могли формализовать наши рассуждения вокруг слов типа «владелец» и обеспечить, чтобы мы когда-либо принимали значения только тех типов, которые были «полностью сконструированы» и не являются бессмысленными.

user11228628
источник
1
Я не говорю, что ваша аналогия неверна, но я думаю, что это может вызвать путаницу. У Дейкстры есть несколько слов об аналогиях. Google "О жестокости по-настоящему преподавания информатики".
Рафаэль Кастро
Я имею в виду автомобильные аналогии, а затем автомобильные аналогии. Я не думаю, что выделение неявной структуры типов в естественном языке (который, по общему признанию, я действительно растягивал во второй половине) в качестве способа объяснения формальной системы типов является тем же типом обучения через аналогию, что и разговор о что программа "хочет" сделать.
user11228628
1

Насколько я понимаю, вид - это тип типа.

Это верно - давайте посмотрим, что это значит. Intили Textконкретные типы, но Maybe aэто абстрактный тип. Он не станет конкретным типом, пока вы не решите, какое конкретное значение вы хотите для aконкретной переменной (или значение / выражение / что угодно), например Maybe Text.

Мы говорим, что Maybe aэто конструктор типа, потому что он похож на функцию, которая принимает один конкретный тип (например Text) и возвращает конкретный тип ( Maybe Textв данном случае). Но конструкторы других типов могут принять еще больше «входных параметров», прежде чем они возвращают конкретный тип. Например, Map k vнеобходимо принять два конкретных типа (например, Intи Text), прежде чем он может построить конкретный тип ( Map Int Text).

Таким образом, конструкторы типов Maybe aи List aимеют ту же «сигнатуру», которую мы обозначаем как * -> *(аналогично сигнатуре функции Haskell), потому что если вы дадите им один конкретный тип, они будут выплевывать конкретный тип. Мы называем это «типом» типа Maybeи Listимеем тот же вид.

Говорят, что конкретные типы имеют тип kind *, и наш пример Map является kind, * -> * -> *поскольку он принимает два конкретных типа в качестве входных данных, прежде чем он сможет выводить конкретный тип.

Вы можете видеть, что это в основном только количество «параметров», которые мы передаем конструктору типов, но понимаем, что мы можем также получить конструкторы типов, вложенные в конструкторы типов, так что мы можем получить вид, который выглядит, * -> (* -> *) -> *например, как ,

Если вы являетесь разработчиком Scala / Java, вам также может пригодиться это объяснение: https://www.atlassian.com/blog/archives/scala-types-of-a-higher-kind

Марк Лассау
источник
Это не правильно. В Хаскеле мы различаем Maybe aсиноним forall a. Maybe aполиморфного типа *и Maybeмономорфный тип * -> *.
b0fh