haskell - Haskell中非空叶树的适用实例

给定以下数据类型:

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

以及以下Functor实例:

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

如何最好地实现此树的Applicative实例？
我想出了:

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)

即使它可以编译，我对此实现也非常怀疑。
我不知道此Branch (Leaf (+1)) (Leaf (+2)) <*> Leaf 7是否应返回Leaf 8(查找要应用的最接近的函数)或重复并返回Branch (Leaf 8) (Leaf 9)。

最佳答案

合理的实例应遵循Applicative functor laws，其中之一是:

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

IE。

Branch t1 t2 <*> Leaf a

应与以下内容相同:

pure ($ a) <*> Branch t1 t2

但根据此实现:

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

它应等于:

($ a) <$> Branch t1 t2

一世。 Ë

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

因此，在Branch (Leaf (+1)) (Leaf (+2)) <*> Leaf 7的特定情况下，它应返回:

Branch (Leaf 8) (Leaf 9)