Почему в основном обходы определяются над аппликативами?

Question

В последнее время я был немного увлечен «перегонкой всего к его основам», и мне не удалось найти четких теоретических причин того, как определяется класс типов Traversable, только практические из «полезно иметь возможность проходить над аппликативными коалгебрами, и многие типы данных могут это сделать» и множество подсказок.

Я знаю, что существует аппликативная «семья», как описано в https://duplode.github.io/posts/divisible-and-the-monoidal-quartet.html.

Я также знаю, что в то время как обходы Traversable являются аппликативными коалгебрами, класс типов Traversable1 из «semigroupoids» описывает прикладные коалгебры, а класс типов Distributive из «distributive» описывает функторные алгебры.

Кроме того, я знаю, что Foldable, Foldable1 и теоретические члены семейства fold описывают типы данных, которые можно свернуть с помощью моноидов, полугрупп и соответствующих членов семейства моноидов, таких как магмы (для сворачивания в виде бинарного дерева) и коммутативные версии каждого ( для складывания как неупорядоченные версии каждого).

Таким образом, поскольку Traversable является подклассом Foldable, я предполагаю, что он моноидальный по своей природе, и аналогичным образом я предполагаю, что Traversable1 является полугрупповым по своей природе, а Distributive — комоноидальным по своей природе (как указано в его описании в «дистрибутивном» пакете).

Кажется, это правильный путь, но откуда здесь взялись Applicative и Apply? Существуют ли магматическая и коммутативная версии? Будет ли дистрибутивное семейство в категории с нетривиальными комоноидами?

По сути, мой вопрос: «Существуют ли эти классы типов и что они из себя представляют? Если нет, то почему?»:

      class FoldableMagma t => TraversableMagma t where
    traverseMagma :: ??? f => (a -> f b) -> (t a -> f (t b))
class FoldableCommute t => TraversableCommute t where
    traverseCommute :: ??? f => (a -> f b) -> (t a -> f (t b))
class Foldable t => ContraTraversable t where
    contraTraverse :: Divisible f => (b -> f a) -> (t a -> f (t b))
-- im really not sure on this last one
-- but it's how i'd expect an endofunctor over coalgebras to look
-- which seems potentially related to traversables?

Предположительно менее важный бонусный вопрос: пытаясь исследовать это, я наткнулся на пакет «data-functor-logistic» https://hackage.haskell.org/package/data-functor-logistic .

Это описывает версию Distributive над контравариантными функторами - существует ли эквивалент Traversable над Divisibles (или Decidables)?

Answer 1

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

Applicativeварианты

Класс имеет точно такие же методы, как и класс, но ему не нужно следовать закону ассоциативности.

      class Functor f => ApplyMagma f where
    (<.>) :: f (a -> b) -> f a -> f b

Если аналогично полугруппам, аналогично магмам.

Класс ApplyCommute будет эквивалентен классу Apply, но со следующим законом коммутативности:

      f <$> x <.> y = flip f <$> y <.> x

Если Applyаналогична полугруппам, аналогична коммутативным полугруппам.

варианты

А Traversable1Magmaможно рассматривать как с дополнительной информацией о структуре. В то время как Foldable1класс имеет toNonEmptyметод, Foldable1Magmaкласс может иметь toBinaryTreeметод.

      class (FoldableMagma t, Traversable1 t) => Traversable1Magma t where
    traverseMagma :: ApplyMagma f => (a -> f b) -> (t a -> f (t b))

А Traversable1Commuteможно рассматривать как без определенного порядка элементов. Если бы это не требовало Ord aограничение, Setиз containersможет быть экземпляром этого класса.Traversable1Commute может быть надклассом Traversable1.

      class (FoldableCommute t, Functor t) => Traversable1Commute t where
    traverseCommute :: ApplyCommute f => (a -> f b) -> (t a -> f (t b))

Обратите внимание, что это варианты Traversable1потому что ни ApplyMagmaни ApplyCommuteиметь функцию, эквивалентную pure.

ContraTraversableне имеет экземпляров. Чтобы понять почему, посмотрите на тип contraTraverseфункция.

      contraTraverse :: Divisible f => (b -> f a) -> (t a -> f (t b))

Мы можем специализироваться на следующем:

      contraTraverse :: Monoid b => (b -> Op b a) -> (t a -> Op b (t b))

Что эквивалентно следующему:

      contraTraverse ~ Monoid b => (b -> a -> b) -> t a -> t b -> a

С использованием constи conquerфункция от Divisible, это позволяет нам создать значение любого типа, что невозможно.

Answer 2

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

Без каких-либо ограничений он может описывать только необитаемые типы данных, например:

      data V1 a
instance VTraversable V1 where
    vtraverse _ = \case
-- uninhabited types can be pattern matched to create any result type

Если бы это был Functor, он мог бы описывать алгебраические типы данных примерно так:

      data FTrav1 a = FTrav1 a
instance FTraversable FTrav1 where
    ftraverse strat (FTrav1 a) = FTrav1 <$> strat a

data FTrav2 a = FTrav2_1 a | FTrav2_2 (FTrav1 a)
instance FTraversable FTrav2 where
    ftraverse strat (FTrav2_1 a) = FTrav2_1 <$> strat a
    ftraverse strat (FTrav2_2 fa) = FTrav2_2 <$> ftraverse strat fa

По сути, это любой тип данных с произвольным (потенциально бесконечным, если бы это можно было описать в Haskell) числом конструкторов одного аргумента FTraversable (гдеa~Identity a). Это говорит о том, что любой Traversablef aизоморфен(f (), a), функтор Writer.

Представление Apply позволяет использовать дополнительные типы данных, такие как следующие:

      data ApplyTrav1 a = ApplyTrav1 a a
instance Traversable1 ApplyTrav1 where
    traverse1 strat (ApplyTrav1 a a) = ApplyTrav1 <$> strat a <*> strat a

data ApplyTrav2 a = ApplyTrav2_1 a (ApplyTrav1 a) | ApplyTrav2_2 (ApplyTrav1 a) a
instance Traversable1 ApplyTrav2 where
    traverse1 strat (ApplyTrav2_1 a fa) = ApplyTrav2_1 <$> strat a <*> traverse1 strat fa
    traverse1 strat (ApplyTrav2_2 fa a) = ApplyTrav2_2 <$> traverse1 strat fa <*> traverse1 strat a

Теперь конструкторы могут иметь произвольное количество аргументов, если это конечное число больше нуля! Теперь изоморфизм(f (), NonEmpty a), где они одинакового размера.

Applicative позволяет следующее:

      data ApplicTrav a = ApplicTrav0 | ApplicTrav a a
instance Traversable ApplicTrav where
    traverse _ ApplicTrav0 = pure ApplicTrav0
    traverse strat (ApplicTrav a a) = ApplicTrav <$> strat a <*> strat a

Теперь разрешены пустые конструкторы! Теперь изоморфизм(f (), [a]).

Гипотетический коммутативный Applicative использовался бы для коммутативных алгебраических типов данных, если бы они были - возможно, если бы Set навязал, что его можно складывать только с коммутативными моноидами, они были бы актуальны! Но, насколько мне известно, коммутативные типы данных не являются основной частью Haskell, поэтому такая форма обхода не будет отображаться для алгебраических типов данных.

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

Насколько мне известно, логистика не связана с этой алгебраической интерпретацией - поскольку функтор Reader обычно используется с Distributives для создания набора функций-получателей, Logistic предназначен для работы с контравариантным функтором Op для создания набора функций-установщиков.

Это наводит меня на мысль, что эквивалента для Traversable не существует из-за функтора Writer, который характеризует Traversables как собственную противоположность ((r,a)изоморфен(a,r)).