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.
I'm aware that there's an applicative "family", as described by https://duplode.github.io/posts/divisible-and-the-monoidal-quartet.html.
I'm 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, I'm 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)?
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
variantsApplyMagma
The
ApplyMagma
class has exactly the same methods as theApply
class, but it doesn't need to follow the associativity law.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:
If
Apply
is analogous to semigroups,ApplyCommute
is analogous to commutative semigroups.Traversable1
variantsTraversable1Magma
A
Traversable1Magma
can be seen as aTraversable1
with more information provided about the structure. While theFoldable1
class has atoNonEmpty
method, TheFoldable1Magma
class could have atoBinaryTree
method.Traversable1Commute
A
Traversable1Commute
can be seen as aTraversable1
without a defined ordering to the elements. If it didn't require anOrd a
constraint,Set
fromcontainers
could be an instance of this class. Traversable1Commute could be a superclass of Traversable1.Note that these are variants of
Traversable1
because neitherApplyMagma
norApplyCommute
have a function equivalent topure
.ContraTraversable
ContraTraversable
does not have any instances. To see why, look at the type of thecontraTraverse
function.We can specialize this to the following:
Which is eqivalent to the following:
Using
const
and theconquer
function from Divisible, this allows us to create a value of any type, which is impossible.