Haskell中非空叶子树的应用实例

Question

给定以下数据类型:

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).

Answer 1

即使它编译,我对这个实现非常怀疑.我不知道这个分支(Leaf(+1))(Leaf(+2))<*> Leaf 7应该返回Leaf 8(找到最接近的函数)或复制并返回Branch(Leaf 8)(Leaf 9)

合理的实例应遵循Applicative functor法律,其中之一是:

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

即

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)