Я думаю, что имеет смысл объяснять экзистенциальные типы вместе с универсальными типами, поскольку эти два понятия дополняют друг друга, то есть одно является «противоположностью» другого.
Я не могу ответить на каждую деталь об экзистенциальных типах (например, дать точное определение, перечислить все возможные применения, их отношение к абстрактным типам данных и т. Д.), Потому что я просто недостаточно осведомлен для этого. Я продемонстрирую только (с использованием Java), что эта статья на HaskellWiki утверждает, что является основным эффектом экзистенциальных типов:
Существующие типы могут использоваться для нескольких различных целей. Но то, что они делают , это «скрыть» переменную типа с правой стороны. Обычно любая переменная типа, появляющаяся справа, также должна появляться слева […]
Пример настройки:
Следующий псевдокод не совсем корректный Java, хотя это было бы достаточно легко исправить. На самом деле, именно это я и собираюсь сделать в этом ответе!
class Tree<α>
{
α value;
Tree<α> left;
Tree<α> right;
}
int height(Tree<α> t)
{
return (t != null) ? 1 + max( height(t.left), height(t.right) )
: 0;
}
Позвольте мне кратко изложить это для вас. Мы определяем & hellip;
рекурсивный тип Tree<α>, представляющий узел в двоичном дереве. Каждый узел хранит value некоторого типа α и имеет ссылки на необязательные поддеревья left и right того же типа.
функция height, которая возвращает самое дальнее расстояние от любого конечного узла до корневого узла t.
Теперь давайте превратим приведенный выше псевдокод для height в правильный синтаксис Java! (Я буду продолжать опускать некоторые шаблоны для краткости, такие как модификаторы ориентации объекта и доступности.) Я собираюсь показать два возможных решения.
1. Универсальное типовое решение:
Наиболее очевидное исправление - просто сделать height универсальным, введя параметр типа α в его сигнатуру:
<α> int height(Tree<α> t)
{
return (t != null) ? 1 + max( height(t.left), height(t.right) )
: 0;
}
Это позволит вам объявлять переменные и создавать выражения типа α внутри этой функции, если вы захотите. Но ...
2. Решение экзистенциального типа:
Если вы посмотрите на тело нашего метода, вы заметите, что мы на самом деле не обращаемся или не работаем с чем-либо типа α ! Нет ни одного выражения с таким типом, ни каких-либо переменных, объявленных с этим типом ... итак, почему мы вообще должны делать height универсальными? Почему мы не можем просто забыть о α ? Как оказалось, мы можем:
int height(Tree<?> t)
{
return (t != null) ? 1 + max( height(t.left), height(t.right) )
: 0;
}
Как я писал в самом начале этого ответа, экзистенциальные и универсальные типы имеют комплементарный / двойственный характер. Таким образом, если решение универсального типа должно было сделать height больше универсальным, то следует ожидать, что экзистенциальные типы будут иметь обратный эффект: сделать его менее универсальным, а именно путем скрытия / удаления параметр типа α .
Как следствие, вы больше не можете ссылаться на тип t.value в этом методе и не манипулировать какими-либо выражениями этого типа, потому что с ним не связан ни один идентификатор. (Подстановочный знак ? является специальным токеном, а не идентификатором, который «захватывает» тип.) t.value фактически стал непрозрачным; возможно, единственное, что вы все еще можете сделать с ним, это привести его к Object.
Резюме:
===========================================================
| universally existentially
| quantified type quantified type
---------------------+-------------------------------------
calling method |
needs to know | yes no
the type argument |
---------------------+-------------------------------------
called method |
can use / refer to | yes no
the type argument |
=====================+=====================================