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

Question

我最近一直在“提炼一切到它的基础”，我一直无法找到明确的理论原因来解释 Traversable 类型类是如何定义的，只有“能够遍历是有用的”的实际原因在适用的代数上，很多数据类型都可以做到这一点”和很多提示。
我知道有一个应用程序“家庭”，如 https://duplode.github.io/posts/divisible-and-the-monoidal-quartet.html 所述。 .
我还知道，虽然 Traversable 遍历是应用代数，但来自“semigroupoids”的 Traversable1 类型类描述了应用代数，而来自“分布式”的 Distributive 类型类描述了仿函数代数。
此外，我知道 Foldable、Foldable1 和理论折叠家族成员描述了可以使用幺半群、半群和相应的幺半群家族成员折叠的数据类型，例如岩浆(用于折叠为二叉树)和每个 (折叠为每个的无序版本)。
因此，由于 Traversable 是 Foldable 的子类，我假设它本质上是幺半群的，同样我假设 Traversable1 本质上是半群的，而 Distributive 本质上是 comonoidal 的(如“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变体ApplyMagmaApplyMagma类具有与 Apply 完全相同的方法类，但它不需要遵循结合律。

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

如果 Apply类似于半群， ApplyMagma类似于岩浆。 ApplyCommuteApplyCommute 类将等价于 Apply 类，但具有以下交换律:

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

如果 Apply类似于半群， ApplyCommute类似于交换半群。 Traversable1变体 Traversable1Magma一个 Traversable1Magma可以看成 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一个 Traversable1Commute可以看成 Traversable1没有对元素定义的顺序。如果不需要 Ord a约束， Set来自 containers可能是此类的一个实例。 Traversable1Commute 可能是 Traversable1 的父类(super class)。

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

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