How could sequence be written down for Arrows?

Question

sequenceA is a well-known function:

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

I wonder whether we can write down something similar for Arrows. Unfortunately, I did not manage to implement the following:

sequenceArr :: (Traversable t, Arrow a) => t (a b c) -> a b (t c)

As far as I understand, Applicative generalizes Arrow, thus, we should be able to write this down. I did it for lists:

sequenceArrLst :: Arrow a => [a b c] -> a b [c]
sequenceArrLst t = let t' = (>>> arr (: [])) <$> t
                   in foldr1 (\f g -> f &&& g >>> arr (uncurry (++))) t'

Yet as one can notice, we are not getting rid of the a b layer in the list but wrapping the results into a new list. So, how can we actually get rid of the a b layer? I should note that in the comments under this question, duplode pointed out:

...between (.), id, arr and first, there isn't anything that allows collapsing two a r layers into one.

If they are right, would we need ArrowApply for this? Frankly, I wrote this down, still not being able to get rid of the arrow inside t:

sequenceArrApp :: (Functor f, ArrowApply a) => f (a b c) -> a b (f (a () c))
sequenceArrApp t = arr $ \ b -> (\ f -> arr (\ () -> (f, b)) >>> app) <$> t

Could this snippet be tweaked to lack the a () layer?

So, my questions are:

sequenceArr :: (Traversable t, Arrow a) => t (a b c) -> a b (t c) - can we write this down? If so, how?
Are there any ways to get rid of the a b layer (Arrow a). If so, why do they not work when we write join for Arrow down (if they actually do not)?
Do we need ArrowApply for this? If so, how? Could my variant be tweaked to get this result: sequenceArr :: (Traversable t, ArrowApply a) => t (a b c) -> a b (t c)?

I don't understand your complaint about the list version. Are you saying you really want something more like traverseArr :: (Arrow a, Traversable t) => a x y -> a (t x) (t y)? I think that would be a reasonable thing to try to get (whether possible or not, I don't know off the top of my head), but you haven't asked it directly. — dfeuer
The existence of the Traversing class suggests that traverseArr likely isn't available for arbitrary arrows. — dfeuer
@dfeuer yes. I added the direct question. I will look into the Traversing class as I have never heard of it before - thank you. What if we speak not an arbitrary arrow, but an ArrowApply instance? As far as I can remember, sequences used to be fed lists only not so long ago, yet they got generalized. All I am trying to do is to keep up :). — Zhiltsoff Igor
Your sequenceArr likely is possible, with some hackery. See my implementation of traverseBia for inspiration. Something like the sneaky Mag Applicative might prove necessary. — dfeuer
Isn't the sequenceArr you propose at first what you get by specilaising sequenceA to the applicatives we can squeeze out of arrows? Or, in terms of WrappedArrow, unwrapArrow . sequenceA . fmap WrapArrow? — duplode

duplode duplode · Accepted Answer · 2020-07-07T05:51:39

As far as I understand, Applicative generalizes Arrow, thus, we should be able to write this down.

Keeping in mind that "generalizes" here really means "if we pin down the input type argument of an Arrow, the resulting * -> * type constructor will be an Applicative", the sequenceArr you propose at first amounts to sequenceA specialised to the applicatives that can be squeezed from arrows in such a way. As those applicatives can be expressed through the WrappedArrow newtype, one possible definition is:

sequenceArr :: (Traversable t, Arrow a) => t (a b c) -> a b (t c)
sequenceArr = unwrapArrow . sequenceA . fmap WrapArrow

Looking at how WrappedArrow instantiates Applicative...

instance Arrow a => Applicative (WrappedArrow a b) where
    pure x = WrapArrow (arr (const x))
    liftA2 f (WrapArrow u) (WrapArrow v) =
      WrapArrow (u &&& v >>> arr (uncurry f))

... should confirm this implementation agrees in spirit with your attempt at writing sequenceArrLst.

(Note this sequenceArr is indeed very different from traverse' from Data.Profunctors.Traversing that dfeuer discusses in the comments. Rather than being a specialization of sequenceA, traverse' generalizes traverse along, so to speak, a wholly other dimension.)

How could sequence be written down for Arrows?

1 Answers