title: Applicative instance for free monad
body: <p>While trying to find a haskell monad that can be executed stepwise / allows threading, I discovered the free monad</p>
  
  <pre><code>data Free f a = Return a | Roll (f (Free f a))
  </code></pre>
  
  <p>with its monad instance</p>
  
  <pre><code>instance (Functor f) =&gt; Monad (Free f) where
    return = Return
    Return x    &gt;&gt;= f = f x
    Roll action &gt;&gt;= f = Roll $ fmap (&gt;&gt;= f) action
  </code></pre>
  
  <p>and its functor instance</p>
  
  <pre><code>instance (Functor f) =&gt; Functor (Free f) where
    fmap f (Return x) = Return (f x)
    fmap f (Roll   x) = Roll $ fmap (fmap f) x
  </code></pre>
  
  <p>I know that every monad is an applicative functor with <code>pure = return</code> and <code>(&lt;*&gt;) = ap</code>.
  For me, applicative functors are conceptually harder than monads. For a better understanding of applicative functors, I like to have the applicative instance without resorting to <code>ap</code>.</p>
  
  <p>The first line for <code>&lt;*&gt;</code>is easy:</p>
  
  <pre><code>instance (Applicative f) =&gt; Applicative (Free f) where
    pure = Return
    Return f &lt;*&gt; x = fmap f x -- follows immediately from pure f &lt;*&gt; x = f &lt;$&gt; x
  --Roll   f &lt;*&gt; x = Roll $ (fmap ((fmap f) &lt;*&gt;)) x -- wrong, does not type-check
  </code></pre>
  
  <p>How to define <code>Roll f &lt;*&gt; x</code> in basic terms with <code>fmap</code> and <code>&lt;*&gt;</code>?</p>