haskell - 实现 `Applicative (Free f)`

Question

对于Free Monad :

data Free f a = Var a
               | Node (f (Free f a)) 

我实现了instance Functor (Free f) :

instance Functor f => Functor (Free f) where
  fmap g (Var x)  = Var (g x)
  fmap g (Node x) = Node $ fmap (\y -> fmap g y) x

然后我尝试实现instance Applicative (Free f) :

instance Functor f => Applicative (Free f) where
    pure x                = Var x

我的直觉是var x是 pure 的正确定义.

但是，无论这是否正确，我不确定如何实现<*> .

特别是以下几种情况是否需要支持？请注意，我忽略了 Var 的构成。和Node与 _ .

(Var _) <*> (Var _)
(Var _) <*> (Node _)
(Node _) <*> (Var _)
(Node _) <*> (Node _)

请提示我以上情况是否需要匹配。

另外，请向我提供一个关于这对 Free f a 意味着什么的直觉。实例存在于 <*> 的两侧.

Answer 1

Will Ness 使用 ap 给出了完全合法的答案。如果您内联 ap，您最终会得到以下结果:

instance Functor f => Applicative (Free f) where
  pure = A
  A a <*> A b = A $ a b
  A a <*> F mb = F $ fmap a <$> mb
  F ma <*> b = F $ (<*> b) <$> ma

(注意:free 软件包的最新版本使用此定义，以便尽可能明确。)

如chi showed ，前两种情况可以合并:

  A f <*> x = f <$> x