title: Are free monads also zippily applicative?
body: <p>I think I've come up with an interesting &quot;zippy&quot; <code>Applicative</code> instance for <a href="http://hackage.haskell.org/package/free-5.1/docs/Control-Monad-Free.html#t:Free" rel="nofollow noreferrer"><code>Free</code></a>.</p>
  <pre><code>data FreeMonad f a = Free (f (FreeMonad f a))
                     | Return a
  
  instance Functor f =&gt; Functor (FreeMonad f) where
      fmap f (Return x) = Return (f x)
      fmap f (Free xs) = Free (fmap (fmap f) xs)
  
  instance Applicative f =&gt; Applicative (FreeMonad f) where
      pure = Return
  
      Return f &lt;*&gt; xs = fmap f xs
      fs &lt;*&gt; Return x = fmap ($x) fs
      Free fs &lt;*&gt; Free xs = Free $ liftA2 (&lt;*&gt;) fs xs
  </code></pre>
  <p>It's sort of a zip-longest strategy. For example, using <code>data Pair r = Pair r r</code> as the functor (so <code>FreeMonad Pair</code> is an externally labelled binary tree):</p>
  <pre><code>    +---+---+    +---+---+               +-----+-----+
      |       |    |       |      &lt;*&gt;      |           |
   +--+--+    h    x    +--+--+   --&gt;   +--+--+     +--+--+
   |     |              |     |         |     |     |     |
   f     g              y     z        f x   g x   h y   h z
  </code></pre>
  <p>I haven't seen anyone mention this instance before. Does it break any <code>Applicative</code> laws? (It doesn't agree with the usual <code>Monad</code> instance of course, which is &quot;substitutey&quot; rather than &quot;zippy&quot;.)</p>