Use indexed applicatives

[treeowl]

I believe the right way to define QTraversable is using indexed applicatives. See some old SO questions I asked, and the answers:

https://stackoverflow.com/questions/35123930/how-should-i-traverse-type-aligned-sequences
https://stackoverflow.com/questions/39135193/is-it-possible-to-reverse-type-aligned-traversals

Also, by the way:

https://stackoverflow.com/questions/30985070/how-can-i-express-foldr-in-terms-of-foldmap-for-type-aligned-sequences

[echatav]

Oh yeah, I stole Joachim's answer or something like it to define the RightQ type and the default implementation of qfoldr.

I'm not sure I agree that this is "the right way" to define QTraversable or qtraverse_ though that's a subjective call.

Since the Monoid of Foldable is replaced by a Category for TAFoldable, the Applicative of Traversable has to be replaced by something stronger.

I disagree with this reasoning since the way Applicative is used in Foldable comes down to the proposition that wrapping a Monoid in an Applicative gives a Monoid, and the same is true for a Category.

 (Applicative f, Monoid a) => Monoid (Ap f a)
 (Applicative f, Category c) => Category (ApQ f c)

So there is no need to replace Applicative. That said, it's a very interesting additional construction. I've done a bunch of unreleased work on indexed transformers it reminds me about. I'd be a little hesitant to introduce indexed things here without a stronger case.

[treeowl]

I don't see why you think so.

1. Using an indexed applicative strengthens the analogy QFoldable : QTraversable :: Foldable : Traversable. Specifically, that qtraverse can implement qfoldMap (which is also a great convenience).
2. I don't know this for sure, but I would venture to bet that it's possible to implement my version of qtraverse using your version plus a bunch of horrible machinations. Since it's pretty much trivial to go the other way, I think it's better to do that.

[echatav]

I don't think the analogy is strengthened for the reason I gave, Applicative is not being used as an analogy to Monoid; but rather to construct another Monoid in Foldable via wrapping, so to me the analogy is QFoldable : QTraversable : : ApQ :: Foldable : Traversable : Ap.

Do you have a use case for traversing with IxApplicative? If we were to introduce it, we'd need at least one example. On the other hand, examples of Applicative abound and the use case is something like, I want to do some IO for each step in a Path.

Honestly, QTraversable was somewhat of an afterthought for me so I take you seriously that it may be lacking.

[treeowl]

I realized my point 2 is wrong. In particular, qtraverseAp can perform its effects in any order, while qtraverseIxAp must perform them in their nose-to-tail order. Additionally, if you were to remove the QFoldable constraint from QTraversableAp then you could define reasonable instances for things like

data Pair c a b = Pair (c a b) (c a b)

It really feels to me like QTraverseableAp sits off to the side: a useful thing but not the Traversable analogue.

You ask about why one might wish to traverse in an indexed applicative. The answer is the same as why you'd want to do anything in an indexed applicative. Generally, it's to maintain certain relationships between successive states, or something like that. To traverse in one, you need something (vaguely) Path-like.

How about I put it another way though: the indexed versions are pretty much guaranteed correct by the type checker. That gives you correct non-indexed ones for free!

[echatav]

Indexed applicatives is a fascinating concept that I'd like to have a careful think about. An indexed monad, from the perspective of category theory, is a "category enriched in the monoidal category of endofunctors on Hask with monoidal product given by functor composition" where a monad is a "monoid object in the monoidal category of endofunctors on Hask with monoidal product given by functor composition" and an applicative is a "monoid object in the monoidal category of endofunctors on Hask with monoidal product given by Day convolution". Thus, an indexed applicative should be a "category enriched in the monoidal category of endofunctors on Hask with monoidal product given by Day convolution". I really think it's a worthwhile idea that probably belongs in another library, replete with example instances.