listhaskellapplicativearrowstraversable

How could sequence be written down for Arrows?


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:

  1. sequenceArr :: (Traversable t, Arrow a) => t (a b c) -> a b (t c) - can we write this down? If so, how?
  2. 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)?
  3. 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)?

Solution

  • 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.)