A free functor is left adjoint to a forgetful functor. For the adjunction you need to have the isomorphism (natural in x and y):
(Free y :~> x) <-> (y :~> Forget x)
In what category should this be? The forgetful functor forgets the Arrow instance, so it goes from the category of Arrow instances to the category of all bifunctors. And the free functor goes the other way, it turns any bifunctor into a free Arrow instance.
The haskell type of arrows in the category of bifunctors is:
type x :~> y = forall a b. x a b -> y a b
It’s the same for arrows in the category of Arrow instances, but with addition of Arrow constraints. Since the forgetful functor only forgets the constraint, we don’t need to represent it in Haskell. This turns the above isomorphism into two functions:
leftAdjunct :: (FreeA x :~> y) -> x :~> y
rightAdjunct :: Arrow y => (x :~> y) -> FreeA x :~> y
leftAdjunct should also have an Arrow y constraint, but it turns out it is never needed in the implementation. There’s actually a very simple implementation in terms of the more useful unit:
unit :: x :~> FreeA x
leftAdjunct f = f . unit
unit is your effect and rightAdjunct is your evalA. So you have exactly the functions needed for the adjunction! You’d need to show that leftAdjunct and rightAdjunct are isomorphic. The easiest way to do that is to prove that rightAdjunct unit = id, in your case evalA effect = id, which is straightforward.
What about analyze? That’s evalA specialized to the constant arrow, with the resulting Monoid constraint specialized to the applicative monoid. I.e.
analyze visit = getApp . getConstArr . evalA (ConstArr . Ap . visit)
with
newtype ConstArr m a b = ConstArr { getConstArr :: m }
and Ap from the reducers package. (Edit: since GHC 8.6 it is also in base in Data.Monoid)
Edit: I almost forgot, FreeA should be a higher order functor! Edit2: Which, on second thought, can also be implemented with rightAdjunct and unit.
hfmap :: (x :~> y) -> FreeA x :~> FreeA y
hfmap f = evalA (effect . f)
By the way: There’s another way to define free functors, for which I put a package on Hackage recently. It does not support kind * -> * -> * (Edit: it does now!), but the code can be adapted to free arrows:
newtype FreeA eff a b = FreeA { runFreeA :: forall arr. Arrow arr => (eff :~> arr) -> arr a b }
evalA f a = runFreeA a f
effect a = FreeA $ \k -> k a
instance Category (FreeA f) where
id = FreeA $ const id
FreeA f . FreeA g = FreeA $ \k -> f k . g k
instance Arrow (FreeA f) where
arr f = FreeA $ const (arr f)
first (FreeA f) = FreeA $ \k -> first (f k)
second (FreeA f) = FreeA $ \k -> second (f k)
FreeA f *** FreeA g = FreeA $ \k -> f k *** g k
FreeA f &&& FreeA g = FreeA $ \k -> f k &&& g k
If you don’t need the introspection your FreeA offers, this FreeA is probably faster.