Что такое контравариантный функтор?

Ответ 1

С точки зрения программиста сущность функторности способна легко адаптировать вещи. То, что я подразумеваю под "приспосабливанием", заключается в том, что если у меня есть f a, и мне нужен f b, мне нужен адаптер, который будет соответствовать моему f a в моей f b -образной дыре.

Кажется интуитивным, что если я могу превратить a в b, я мог бы превратить a f a в f b. И действительно, что образ, который класс Haskell Functor воплощает; если я поставлю функцию a -> b, тогда fmap позволяет мне адаптировать f a вещи в объекты f b, не беспокоясь о том, что включает f. ¹

Конечно, речь идет о параметризованных типах, таких как list-of-x [x], Maybe y или IO z здесь, и то, что мы можем изменить с помощью наших адаптеров, это x, y или z в них. Если нам нужна гибкость для получения адаптера из любой возможной функции a -> b, то, конечно, мы адаптируемся к тому, чтобы быть в равной степени применимы к любому возможному типу.

Что менее интуитивно (сначала) состоит в том, что существуют некоторые типы, которые могут быть адаптированы почти точно так же, как функциональные, только они "обратные"; для них, если мы хотим адаптировать f a для заполнения потребности f b, нам действительно нужно предоставить функцию b -> a, а не a -> b one!

Мой любимый конкретный пример - это фактически тип функции a -> r (a для аргумента, r для результата); вся эта абстрактная глупость имеет смысл при применении к функциям (и если вы сделали какое-либо существенное программирование, вы почти наверняка использовали эти понятия, не зная терминологии или того, насколько широко они применимы), и эти два понятия настолько очевидны двойственные друг к другу в этом контексте.

Хорошо известно, что a -> r является функтором в r. Это имеет смысл; если у меня есть a -> r, и мне нужен a -> s, тогда я мог бы использовать функцию r -> s для адаптации моей исходной функции просто путем последующей обработки результата. ²

Если, с другой стороны, у меня есть функция a -> r, и мне нужно это b -> r, то снова ясно, что я могу удовлетворить свои потребности, предварительно обработав аргументы, прежде чем передавать их исходной функции. Но с чем я их предварительно обрабатываю? Исходная функция - черный ящик; независимо от того, что я делаю, он всегда ожидает ввода a. Поэтому мне нужно преобразовать значения b в значения a, которые он ожидает: моему адаптеру предварительной обработки нужна функция b -> a.

Мы только что видели, что тип функции a -> r является ковариантным функтором в r и контравариантным функтором в a. Я думаю об этом, говоря, что мы можем адаптировать результат функции, а тип результата "изменяется с помощью адаптера r -> s, а когда мы адаптируем аргумент функции, тип аргумента изменяется в" противоположном направлении "к адаптеру.

Интересно, что реализация функции-результата fmap и функции-аргумента contramap почти то же самое: просто составная функция (оператор .)! Единственная разница в том, с какой стороны вы составляете функцию адаптера: ³

fmap :: (r -> s) -> (a -> r) -> (a -> s)
fmap adaptor f = adaptor . f
fmap adaptor = (adaptor .)
fmap = (.)

contramap' :: (b -> a) -> (a -> r) -> (b -> r)
contramap' adaptor f = f . adaptor
contramap' adaptor = (. adaptor)
contramap' = flip (.)

Я считаю, что второе определение из каждого блока наиболее проницательно; (ковариантно) отображение по результату функции - это композиция слева (посткомпозиция, если мы хотим взять представление "это-произойдет-после-того" ), тогда как контравариантное отображение над аргументом функции - это композиция справа (pre- состав).

Эта интуиция довольно хорошо обобщается; если структура f x может дать нам значения типа x (как функция a -> r дает нам r значения, по крайней мере потенциально), она может быть ковариантной Functor в x, и мы может использовать функцию x -> y, чтобы адаптировать ее к f y. Но если структура f x получает от нас значения типа x (опять же, как и аргумент функции a -> r типа a), тогда это может быть функтор Contravariant, и нам нужно будет использовать y -> x, чтобы адаптировать его к f y.

Мне интересно подумать, что эти "источники ковариантны, направления контравариантны" интуиция меняет направление, когда вы думаете с точки зрения разработчика источника/адресата, а не вызывающего. Если я пытаюсь внедрить f x, который получает значения x, я могу "адаптировать мой собственный интерфейс", поэтому вместо этого я должен работать с значениями y (при этом все еще представляя интерфейс "получает x значения" ) мои абоненты) с помощью функции x -> y. Обычно мы так не думаем; даже будучи разработчиком f x, я думаю о том, чтобы адаптировать то, что я вызываю, вместо того, чтобы "адаптировать мой интерфейс вызывающего абонента ко мне". Но это еще одна перспектива, которую вы можете предпринять.

Единственное полу-реальное использование, которое я сделал из Contravariant (в отличие от неявного использования контравариантности функций в своих аргументах с использованием композиции по-правому, что очень часто) было для тип Serialiser a, который мог бы сериализовать значения x. Serialiser должен был быть Contravariant, а не a Functor; учитывая, что я могу сериализовать Foos, я также могу сериализовать Bars, если могу Bar -> Foo. ⁴ Но когда вы понимаете, что Serialiser a в основном a -> ByteString, это становится очевидным; Я просто повторяю специальный пример примера a -> r.

В чистом функциональном программировании очень мало пользы от наличия чего-то, что "получает значения", без того, чтобы он тоже возвращал что-то обратно, поэтому все контравариантные функторы имеют тенденцию выглядеть как функции, но почти любая простая структура данных, которая может содержать значения произвольный тип будет ковариантным функтором в параметре этого типа. Вот почему Functor раненые доброе имя раннее и используется повсеместно (ну, и что Functor был признан как фундаментальная часть Monad, которая уже широко использовалась до того, как был определен Functor как класс в Haskell).

В соответствии с ОО я считаю, что контравариантные функторы могут быть значительно более распространены (но не абстрагированы с помощью единой структуры, такой как Contravariant), хотя также очень легко иметь изменчивость и побочные эффекты, означающие, что параметризованный тип просто не мог (обычно: ваш стандартный контейнер a, который является читаемым и записываемым, является как эмиттером, так и приемником a, а не означает, что он является как ковариантным, так и контравариантным, что не означает его).

¹ В экземпляре Functor каждого отдельного f говорится, как применять произвольные функции к конкретному виду этого f, не беспокоясь о конкретных типах f к; хорошее разделение проблем.

² Этот функтор также является монадой, эквивалентной монаде Reader. Я не собираюсь выходить за рамки функторов подробно здесь, но, учитывая остальную часть моего сообщения, очевидным вопросом будет "тип a -> r также какая-то контравариантная монада в a then?". Контравариантность не относится к монадам, к сожалению (см. Существуют ли контравариантные монады?), но существует контравариантный аналог Applicative: https://hackage.haskell.org/package/contravariant-1.4/docs/Data-Functor-Contravariant-Divisible.html

³ Обратите внимание, что мой contramap' здесь не соответствует фактическому contramap из Contravariant, как это реализовано в Haskell; вы не можете сделать a -> r фактическим экземпляром Contravariant в коде Haskell просто потому, что a не является последним параметром типа (->). Концептуально он работает отлично, и вы всегда можете использовать оболочку newtype для замены параметров типа и создания экземпляра (контравариант определяет тип Op для этой цели).

⁴ По крайней мере, для определения "сериализации", который не обязательно включает возможность восстановления панели позже, поскольку он будет сериализовать a Bar одинаково с Foo, на который он отображен без способ включить любую информацию о том, что такое отображение.

Ответ 2

Прежде всего, ответ @haoformayor превосходен, поэтому рассмотрите это скорее как дополнение, чем полный ответ.

Определение

Один из способов, которым я хотел бы думать о Функторе (со/контравариантный), заключается в диаграммах. Определение отражено в следующих. (Я сокращаю contramap с помощью cmap)

      covariant                           contravariant
f a ─── fmap φ ───▶ f b             g a ◀─── cmap φ ─── g b
 ▲                   ▲               ▲                   ▲
 │                   │               │                   │
 │                   │               │                   │
 a ────── φ ───────▶ b               a ─────── φ ──────▶ b

Обратите внимание: единственное изменение в этих двух определениях - стрелка вверху (ну и имена, чтобы я мог ссылаться на них как на разные вещи).

пример

Пример, который я всегда имею в type F a = forall r. r → a когда говорю о них, это функции - и тогда примером f будет type F a = forall r. r → a type F a = forall r. r → a (что означает, что первый аргумент произвольный, но фиксированный r), или, другими словами, все функции с общим входом. Как всегда, для (ковариантного) Functor просто fmap ψ φ= ψ. φ".

Где (контравариантный) Functor - это все функции с общим результатом - type G a = forall r. a → r type G a = forall r. a → r здесь Contravariant экземпляр был бы cmap ψ φ = φ. ψ cmap ψ φ = φ. ψ.

Но что, черт возьми, это значит

φ :: a → b и ψ :: b → c

поэтому обычно (ψ. φ) x = ψ (φ x) или x ↦ y = φ x и y ↦ ψ y имеет смысл, что в выражении для cmap:

φ :: a → b но ψ :: c → a

поэтому ψ не может взять результат φ но может преобразовать свои аргументы во что-то, что φ может использовать - поэтому x ↦ y = ψ x и y ↦ φ y - единственный правильный выбор.

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

                 covariant
f a ─── fmap φ ───▶ f b ─── fmap ψ ───▶ f c
 ▲                   ▲                   ▲
 │                   │                   │
 │                   │                   │
 a ─────── φ ──────▶ b ─────── ψ ──────▶ c


               contravariant
g a ◀─── cmap φ ─── g b ◀─── cmap ψ ─── g c
 ▲                   ▲                   ▲
 │                   │                   │
 │                   │                   │
 a ─────── φ ──────▶ b ─────── ψ ──────▶ c

Примечание:

В математике обычно требуется закон, чтобы назвать что-то функтором.

        covariant
   a                        f a
  │  ╲                     │    ╲
φ │   ╲ ψ.φ   ══▷   fmap φ │     ╲ fmap (ψ.φ)
  ▼    ◀                   ▼      ◀  
  b ──▶ c                f b ────▶ f c
    ψ                       fmap ψ

       contravariant
   a                        f a
  │  ╲                     ▲    ▶
φ │   ╲ ψ.φ   ══▷   cmap φ │     ╲ cmap (ψ.φ)
  ▼    ◀                   │      ╲  
  b ──▶ c                f b ◀─── f c
    ψ                       cmap ψ

что эквивалентно высказыванию

fmap ψ . fmap φ = fmap (ψ.φ)

в то время как

cmap φ . cmap ψ = cmap (ψ.φ)

Ответ 3

Во-первых, заметка о нашем друге, классе Functor

Вы можете думать о Functor f как утверждение, что никогда не появляется в "отрицательной позиции". a Это эзотерический термин для этой идеи: обратите внимание, что в следующих типах данных переменная " a выступает в качестве переменной "result".

• newtype IO a = IO (World → (World, a))

• newtype Identity a = Identity a

• newtype List a = List (forall r. r → (a → List a → r) → r)

В каждом из этих примеров a появляется в положительной позиции. В некотором смысле a для каждого типа представляет "результат" функции. Это может помочь думать о во втором примере, как a () → a. И это может помочь вспомнить, что третий пример эквивалентен data List a = Nil | Cons a (List a) data List a = Nil | Cons a (List a). В обратных вызовах, таких как a → List → r a появляется в отрицательной позиции, но сам обратный вызов находится в отрицательной позиции, поэтому отрицательные и отрицательные множители должны быть положительными.

Эта схема для подписи параметров функции разработана в этом замечательном сообщении в блоге.

Теперь обратите внимание, что каждый из этих типов допускает Functor. Это не ошибка! Функторы предназначены для моделирования идеи категориальных ковариантных функторов, которые "сохраняют порядок стрелок", то есть fa → fb в отличие от fb → fa. В Haskell, типы которых никогда не появляется в отрицательном положении всегда допускают a Functor. Мы говорим, эти типы ковариантны на. a

Другими словами, можно правильно переименовать класс Functor в Covariant. Это одна и та же идея.

Причина, по которой эта идея так странно сформулирована словом "никогда", заключается в том, что a может появляться как в положительном, так и в отрицательном месте, и в этом случае мы говорим, что тип инвариантен относительно a. a также может никогда не появиться (например, фантомный тип), и в этом случае мы говорим, что тип является одновременно ковариантным и контравариантным относительно a bivariant.

Вернуться к Контравариант

Таким образом, для типов, где a никогда не появляется в положительной позиции, мы говорим, что тип является контравариантным в a. Каждый такой тип Foo a допускает instance Contravariant Foo. Вот несколько примеров, взятых из contravariant пакета:

• data Void a ( это фантом) a
• data Unit a = Unit ( это фантом снова) a
• newtype Const constant a = Const constant
• newtype WriteOnlyStateVariable a = WriteOnlyStateVariable (a → IO())
• newtype Predicate a = Predicate (a → Bool)
• newtype Equivalence a = Equivalence (a → a → Bool)

В этих примерах a является либо бивариантным, либо просто контравариантным. a либо никогда не появляется, либо является отрицательным (в этих надуманных примерах a всегда появляется перед стрелкой, поэтому определить это очень просто). В результате каждый из этих типов допускает instance Contravariant.

Более интуитивным упражнением было бы прищуриться на эти типы (которые демонстрируют контравариантность), а затем коситься на вышеприведенные типы (которые демонстрируют ковариацию) и посмотреть, можете ли вы интуитивно понять разницу в семантическом значении a. Может быть, это полезно, или, может быть, это все еще заумная ловкость рук.

Когда они могут быть практически полезны? Давайте, например, захотим разделить список файлов cookie по типам чипов. У нас есть chipEquality :: Chip → Chip → Bool. Чтобы получить Cookie → Cookie → Bool, мы просто оцениваем runEquivalence. contramap cookie2chip. Equivalence $ chipEquality runEquivalence. contramap cookie2chip. Equivalence $ chipEquality runEquivalence. contramap cookie2chip. Equivalence $ chipEquality.

Довольно многословно! Но решение проблемы многословия, вызванного новым типом, должно быть другим вопросом...

Другие ресурсы (добавьте ссылки здесь, как вы их найдете)

• 24 дня взлома: контравариантный

• Ковариация, контравариантность, положительные и отрицательные позиции

• Я люблю профессоров

• Обсуждение: Веселье с профессорами: я не могу переоценить, насколько хорош этот разговор

Ответ 4

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

Во-первых, совет: не читайте contraMap функции contraMap используя ту же мысленную метафору для f что и при чтении хорошей старой map Functor.

Вы знаете, как вы думаете:

"вещь, которая содержит (или производит) и t "

... когда вы читаете тип, как ft?

Ну, в этом случае вам нужно прекратить это делать.

Контравариантный функтор является "двойственным" по contraMap с классическим функтором, поэтому, когда вы видите fa в contraMap, вам следует подумать о "двойной" метафоре:

ft это вещь, которая потребляет t

Теперь тип contraMap должен начать contraMap смысл:

contraMap :: (a → b) → fb...

... тут пауза, и тип совершенно разумный

1. Функция, которая "производит" a b.
2. Вещь, которая "потребляет" b.

Первый аргумент готовит b. Второй аргумент ест b.

Имеет смысл, верно?

Теперь закончите писать тип:

contraMap :: (a → b) → fb → fa

Таким образом, в конце концов, это дело должно принести "потребитель ". a

Ну, конечно, мы можем построить это, учитывая, что наш первый аргумент - это функция, которая принимает a качестве входных данных.

Функция (a → b) должна быть хорошим строительным блоком для построения "потребителя a ".

Поэтому contraMap основном позволяет вам создать нового "потребителя", вот так (предупреждение: входящие составленные символы):

(takes a as input/produces b as output) ~~> (consumer of b)

• Слева от моего contraMap символа: первый аргумент contraMap (т.е. (a → b)).
• Справа: второй аргумент (т. fb).
• Все это склеено: конечный результат contraMap (вещь, которая знает, как использовать a, то есть fa).