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)

如何最好地实现这棵树的应用实例？我想到了：

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 应该 return Leaf 8 （找到最接近的函数来应用）还是重复 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)

合理的例子应该在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

我。 e

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

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

Branch (Leaf 8) (Leaf 9)

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

Applicative instance for non-empty leafy tree in Haskell

binary-tree

haskell

applicative