实现` `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

定义Monad，并使用<*>的ap (和pure的return，或课程)工作：

{-# LANGUAGE FlexibleContexts, UndecidableInstances #-}

import Control.Applicative  -- <$>
import Control.Monad        -- ap

data Free f a = A a | F (f (Free f a)) 

instance Functor f => Functor (Free f) where
  fmap g (A a)  = A (g a)
  fmap g (F fv) = F ((g <$>) <$> fv)

instance Functor f => Monad (Free f) where
  return = A
  A a  >>= k = k a
  F fv >>= k = F ((k =<<) <$> fv)

-- ap mf mv = mf >>= \f-> mv >>= \v-> return f v

instance Functor f => Applicative (Free f) where
  pure = return
  fg <*> fv = ap fg fv

-- from http://stackoverflow.com/a/10875756/849891
instance (Show (f (Free f a)), Show a) => Show (Free f a) where
    show (A x)  = " A " ++ show x  
    show (F fv) = " F " ++ show fv 

它是easy to handle the types，在精神上遵循相同的模式，就像

($)                ::   (a -> b) ->   a ->   b
let g=g in (g  $)  ::                 a ->   b
            g      ::   (a -> b)
                                     _____
Functor f =>                        /     \
fmap               ::   (a -> b) -> f a -> f b
let g=g in (g <$>) ::               f a -> f b
            g      ::   (a -> b) 
                       ___________________
Applicative f =>      /             /     \
(<*>)              :: f (a -> b) -> f a -> f b
let h=h in (h <*>) ::               f a -> f b
            h      :: f (a -> b)
                             _____________
Monad m =>                  /.------.     \
(=<<)              :: (a -> m b) -> m a -> m b
let k=k in (k =<<) ::               m a -> m b
            k      :: (a -> m b)

这就是我使用(g <$>)和(k =<<)的原因。

至于建立直觉，请参阅

 #> let x = F [A 10, F [A 20, A 30]]

 #> F[A (+1), A (+2)] <*> x
 F [ F [ A 11, F [ A 21, A 31]], F [ A 12, F [ A 22, A 32]]]

 #> A (+1) <*> F[x, x]
 F [ F [ A 11, F [ A 21, A 31]], F [ A 11, F [ A 21, A 31]]]

 #> (\a-> (+1) <$> F [A a, A (a+1)]) =<< x
 F [ F [ A 11, A 12], F [ F [ A 21, A 22], F [ A 31, A 32]]]

Answer 2

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