title: Useful operations on free arrows
body: <p>We know free monads are useful, and packages like <a href="http://hackage.haskell.org/package/operational/">Operational</a> make it easy to define new monads by only caring about the application-specific effects, not the monadic structure itself.</p>
  
  <p>We can easily define "free arrows" analogous to how free monads are defined:</p>
  
  <pre><code>{-# LANGUAGE GADTs #-}
  module FreeA
         ( FreeA, effect
         ) where
  
  import Prelude hiding ((.), id)
  import Control.Category
  import Control.Arrow
  import Control.Applicative
  import Data.Monoid
  
  data FreeA eff a b where
      Pure :: (a -&gt; b) -&gt; FreeA eff a b
      Effect :: eff a b -&gt; FreeA eff a b
      Seq :: FreeA eff a b -&gt; FreeA eff b c -&gt; FreeA eff a c
      Par :: FreeA eff a₁ b₁ -&gt; FreeA eff a₂ b₂ -&gt; FreeA eff (a₁, a₂) (b₁, b₂)
  
  effect :: eff a b -&gt; FreeA eff a b
  effect = Effect
  
  instance Category (FreeA eff) where
      id = Pure id
      (.) = flip Seq
  
  instance Arrow (FreeA eff) where
      arr = Pure
      first f = Par f id
      second f = Par id f
      (***) = Par
  </code></pre>
  
  <p>My question is, what would be the most useful generic operations on free arrows? For my particular application, I needed special cases of these two:</p>
  
  <pre><code>{-# LANGUAGE Rank2Types #-}
  {-# LANGUAGE ScopedTypeVariables #-}
  analyze :: forall f eff a₀ b₀ r. (Applicative f, Monoid r)
          =&gt; (forall a b. eff a b -&gt; f r)
          -&gt; FreeA eff a₀ b₀ -&gt; f r
  analyze visit = go
    where
      go :: forall a b. FreeA eff a b -&gt; f r
      go arr = case arr of
          Pure _ -&gt; pure mempty
          Seq f₁ f₂ -&gt; mappend &lt;$&gt; go f₁ &lt;*&gt; go f₂
          Par f₁ f₂ -&gt; mappend &lt;$&gt; go f₁ &lt;*&gt; go f₂
          Effect eff -&gt; visit eff
  
  evalA :: forall eff arr a₀ b₀. (Arrow arr) =&gt; (forall a b. eff a b -&gt; arr a b) -&gt; FreeA eff a₀ b₀ -&gt; arr a₀ b₀
  evalA exec = go
    where
      go :: forall a b. FreeA eff a b -&gt; arr a b
      go freeA = case freeA of
          Pure f -&gt; arr f
          Seq f₁ f₂ -&gt; go f₂ . go f₁
          Par f₁ f₂ -&gt; go f₁ *** go f₂
          Effect eff -&gt; exec eff
  </code></pre>
  
  <p>but I don't have any theoretical arguments on why these (and not others) would be the useful ones.</p>