Despite the jargon filled title I don't think this question is very complex.
Introducing the characters
There are two important Functor combinators at play here. Flip equivalent to the haskell functiong flip but operating on types
newtype Flip p a b
= Flip
{ unFlip :: p b a
}
and Join equivalent to the W combinator on types, it takes a bifunctor and produces a functor along both its arguments
newtype Join p a
= W
{ unW :: p a a
}
Traversable
Now for Foldable it is possible to make the following instance:
instance
( forall a . Foldable (p a)
, forall a . Foldable (Flip p a)
)
=> Foldable (Join p) where
foldr g x (W xs) = foldr g (foldr g x xs) (Flip xs)
That is to say if p is foldable across both of its arguments then Join p is foldable. This is done by folding across the left and then the right.
Now I would like to make an analogous instance for Traversable, however I run into a problem. I can write sequence easily enough
sequence (W xs) = (map W . join . map (sequenceA . unFlip) . sequenceA . Flip) xs
However it seems that I need to be able to use join so I am having trouble writing sequenceA. In fact it very much seems impossible to write a sequenceA.
However I struggle to come up with a counter example. That is a p which is traversable on two arguments but not traversable when joined.
So far I've tried all the basics but none are counter examples. Join (,) is traversable
sequenceA (W (x, y)) = liftA2 (W . (,)) x y
Higher order tuples such as Join ((,,) a) are fine.
sequenceA (W (x, y, z)) = liftA2 (W . (,,) x) y z
Join Either is also traversable
sequenceA (W (Left x)) = map (W . Left) x
sequenceA (W (Right x)) = map (W . Right) x
I've come up with more examples by composing types around, which I will leave out for simplicity but needless to say they all ended up being traversable.
Is there a counter example? Can this instance be written?
