haskell - 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

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)

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

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)