title: Applicative instance for non-empty leafy tree in Haskell
body: <p>Given the following data type:</p>
  
  <pre><code>data Tree a =
      Branch (Tree a) (Tree a)
    | Leaf a deriving (Eq, Show)
  </code></pre>
  
  <p>And the following Functor instance :</p>
  
  <pre><code>instance Functor Tree where
    fmap f (Leaf a)       = Leaf $ f a
    fmap f (Branch t1 t2) = Branch (fmap f t1) (fmap f t2)
  </code></pre>
  
  <p>How to implement best the Applicative instance for this tree?
  I came up with:</p>
  
  <pre><code>instance Applicative Tree where
    pure = Leaf
  
    Leaf f       &lt;*&gt; t            = f &lt;$&gt; t
    Branch t1 t2 &lt;*&gt; Leaf a       = t1 &lt;*&gt; Leaf a
    Branch t1 t2 &lt;*&gt; Branch t3 t4 = Branch (t1 &lt;*&gt; t3) (t2 &lt;*&gt; t4)
  </code></pre>
  
  <p>Even if it compiles, I'm very suspicious about this implementation.
  I don't know if this <code>Branch (Leaf (+1)) (Leaf (+2)) &lt;*&gt; Leaf 7</code> should return <code>Leaf 8</code> (find the closest function to apply) or duplicate and return <code>Branch (Leaf 8) (Leaf 9)</code>.</p>