There's a myth floating around that "Arrow is much less useful because it
forces you to implement arr".  In fact, Arrow without arr would be as
useless as Applicative without fmap.  In almost all situations where you are
stymied by arr a small redesign will solve the whole problem.  In fact, you
need to get into the realm of linear-types-like things before arr is too
much (and even then a *linear* arr would be fine).

I designed a library for constructing Postgres queries and it uses an Arrow
interface.

    https://hackage.haskell.org/package/opaleye-0.5.3.0/docs/Opaleye-Internal-QueryArr.html

Naturally there is no way to run an arbitrary Haskell function "in the
database".  This is not an impediment because everything that the database
acts on inside the arrow type (QueryArr) is wrapped in an abstract type
(Column).  This means the only way that arbitrary Haskell functions can be
used inside the arrow is as a sort of "partial compilation".  There is, in
effect, a staging restriction.  Haskell functions a -> b run at "query
compile time" and Postgres functions run at "query run time".

Hm. Interesting point. And a nice coincidence that you call Applicative without fmap "useless". I just recently saw one of those. It *did* feel like there might be a better structure, but I couldn't pin it down. Maybe your technique works in that context as well? Would you mind having a look? I'd like to have my eyes opened in that direction.

The structure in question are XML-Picklers, i.e. tools to convert to and from XML. The original types are from HXT, but for the purpose of discussion we can simplify them to

    data PU a = PU { appPickle   :: a -> XmlState -> XmlState                    -- turn a value into XML
                   , appUnPickle :: XmlState -> (Either UnpickleErr a, XmlState) -- turn XML into a value
                   }
    
    -- "pure"
    xpLift :: a -> PU a
    xpLift x =  PU { appPickle   = const id
                   , appUnPickle = pure x
                   }    
   
    -- Combine two picklers sequentially
    -- If the first fails during unpickling, the whole unpickler fails
    xpSeq :: (b -> a) -> PU a -> (a -> PU b) -> PU b
    xpSeq f pa k
       = PU { appPickle   = ( \ b -> let a = f b in appPickle pa a . appPickle (k a) b )
            , appUnPickle = appUnPickle pa >>= (appUnPickle . k)    
            }

    -- Pickle a pair of values sequentially
    xpPair :: PU a -> PU b -> PU (a, b)
    xpPair pa pb = ( xpSeq fst pa (\ a -> xpSeq snd pb (\ b -> xpLift (a,b))) )

    -- The closest equivalent to "fmap"
    xpWrap :: (a -> b, b -> a) -> PU a -> PU b 

Now: This is not exactly an Applicative. If it where a functor, it would be a (lax) monoidal functor. Taking syntax from the Typeclassopedia, xpPair would be Monoidal's (**). And a (lax) monoidal functor is exactly an Applicative. If I'm not mistaken this structure satisfies all the laws of Monoidal – except that it is not a functor.

Obviously there's no way to implement fmap because you always need to provide functions for both directions, as seen in xpWrap. So how would you change this structure to make it possible?

It feels like the underlying problem is the same as with arr: At first there seems to be no way to lift functions into the structure. And we don't want to create two separate types because the whole idea of PU is to make pairs of related picklers and unpicklers composable.