title: Structurally enforced Free Alternative, without left distributivity
body: <p>There is a nice <a href="http://hackage.haskell.org/package/free-4.12.4/docs/Control-Alternative-Free.html" rel="noreferrer">Free Alternative</a> in the great <em>free</em> package, which lifts a Functor to a left-distributive Alternative.</p>
  
  <p>That is, the claim is that:</p>
  
  <pre><code>runAlt :: Alternative g =&gt; (forall x. f x -&gt; g x) -&gt; Alt f a -&gt; g a
  </code></pre>
  
  <p>is an <em>Alternative homomorphism</em>, with <code>liftAlt</code>.  And, indeed, it <em>is</em> one, but only for <a href="https://wiki.haskell.org/Typeclassopedia#Laws_6" rel="noreferrer"><em>left-distributive</em></a> Alternative instances.</p>
  
  <p>Of course, in reality, very few Alternative instances are actually left-distributive.  Most of the alternative instances that actually matter (parsers, MaybeT f for most Monad f, etc.) are not left-distributive.  This fact can be shown by an example where <code>runAlt</code> and <code>liftAlt</code> do not form an Alternative homomorphism:</p>
  
  <pre><code>(writeIORef x False &lt;|&gt; writeIORef True) *&gt; (guard =&lt;&lt; readIORef x)
  -- is an IO action that throws an exception
  runAlt id $ (liftAlt (writeIORef x False) &lt;|&gt; liftAlt (writeIORef True))
                 *&gt; liftAlt (guard =&lt;&lt; readIORef x)
  -- is an IO action that throws no exception and returns successfully ()
  </code></pre>
  
  <p>So <code>runAlt</code> is only an Alternative homomorphism for some Alternatives, but not all.  This is because the structure of <code>Alt</code> <em>normalizes</em> all actions to distribute over the left.</p>
  
  <p><code>Alt</code> is great because, structurally, <code>Alt f</code> is a lawful <code>Applicative</code> and <code>Alternative</code>.  There isn't any possible way to construct a value of type <code>Alt f a</code> using the Applicative and Alternative functions that don't follow the laws...the structure of the type itself is what makes it a free Alternative.</p>
  
  <p>Just like, for lists, you can't construct a list using <code>&lt;&gt;</code> and <code>mempty</code> that doesn't respect <code>x &lt;&gt; mempty = x</code>, <code>mempty &lt;&gt; x = x</code>, and associativity.</p>
  
  <p>I've written a Free alternative that <em>doesn't</em> enforce the Applicative and Alternative laws, structurally, but <em>does</em> yield a valid Alternative and Applicative homomorphism with runAlt/liftAlt:</p>
  
  <pre><code>data Alt :: (* -&gt; *) -&gt; * -&gt; * where
      Pure  :: a   -&gt; Alt f a
      Lift  :: f a -&gt; Alt f a
      Empty :: Alt f a
      Ap    :: Alt f (a -&gt; b) -&gt; Alt f a -&gt; Alt f b
      Plus  :: Alt f as -&gt; Alt f as -&gt; Alt f as
  
  instance Functor f =&gt; Functor (Alt f) where
      fmap f = \case
        Pure x     -&gt; Pure (f x)
        Lift x     -&gt; Lift (f &lt;$&gt; x)
        Empty      -&gt; Empty
        Ap fs xs   -&gt; Ap ((f .) &lt;$&gt; fs) xs
        Plus xs ys -&gt; Plus (f &lt;$&gt; xs) (f &lt;$&gt; ys)
  
  instance Functor f =&gt; Applicative (Alt f) where
      pure  = Pure
      (&lt;*&gt;) = Ap
  
  instance Functor f =&gt; Alternative (Alt f) where
      empty = Empty
      (&lt;|&gt;) = Plus
  </code></pre>
  
  <p>structurally, <code>Alt f</code> is not an actual <code>Applicative</code>, because:</p>
  
  <pre><code>pure f &lt;*&gt; pure x = Ap (Pure f) (Pure x)
  pure (f x)        = Pure (f x)
  </code></pre>
  
  <p>So <code>pure f &lt;*&gt; pure x</code> is not the same as <code>pure (f x)</code>, structurally.  Not a valid Applicative, right off the bat.</p>
  
  <p><em>But</em>, with the given <code>runAlt</code> and <code>liftAlt</code>:</p>
  
  <pre><code>liftAlt :: f a -&gt; Alt f a
  liftAlt = Lift
  
  runAlt :: Alternative g =&gt; (forall x. f x -&gt; g x) -&gt; Alt f a -&gt; g a
  runAlt f = \case
    Pure x     -&gt; pure x
    Lift x     -&gt; f x
    Empty      -&gt; empty
    Ap fs xs   -&gt; runAlt f fs &lt;*&gt; runAlt f xs
    Plus xs ys -&gt; runAlt f xs &lt;|&gt; runAlt f ys
  </code></pre>
  
  <p>And <code>runAlt</code> here does indeed act as a valid Applicative homomorphism with a given natural transformation...</p>
  
  <p>One could say that my new <code>Alt f</code> is a valid Alternative and Applicative when quotiented by the equivalence relationship defined by <code>runAlt</code>, i suppose.</p>
  
  <p>Anyway, this is only slightly unsatisfying.  Is there any way to write a free Alternative that is <em>structurally</em> a valid Alternative and Applicative, <em>without</em> enforcing left distributivity?</p>
  
  <p>(In particular, I'm actually interested in one that follows the <a href="https://wiki.haskell.org/Typeclassopedia#Laws_6" rel="noreferrer">left catch</a> law, and enforces it structurally.  This would be a separate and also interesting thing, but not completely necessary.)</p>
  
  <p>And, if there isn't any way, why not?</p>