从根本上来说，为什么遍历是在 Applicatives 上定义的？

Question

最近我一直在“将一切提炼为基础”，并且我一直无法找到关于如何定义 Traversable 类型类的明确的理论原因，只有“能够遍历是有用的”的实际原因在应用余代数上，很多数据类型都可以做到这一点”以及很多提示。

我知道有一个适用的“家族”，如https://duplode.github.io/posts/divisible-and-the-monoidal-quartet.html所描述。

我还知道，虽然 Traversable 遍历是应用性余代数，但“semigroupoids”中的 Traversable1 类型类描述了应用性余代数，“distributive”中的 Distributive 类型类描述了函子代数。

此外，我知道 Foldable、Foldable1 和理论折叠家族成员描述了可以使用幺半群、半群和相应的幺半群家族成员（例如岩浆（用于折叠为二叉树）和每个的交换版本）折叠的数据类型（用于折叠为每个的无序版本）。

因此，由于 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

这描述了逆变函子上的分配的一个版本 - 是否存在等效的可整除（或可判定）上的可遍历？

Answer 1

我不知道有任何库实现了这些类，但我会尝试阐明这些类所代表的内容。我是一名程序员，而不是范畴论学家，所以对此持保留态度。

Applicative变体

ApplyMagma

该类ApplyMagma与类具有完全相同的方法Apply，但不需要遵循结合律。

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

如果Apply类似于半群，ApplyMagma则 类似于岩浆。

ApplyCommute

ApplyCommute 类与 Apply 类等效，但具有以下交换律：

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

如果Apply类似于半群，ApplyCommute则类似于交换半群。

Traversable1变体

Traversable1Magma

ATraversable1Magma可以被视为Traversable1提供了有关该结构的更多信息。虽然Foldable1类有一个toNonEmpty方法，但Foldable1Magma类可以有一个toBinaryTree方法。

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

Traversable1Commute

ATraversable1Commute可以被视为Traversable1没有定义元素顺序的 a。如果不需要约束Ord a，Set则 fromcontainers可以是此类的实例。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

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

使用Divisible 中的const函数conquer，这允许我们创建任何类型的值，这是不可能的。