Implementing `Applicative (Free f)`

Question

For the Free Monad:

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

I implemented 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

Then I tried to implement instance Applicative (Free f):

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

My intuition is that var x is the right definition of pure.

However, regardless of whether that's correct, I'm not sure how to implement <*>.

In particular, is it necessary to support the following cases? Note that I ignored the make-up of the Var and Node with _.

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

Please give me a hint as to whether the above cases need to be matched.

Also, please provide me with an intuition as to what it means for both Free f a instances to exist on either side of <*>.

`Free` gives you the Free monad. Every monad induces an applicative. So you may gain some insight by implementing the Monad instance first and deriving the Applicative one from it. — gallais, Dec 17 '14 at 14:43
By the applicative laws, `pure f <*> x` is `fmap f x`. This solves the first two cases. Further, the interchange law states that `u <*> pure y = pure ($ y) <*> u` which solves the third case as well. — chi, Dec 17 '14 at 14:43

score 2 · Answer 1 · edited May 23 '17 at 12:15

Will Ness gives a perfectly legitimate answer using ap. If you inline ap, you end up with this:

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

(Note: recent versions of the free package use this definition so as to be as explicit as possible.)

As chi showed, the first two cases can be combined:

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

Will Ness · Answer 2 · 2016-01-02T21:14:09.537

Defining Monad, and using ap for <*> (and return for pure, or course) works:

{-# 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

It is easy to handle the types, mentally, following the same pattern, as

($)                ::   (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)

That's why I used (g <$>) and (k =<<), there.

As for building the intuition, see

 #> 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]]]

Implementing `Applicative (Free f)`

2 Answers2

Linked