Может ли кто-нибудь объяснить связь между ковариацией типов/контравариантностью и теорией категорий?

Я только начинаю читать о теории категорий, и был бы очень признателен, если бы кто-то мог объяснить связь между контравариантностью/ковариацией CS и теорией категорий. Каковы будут некоторые категории категорий (т.е. Какие их объекты/морфизмы?)? Заранее спасибо?

Ответ 1

Контравариантный функтор из $C $в $D $является тем же самым, что и нормальный (т.е. ковариантный) функтор от $C $до $D ^ {op} $, где $D ^ {op} $- противоположная категория $D $. Поэтому сначала лучше понять противоположные категории - тогда вы автоматически поймете контравариантные функторы!

Контравариантные функторы не часто появляются в CS, хотя я могу представить два исключения:

Возможно, вы слышали о контравариантности в контексте подтипирования. Хотя это технически тот же термин, соединение действительно, действительно слабое. В объектно-ориентированном программировании классы образуют частичный порядок; каждый частичный порядок - это категория с "бинарными гомосетными множествами" - для любых двух объектов $A $и $B $существует ровно один морфизм $A\to B $iff $A\leq B $(обратите внимание на направление; эта слегка запутанная ориентация является стандартом по причинам, которые я не буду здесь объяснять) и никаких морфизмов в противном случае.

Параметрированные типы, например, Scala PartialFunction [-A, Unit] являются функторами этой простой категории для себя... мы обычно фокусируемся на том, что они делают с объектами: задан класс X, PartialFunction [X, Unit ] также является классом. Но функторы также сохраняют морфизмы; в этом случае, если бы у нас был подкласс Dog of Animal, у нас был бы морфизм Dog $\ to $Animal, и функтор сохранил бы этот морфизм, предоставив нам морфизм PartialFunction [Animal, Unit] $\ to $PartialFunction [Dog, Unit], сообщая нам, что PartialFunction [Animal, Unit] является подклассом PartialFunction [Dog, Unit]. Если вы думаете об этом, это имеет смысл: предположим, что у вас есть ситуация, когда вам нужна функция, которая работает на собаках. Функция, которая работает на всех животных, несомненно, будет работать там!

Тем не менее, использование полноразмерной теории категорий для разговоров о частично упорядоченных множествах является избыточным избытком.
Менее распространенный, но на самом деле использует теорию категорий: рассмотрим типы категорий (Hask), объектами которых являются типы языка программирования Haskell и где морфизм $\ tau_1\to\tau_2 $является функцией типа $\ tau_1 $- > $\ tau_2 $. Существует также категория Judges (Hask), объектами которой являются списки типизирующих суждений $\ tau_1\vdash\tau_2 $и морфизмы которых являются доказательствами всех суждений одного списка, используя суждения в другом списке как гипотезы. Существует функтор из Types (Hask) в Judges (Hask), который принимает тип (Hask) -морфизм $f: A\to B $к доказательству

     B |- Int
    ----------
      ......
    ----------
     A |- Int

который является морфизмом $(B\vdash Int)\to (A\vdash Int) $- заметить изменение направления. В основном, это говорит о том, что если у вас есть функция, которая превращает A в B'a и выражение типа Int со свободной переменной x типа B, вы можете обернуть ее "let x = fy in..." и вывести выражение типа Int, но единственная свободная переменная имеет тип $A $, а не $B $.

Ответ 2

Есть очень хорошие видеоролики о контравариантности/ковариации в Переход на глубокий канал в Microsoft Channel9. Вы можете начать здесь: