Applicative instance for free monad
While trying to find a haskell monad that can be executed stepwise / allows threading, I discovered the free monad
data Free f a = Return a | Roll (f (Free f a))
with its monad instance
instance (Functor f) => Monad (Free f) where
return = Return
Return x >>= f = f x
Roll action >>= f = Roll $ fmap (>>= f) action
and its functor instance
instance (Functor f) => Functor (Free f) where
fmap f (Return x) = Return (f x)
fmap f (Roll x) = Roll $ fmap (fmap f) x
I know that every monad is an applicative functor with pure = return and (<*>) = ap . For me, applicative functors are conceptually harder than monads. For a better understanding of applicative functors, I like to have the applicative instance without resorting to ap .
The first line for <*> is easy:
instance (Applicative f) => Applicative (Free f) where
pure = Return
Return f <*> x = fmap f x -- follows immediately from pure f <*> x = f <$> x
--Roll f <*> x = Roll $ (fmap ((fmap f) <*>)) x -- wrong, does not type-check
How to define Roll f <*> x in basic terms with fmap and <*> ?
Will this do?
instance (Functor f) => Applicative (Free f) where
pure = Return
Return f <*> as = fmap f as
Roll faf <*> as = Roll (fmap (<*> as) faf)
The plan is to act only at the leaves of the tree which produces the function, so for Return , we act by applying the function to all the argument values produced by the argument action. For Roll , we just do to all the sub-actions what we intend to do to the overall action.
Crucially, what we do when we reach Return is already set before we start. We don't change our plans depending on where we are in the tree. That's the hallmark of being Applicative : the structure of the computation is fixed, so that values depend on values but actions don't.
上一篇: 为什么在Haskell Monads中将“bind”写为>> =？
下一篇: 适用于免费monad的应用程序实例