Does a joined Bitraversable require Monad?

121 Views Asked by At

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?

0

There are 0 best solutions below