Applicative instance for non-empty leafy tree in Haskell

Question

Given the following data type:

data Tree a =
    Branch (Tree a) (Tree a)
  | Leaf a deriving (Eq, Show)

And the following Functor instance :

instance Functor Tree where
  fmap f (Leaf a)       = Leaf $ f a
  fmap f (Branch t1 t2) = Branch (fmap f t1) (fmap f t2)

How to implement best the Applicative instance for this tree? I came up with:

instance Applicative Tree where
  pure = Leaf

  Leaf f       <*> t            = f <$> t
  Branch t1 t2 <*> Leaf a       = t1 <*> Leaf a
  Branch t1 t2 <*> Branch t3 t4 = Branch (t1 <*> t3) (t2 <*> t4)

Even if it compiles, I'm very suspicious about this implementation. I don't know if this Branch (Leaf (+1)) (Leaf (+2)) <*> Leaf 7 should return Leaf 8 (find the closest function to apply) or duplicate and return Branch (Leaf 8) (Leaf 9).

Answer 1

Even if it compiles, I'm very suspicious about this implementation. I don't know if this Branch (Leaf (+1)) (Leaf (+2)) <*> Leaf 7 should return Leaf 8 (find the closest function to apply) or duplicate and return Branch (Leaf 8) (Leaf 9)

Reasonable instances should follow Applicative functor laws and one of them is:

u <*> pure y = pure ($ y) <*> u -- Interchange

i.e.

Branch t1 t2 <*> Leaf a

should be the same as:

pure ($ a) <*> Branch t1 t2

But according to this implementation:

Leaf f <*> t = f <$> t

It should be equal to:

($ a) <$> Branch t1 t2

i. e

Branch (fmap ($ a) t1) (fmap ($ a) t2)

Hence, in the particular case of Branch (Leaf (+1)) (Leaf (+2)) <*> Leaf 7, it should return:

Branch (Leaf 8) (Leaf 9)