title: Understand the Applicative problem (#7) in Chapter 12 of "Programming In Haskell"
body: <p>I've been working through the excellent <a href="http://www.cs.nott.ac.uk/~pszgmh/pih.html" rel="nofollow noreferrer">Programming in Haskell (2nd ed)</a>.  I'm a bit flummoxed by the question on Applicatives, though.</p>
  
  <p>Given the following type:</p>
  
  <pre><code>data Expr a = Var a | Val Int | Add (Expr a) (Expr a) deriving Show
  </code></pre>
  
  <p>The question is to write the implementations of the <code>Functor</code>, <code>Applicative</code> and <code>Monad</code> classes.</p>
  
  <p><code>Functor</code> is straightforward, as is <code>Monad</code> (at least it compiles, I've not fully wrapped my head around it yet but I'm more worried about this bit first).</p>
  
  <p>I've come up with this, which compiles, but I have concerns:</p>
  
  <pre><code>instance Applicative Expr where
      -- pure :: a -&gt; Expr a
      pure = Var
  
      -- (&lt;*&gt;) :: Expr (a -&gt; b) -&gt; Expr a -&gt; Expr b
      (Var fab) &lt;*&gt; fa = fmap fab fa
  </code></pre>
  
  <p><code>pure</code> is fine, but I'm worried about the actual applicative operator <code>&lt;*&gt;</code>.  As far as I can tell, it only makes sense for <code>Var</code> - not for <code>Val</code> or <code>Add</code>.  And it just seems weird to me that you'd have a type where's it's legal to express things that can explode - for instance, you could have <code>Add (Var ord) (Val 10)</code> which is of type <code>Expr (Char -&gt; Int)</code>, so would typecheck as the lhs in a <code>&lt;*&gt;</code> expression, but (as it stands) would explode.  And it's not clear to me how the recursive definition would work - because as soon as you hit <code>(Val 10)</code>, you're stuffed - there's no way to convert the rhs to the necessary type.</p>
  
  <p>What am I missing here?  How do I complete the definition of <code>&lt;*&gt;</code> such that things don't explode, and it's still a valid applicative?  Am I right in thinking/feeling that in reality, you wouldn't design a type like this?</p>
  
  <p>Thanks!</p>