Implementation "Applicative (free f)"
For Free Monad
:
data Free f a = Var a
| Node (f (Free f a))
I have 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 what var x
is the correct definition pure
.
However, whether or not it is correct, I am not sure how to implement <*>
.
In particular, is it necessary to support the following cases? Please note that I ignored the composition Var
and Node
using _
.
(Var _) <*> (Var _)
(Var _) <*> (Node _)
(Node _) <*> (Var _)
(Node _) <*> (Node _)
Please give me a hint as to whether the above cases should match.
Also, provide me with an intuition as to what it means for both instances to Free f a
exist on either side of <*>
.
source to share
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 types , mentally, following the same scheme 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.
For creating 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]]]
source to share
Will Ness give a perfectly legitimate answer using ap
. If you are inline ap
you get 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 package free
use this definition to be as clear as possible.)
As shown by chi , the first two cases can be combined:
A f <*> x = f <$> x
source to share