i've been on a bit of a "distilling everything to its fundamentals" kick lately, and i've been unable to find clear theoretical reasons for how the Traversable typeclass is defined, only practical ones of "it's useful to be able to traverse over applicative coalgebras, and lots of datatypes can do it" and a whole lot of hints

im aware that there's an applicative "family", as described by https://duplode.github.io/posts/divisible-and-the-monoidal-quartet.html

im also aware that while Traversable traversals are applicative coalgebras, the Traversable1 typeclass from 'semigroupoids' describes apply coalgebras, and the Distributive typeclass from 'distributive' describes functor algebras

additionally, im aware that Foldable, Foldable1, and theoretical fold family members, describe datatypes that can be folded using monoids, semigroups, and corresponding monoid family members such as magmas (for folding as a binary tree) and commutative versions of each (for folding as unordered versions of each)

as such, as Traversable is a subclass of Foldable, i assume it's monoidal in nature, and similarly i assume Traversable1 is semigroupal in nature, and Distributive is comonoidal in nature (as mentioned in its description in the 'distributive' package)

this feels like the right track, but where do Applicative and Apply come from here? are there magmatic and commutative versions? would there be a distributive family in a category with non-trivial comonoids?

essentially, my question is "do these typeclasses exist, and what are they? if not, why not?":

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?

presumably less important bonus question: while attempting to research this i came across the 'data-functor-logistic' package https://hackage.haskell.org/package/data-functor-logistic

this describes a version of Distributive over contravariant functors - is there an equivalent Traversable over Divisibles (or Decidables)?

CodePudding user response：

I'm not aware of any library that implements those classes, but I'll try to unravel what those classes would represent. I am a programmer, not a category theorist, so take this with a grain of salt.

Applicative variants

ApplyMagma

The ApplyMagma class has exactly the same methods as the Apply class, but it doesn't need to follow the associativity law.

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

If Apply is analogous to semigroups, ApplyMagma is analogous to magmas.

ApplyCommute

The ApplyCommute class will be equivalent to the Apply class but with the following commutativity law:

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

If Apply is analogous to semigroups, ApplyCommute is analogous to commutative semigroups.

Traversable1 variants

Traversable1Magma

A Traversable1Magma can be seen as a Traversable1 with more information provided about the structure. While the Foldable1 class has a toNonEmpty method, The Foldable1Magma class could have a toBinaryTree method.

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

Traversable1Commute

A Traversable1Commute can be seen as a Traversable1 without a defined ordering to the elements. If it didn't require an Ord a constraint, Set from containers could be an instance of this class. Traversable1Commute could be a superclass of Traversable1.

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

Note that these are variants of Traversable1 because neither ApplyMagma nor ApplyCommute have a function equivalent to pure.

ContraTraversable

ContraTraversable does not have any instances. To see why, look at the type of the contraTraverse function.

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

We can specialize this to the following:

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

Which is eqivalent to the following:

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

Using const and the conquer function from Divisible, this allows us to create a value of any type, which is impossible.