Is it possible to write join down for Arrows, not ArrowApply?

Question

I tried writing down joinArr :: ??? a => a r (a r b) -> a r b. I came up with a solution which uses app, therefore narrowing the a down to ArrowApply's:

joinArr :: ArrowApply a => a r (a r b) -> a r b
joinArr g = g &&& Control.Category.id >>> app

Is it possible to have this function written down for arrows?

My guess is no.

Control.Monad.join could have been a good stand-in for >>= in the definition of the Monad type class: m >>= k = join $ k <$> m.

Having joinArr :: Arrow a => a r (a r b) (a r b) on our hands, it would be possible to write down instance Arrow a => Monad (ArrowMonad a):

m >>= k = joinArr (k <$> m)

Please note that joinArr should be slightly tweaked to be able to deal with the wrapper. If we speak of ArrowApply:

joinArr :: ArrowApply a => ArrowMonad a (ArrowMonad a b) -> ArrowMonad a b
joinArr (ArrowMonad m) = ArrowMonad $
   m &&& Control.Category.id >>>
   first (arr (\x -> let ArrowMonad h = x in h)) >>> 
   app

instance ArrowApply a => Monad (ArrowMonad a) is already implemented in the source file.

I reckon this argument not to be the best one (if it is right).

Am I right? What is the more formal way to back this up (or disprove it)?

@JosephSible-ReinstateMonica true, that’s what I’m basing my argument on - we can be sure that an Arrow does not give rise to a Monad generally. Yet I reckon joinArr :: Arrow a => a r (a r b) -> a r b to enable us to write this down. Or am I using this fact wrongly? — Zhiltsoff Igor
If you had joinArr, then you could write instance Monad SomeArrowThatIsntAMonad where m >>= f = joinArr (f <$> m). — Joseph Sible-Reinstate Monica
@JosephSible-ReinstateMonica yes, that was my point. At least I think so. How does it differ from my argument? — Zhiltsoff Igor
(1) Looking at it from another direction: between (.), id, arr and first, there isn't anything that allows collapsing two a r layers into one. (2) @JosephSible-ReinstateMonica It's not a particularly enlightening example, perhaps, but Static for any applicative which isn't a monad should suffice. Scan from the foldl library might be a more interesting illustration. — duplode

Jon Purdy Jon Purdy · Accepted Answer · 2020-06-24T04:24:31

I think the formal reason that you can’t implement a x (a x y) -> a x y using only Arrow is that this requires a notion of either application (as you tried) or currying, or rather uncurrying in this case:

uncurry :: a x (a y z) -> a (x, y) z

With that, joinArr is simply:

joinArr :: a x (a x y) -> a x y
joinArr f = dup >>> uncurry f
  where dup = id &&& id

But if we can’t implement this without apply, curry, or uncurry, that means that a must be a Cartesian closed category (CCC) because we need some notion of “exponential” or higher-order arrow, which ArrowApply gives us, but Arrow only gives us a Cartesian category. (And I believe ArrowApply is equivalent to Monad because Monad is a strong monad in a CCC.)

The closest you can get with only Arrow is an Applicative, as you saw in the definition of instance (Arrow a) => Applicative (ArrowMonad a), which happens to be equivalent in power to join in the Reader monad (since there join = (<*> id)), but not the stronger monadic join:

joinArr' :: a x (x -> y) -> a x y
joinArr' f = (f &&& id) >>> arr (uncurry ($))

Note that instead of a higher-order arrow here, a x (a x y), we just reuse the (->) type.

Is it possible to write join down for Arrows, not ArrowApply?

1 Answers