Почему говорят, что классы типов являются экзистенциальными?

Question

Согласно эта ссылка описывает экзистенциальные типы :

Значение экзистенциального типа, такого как ∃x. F (x) - это пара, содержащая некоторый тип x и значение типа F (x). Принимая во внимание значение полиморфного типа, такого как .x. F (x) - это функция, которая принимает некоторый тип x и выдает значение типа F (x). В обоих случаях тип закрывается над каким-то конструктором типа F.

Но определение функции с ограничениями класса типа не совпадает с экземпляром класса типа.

Это не forall f, exists Functor f, ... (поскольку очевидно, что не каждый тип f имеет экземпляр Functor f, следовательно, exists Functor f ... не соответствует действительности).

Это не exists f and Functor f, ... (поскольку оно применимо ко всем случаям удовлетворяемого f, а не только к выбранному).

Для меня это forall f and instances of Functor f, ..., больше похоже на неявные аргументы scala, а не на экзистенциальные типы.

А согласно эта ссылка описывает классы типов :

[Объявление класса для Eq] означает, логически, что есть тип a, для которого тип a -> a -> Bool обитаем, или, из a можно доказать, что a -> a -> Bool (класс обещает два разных доказательства для этого, имея имена == и /=). Это предложение носит экзистенциальный характер (не путать с экзистенциальным типом)

В чем разница между классами типов и экзистенциальными типами, и почему они оба считаются "экзистенциальными"?

Answer 1

Вики, которую вы цитируете, неверна или, по крайней мере, неточна.Объявление класса не является экзистенциальным предложением;это не какое-либо предложение, это просто определение стенографии.Затем можно перейти к предложению, используя это определение, если хотите, но само по себе это не так.Например,

class Eq a where (==) :: a -> a -> Bool

дает новое определение.Затем можно написать несуществующее, неуниверсальное суждение, используя его, скажем,

Eq ()

, которое мы могли бы «доказать», написав:

instance Eq () where () == () = True

Или можно написать

prop_ExistsFoo :: exists a. Eq a *> a

как экзистенциальное суждение.(На самом деле Хаскелл не имеет ни первого выражения exists, ни (*>). Думайте о (*>) как о двойственном по отношению к (=>) - точно так же, как exists является двойственным по отношению к forall. Так, где (=>) - этофункция, которая получает свидетельство об ограничении, (*>) - это кортеж, который содержит свидетельство об ограничении, точно так же, как forall - для функции, которая принимает тип, тогда как exists - для кортежа, который содержит тип.) Мыможет «доказать» это утверждение, например,

prop_ExistsFoo = ()

Обратите внимание, что тип, содержащийся в кортеже exists, равен ();доказательства, содержащиеся в кортеже (*>), - это экземпляр Eq (), который мы написали выше.Я уважал тенденцию Хаскелла делать здесь типы и экземпляры молчаливыми и неявными, чтобы они не появлялись в видимом тексте доказательства.

Точно так же мы могли бы сделать другое универсальное предложение из Eq, написавчто-то вроде

prop_ForallEq :: forall a. Eq a => a

, которое нетривиально доказуемо, или

prop_ForallEq2 :: forall a. Eq a => a -> a -> Bool

, которое мы могли бы "доказать", например, написав

prop_ForallEq2 x y = not (x == y)

или вмного других способов.

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

Answer 2

Вторая цитата неточна. Экзистенциальное требование приходит с экземплярами, а не с самим классом. Рассмотрим следующий класс:

class Chaos a where
    to :: a -> y
    from :: x -> a

Хотя это совершенно правильное объявление, не может быть никаких экземпляров Chaos (если бы существовало, to . from существовало бы, что было бы довольно забавно). Тип, скажем, to ...

GHCi> :t to
to :: Chaos a => a -> y

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

Отложив на мгновение классы, эта ситуация довольно похожа на то, что мы имеем с функцией absurd :

absurd :: Void -> a

Этот тип говорит, что, учитывая значение Void, мы можем создать значение любого типа. Это звучит, ну, абсурдно - но потом мы помним, что Void - пустой тип, что означает, что Void значений нет, и все это хорошо.

Для контраста, мы могли бы заметить, что экземпляры становятся возможными, когда мы разделяем Chaos на два класса:

class Primordial a where
    conjure :: a -> y

class Doom a where
    destroy :: x -> a


instance Primordial Void where
    conjure = absurd

instance Doom () where
    destroy = const ()

Когда мы, например, пишем instance Primordial Void, мы заявляем, что Void является экземпляром Primordial. Это подразумевает, что должна существовать функция conjure :: Void -> y, после чего мы должны подкрепить заявку, предоставив реализацию.