Являются ли все контейнеры фиксированного размера сильными моноидальными функторами и / или наоборот?

9

Класс Applicativeтипов представляет слабые моноидальные функторы, которые сохраняют декартову моноидальную структуру в категории типизированных функций.

Другими словами, учитывая канонические изоморфизмы, свидетельствующие о том, что (,)образуется моноидальная структура:

-- Implementations left to the motivated reader
assoc_fwd :: ((a, b), c) -> (a, (b, c))
assoc_bwd :: (a, (b, c)) -> ((a, b), c)

lunit_fwd :: ((), a) -> a
lunit_bwd :: a -> ((), a)

runit_fwd :: (a, ()) -> a
runit_bwd :: a -> (a, ())

Класс типов и его законы можно эквивалентно записать так:

class Functor f => Applicative f
  where
  zip :: (f a, f b) -> f (a, b)
  husk :: () -> f ()

-- Laws:

-- assoc_fwd >>> bimap id zip >>> zip
-- =
-- bimap zip id >>> zip >>> fmap assoc_fwd

-- lunit_fwd
-- =
-- bimap husk id >>> zip >>> fmap lunit_fwd

-- runit_fwd
-- =
-- bimap id husk >>> zip >>> fmap runit_fwd

Можно было бы удивительно , что функтор , который oplax моноидальный относительно ту же структуру может выглядеть так:

class Functor f => OpApplicative f
  where
  unzip :: f (a, b) -> (f a, f b)
  unhusk :: f () -> ()

-- Laws:

-- assoc_bwd <<< bimap id unzip <<< unzip
-- =
-- bimap unzip id <<< unzip <<< fmap assoc_bwd

-- lunit_bwd
-- =
-- bimap unhusk id <<< unzip <<< fmap lunit_bwd

-- runit_bwd
-- =
-- bimap id unhusk <<< unzip <<< fmap runit_bwd

Если мы думаем о типах, используемых в определениях и законах, неутешительная истина раскрывается; OpApplicativeне более конкретное ограничение, чем Functor:

instance Functor f => OpApplicative f
  where
  unzip fab = (fst <$> fab, snd <$> fab)
  unhusk = const ()

Однако, хотя каждый Applicativeфунктор (на самом деле, любой Functor) тривиален OpApplicative, не обязательно есть хорошие отношения между Applicativeслабостями и OpApplicativeпрозрачностями. Таким образом, мы можем искать сильные моноидальные функторы относительно декартовой моноидальной структуры:

class (Applicative f, OpApplicative f) => StrongApplicative f

-- Laws:
-- unhusk . husk = id
-- husk . unhusk = id
-- zip . unzip = id
-- unzip . zip = id

Первый закон, приведенный выше, тривиален, поскольку единственным обитателем этого типа () -> ()является функция тождественности ().

Тем не менее, оставшиеся три закона, и , следовательно, сам подкласс, является не тривиальной. В частности, не каждый Applicativeявляется законным примером этого класса.

Вот некоторые Applicativeфункторы, для которых мы можем объявить законные случаи StrongApplicative:

  • Identity
  • VoidF
  • (->) r
  • Monoid m => (,) m (Посмотри ответы)
  • Vec (n :: Nat)
  • Stream (Бесконечный)

И вот некоторые Applicativeиз которых мы не можем:

  • []
  • Either e
  • Maybe
  • NonEmptyList

Приведенная здесь схема предполагает, что StrongApplicativeкласс в некотором смысле является FixedSizeклассом, где «фиксированный размер» * означает, что множественность ** жителей одного aиз жителей f aявляется фиксированной.

Это можно сформулировать как две гипотезы:

  • Каждый Applicativeпредставляющий «фиксированный размер» контейнер элементов своего аргумента типа является экземпляромStrongApplicative
  • Не StrongApplicativeсуществует экземпляра, в котором число вхождений aможет варьироваться

Может ли кто-нибудь подумать о контрпримерах, опровергающих эти предположения, или о некоторых убедительных рассуждениях, демонстрирующих, почему они истинны или ложны?


* Я понимаю, что не правильно определил прилагательное «фиксированный размер». К сожалению, задача немного круглая. Я не знаю ни одного формального описания контейнера «фиксированного размера», и пытаюсь придумать его. StrongApplicativeмоя лучшая попытка до сих пор.

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

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

** Под «множественностью» я имею в виду в произвольном смысле «сколько» произвольных элементов типа параметра функтора встречается у обитателя типа фомена функтора. Это не имеет отношения к конкретному типу, к которому применяется функтор, и, следовательно, не относится к каким-либо конкретным обитателям типа параметра.

Не точная информация об этом привела к некоторой путанице в комментариях, поэтому вот несколько примеров того, что я бы посчитал размером / множественностью различных функторов:

  • VoidF: фиксированный, 0
  • Identity: фиксированный, 1
  • Maybe: переменная, минимум 0, максимум 1
  • []: переменная, минимум 0, максимум бесконечно
  • NonEmptyList: переменная, минимум 1, максимум бесконечно
  • Stream: фиксированный, бесконечный
  • Monoid m => (,) m: фиксированный, 1
  • data Pair a = Pair a a: фиксированный, 2
  • Either x: переменная, минимум 0, максимум 1
  • data Strange a = L a | R a: фиксированный, 1
Асад Саидуддин
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Самуэль Лью
Одно из возможных определений «фиксированного размера» будет «представимым». Все представимые функторы являются сильными аппликативами в смысле, описанном здесь, потому что (->) rесть и они изоморфны в правильном направлении к этому.
Даниэль Вагнер
@DanielWagner Я думаю, вам нужно больше, чем просто изоморфизм, чтобы унаследовать сильное аппликативное от (->) r; вам нужны компоненты изоморфизма, чтобы сохранить сильную аппликативную структуру. По какой-то причине у Representableкласса типов в Haskell есть загадочный tabulate . return = returnзакон (который на самом деле даже не имеет смысла для немонадных функторов), но он дает нам 1/4 от условий, которые мы должны сказать, tabulateи zipявляются морфизмами подходящей категории моноидов. , Остальные 3 - это дополнительные законы, которые вы должны требовать.
Асад Саидуддин
Извините, это должно быть " tabulateи indexявляются морфизмами подходящей категории ..."
Асад Саидуддин
@AsadSaeeduddin То, как закон изложен в документах, возможно, странно специфично, но, оказывается, требование returnне является серьезной проблемой. cotraverse getConst . Constявляется реализацией по умолчанию для return/ pureв терминах Distributive, и, поскольку дистрибутивы / представительства имеют фиксированную форму, эта реализация является уникальной.
дублировать

Ответы:

4
  • Каждый Applicativeпредставляющий «фиксированный размер» контейнер элементов своего аргумента типа является экземпляромStrongApplicative
  • Не StrongApplicativeсуществует экземпляра, в котором число вхождений aможет варьироваться

Может ли кто-нибудь подумать о контрпримерах, опровергающих эти предположения, или о некоторых убедительных рассуждениях, демонстрирующих, почему они истинны или ложны?

Я не уверен насчет этой первой гипотезы, и, основываясь на обсуждениях с @AsadSaeeduddin, это, вероятно, будет трудно доказать, но вторая гипотеза верна. Чтобы понять почему, рассмотрим StrongApplicativeзакон husk . unhusk == id; то есть для всех x :: f (), husk (unhusk x) == x. Но в Haskell, unhusk == const ()так что закон равносильно тому, для всех x :: f (), husk () == x. Но это, в свою очередь, подразумевает, что может существовать только одно отдельное значение типа f (): если было два значения x, y :: f (), то x == husk ()и husk () == y, так x == y. Но если существует только одно возможное f ()значение, то оно fдолжно иметь фиксированную форму. (Например, для data Pair a = Pair a a, есть только одно значение типа Pair (), это существо Pair () (), но есть несколько значений типа Maybe ()или [()].) Таким образомhusk . unhusk == idподразумевает, что он fдолжен быть фиксированной формы.

bradrn
источник
Гектометр Действительно ли ясно, что "может существовать только одно отдельное значение типа f ()" подразумевается "число вхождений, aкоторые не могут варьироваться" в присутствии причудливых GADT и прочего?
Даниэль Вагнер
@DanielWagner Оказалось, что «количество вхождений aне может варьироваться» не является достаточным условием для StrongApplicativeэкземпляра; например, data Writer w a = Writer (w,a)имеет неизменную кратность a, но не является StrongApplicative. Вам на самом деле нужно, чтобы форма функтора была инвариантной, и я считаю, что это следствие того, f ()что она является одиночной.
Bradrn
Я не уверен, что вижу, как это актуально. В ответе, подтверждая вторую гипотезу, вы утверждаете, что «сильный аппликативный» подразумевает «одно отдельное f ()», подразумевает «число вхождений aне может варьироваться». Я возражаю, что последний шаг этого аргумента не совсем верно; например рассмотреть data Weird a where One :: a -> Weird a; None :: Weird Bool. Существует отдельное значение типа Weird (), но разные конструкторы имеют различное число as внутри. (Это не полный контрпример, потому что Functorэто сложно, но как мы узнаем, что это не может быть исправлено?)
Даниэль Вагнер
@DanielWagner Хорошая мысль, что Weird ()это синглтон, но он не имеет фиксированной формы. Но Weirdэто не Functorтак, так что не может быть в StrongApplicativeлюбом случае. Я полагаю, что соответствующая гипотеза была бы такой: если « fа» Functor, означает f ()ли «синглтон» fфиксированную форму ? Я сильно подозреваю, что это правда, но, как вы заметили, у меня пока нет никаких доказательств.
bradrn
5

Мы можем ответить хотя бы на один из этих вопросов отрицательно:

Каждый Applicative, представляющий контейнер «фиксированного размера» с элементами своего аргумента типа, является экземпляром StrongApplicative

На самом деле один из примеров законности StrongApplicativeв исходном вопросе неверен. Писатель аппликативен Monoid => (,) mне так StrongApplicative, потому что к примеру husk $ unhusk $ ("foo", ()) == ("", ()) /= ("foo", ()).

Аналогично, пример контейнера фиксированного размера:

data Strange a = L a | R a

фиксированной кратности 1, не является сильным аппликативным, потому что, если мы определяем, husk = Leftто husk $ unhusk $ Right () /= Right (), и наоборот. Эквивалентный способ увидеть это состоит в том, что это всего лишь писатель, применимый для выбора моноида Bool.

Таким образом, существуют аппликативы «фиксированного размера», которых нет StrongApplicative. Все ли StrongApplicatives имеют фиксированный размер, еще неизвестно.

оборота Асад Саидуддин
источник
5

Давайте возьмем представимые функторы в качестве нашего определения «контейнера фиксированного размера»:

class Representable f where
    type Rep f
    tabulate :: (Rep f -> a) -> f a
    index :: f a -> Rep f -> a

Реальное Representableимеет несколько законов и суперклассов, но для целей этого ответа нам действительно нужны только два свойства:

tabulate . index = id
index . tabulate = id

(Хорошо, нам также нужен законопослушный instance StrongApplicative ((->) r). Легко, ты уже согласен, что он существует.)

Если мы примем это определение, то я могу подтвердить эту гипотезу 1:

Каждый Applicativeпредставляющий «фиксированный размер» контейнер элементов своего аргумента типа является [законопослушным] экземпляромStrongApplicative

правда. Вот как:

instance Representable f => Applicative f where
    zip (fa, fb) = tabulate (zip (index fa, index fb))
    husk = tabulate . husk

instance Representable f => OpApplicative f where
    unzip fab = let (fa, fb) = unzip (index fab) in (tabulate fa, tabulate fb)
    unhusk = unhusk . index

instance Representable f => StrongApplicative f

Есть много законов, которые нужно доказать, но я сосредоточусь только на Большой четверке, которая StrongApplicativeдобавляет - вы, вероятно, уже верите в вводные Applicativeи OpApplicative, но если нет, их доказательства выглядят так же, как приведенные ниже ( которые в свою очередь очень похожи друг на друга). Для ясности я буду использовать zipf, huskfи т. Д. Для экземпляра функции, и zipr, huskrи т. Д. Для представимого экземпляра, чтобы вы могли отслеживать, какой есть какой. (И чтобы легко было убедиться, что мы не принимаем то, что пытаемся доказать, как допущение! Это нормально использовать unhuskf . huskf = idпри доказательстве unhuskr . huskr = id, но было бы неправильно предполагать unhuskr . huskr = idэто же доказательство.)

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

unhuskr . huskr
= { def. of unhuskr and huskr }
(unhuskf . index) . (tabulate . huskf)
= { index . tabulate = id }
unhuskf . huskf
= { unhuskf . huskf = id }
id

huskr . unhuskr
= { def. of huskr and unhuskr }
(tabulate . huskf) . (unhuskf . index)
= { huskf . unhuskf = id }
tabulate . index
= { tabulate . index = id }
id

zipr (unzipr fab)
= { def. of unzipr }
zipr (let (fa, fb) = unzipf (index fab) in (tabulate fa, tabulate fb))
= { def. of zipr }
let (fa, fb) = unzipf (index fab) in tabulate (zipf (index (tabulate fa), index (tabulate fb)))
= { index . tabulate = id }
let (fa, fb) = unzipf (index fab) in tabulate (zipf (fa, fb))
= { def. of (fa, fb) }
tabulate (zipf (unzipf (index fab)))
= { zipf . unzipf = id }
tabulate (index fab)
= { tabulate . index = id }
fab

unzipr (zipr (fa, fb))
= { def. of zipr }
unzipr (tabulate (zipf (index fa, index fb)))
= { def. of unzipr }
let (fa', fb') = unzipf (index (tabulate (zipf (index fa, index fb))))
in (tabulate fa', tabulate fb')
= { index . tabulate = id }
let (fa', fb') = unzipf (zipf (index fa, index fb))
in (tabulate fa', tabulate fb')
= { unzipf . zipf = id }
let (fa', fb') = (index fa, index fb)
in (tabulate fa', tabulate fb')
= { def. of fa' and fb' }
(tabulate (index fa), tabulate (index fb))
= { tabulate . index = id }
(fa, fb)
Даниэль Вагнер
источник
В настоящее время размышлял: instance StrongApplicative f => Representable f where type Rep f = forall x. f x -> x. indexэто просто. Я еще не разработал трюк tabulate, но это кажется мучительно близко.
Даниэль Вагнер
В разговоре с @AsadSaeeduddin мне удалось найти этот же StrongApplicativeэкземпляр, но я не смог доказать законы. Поздравляю с этим! Я тоже пытался сделать Representableпример StrongApplicative, но не мог придумать хороший Repтип - мне было бы интересно узнать, как вы forall x. f x -> xэтого добиваетесь?
bradrn
@bradrn Напомним, что гипотеза состоит в том, что эти вещи имеют фиксированный набор «дырок», в которые элементы вставляются. Тогда функции типа forall x. f x -> x- это именно те функции, которые выбирают отверстие и возвращают значение в этом отверстии. (И, думая о том, как это осуществить tabulate, я выдвинул возражение против типа unhusk; подробности см. В комментариях к самому вопросу.)
Даниэль Вагнер,
Спасибо @DanielWagner! Это действительно умный подход - я бы не подумал об этом.
Bradrn
После попытки реализовать это, я не думаю, что я убежден, что forall x. f x -> xбудет работать как Rep. Я считаю, что, используя это Rep, вы можете писать indexдля любого типа, а не только для одногоStrongApplicative - поэтому я подозреваю, что это forall x. f x -> xможет быть слишком общим.
bradrn