Portability | non-portable (rank-2 polymorphism) |
---|---|
Stability | provisional |
Maintainer | Edward Kmett <ekmett@gmail.com> |
Safe Haskell | None |
"Free Monads for Less"
This is based on the "Free Monads for Less" series of articles:
http://comonad.com/reader/2011/free-monads-for-less/ http://comonad.com/reader/2011/free-monads-for-less-2/
- newtype F f a = F {
- runF :: forall r. (a -> r) -> (f r -> r) -> r
- improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f a
- fromF :: MonadFree f m => F f a -> m a
- iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> F f a -> m a
- toF :: Functor f => Free f a -> F f a
- retract :: Monad m => F m a -> m a
- class Monad m => MonadFree f m | m -> f where
- wrap :: f (m a) -> m a
- liftF :: (Functor f, MonadFree f m) => f a -> m a
Documentation
The Church-encoded free monad for a functor f
.
It is asymptotically more efficient to use (>>=
) for F
than it is to (>>=
) with Free
.
MonadTrans F | |
MonadReader e m => MonadReader e (F m) | |
MonadState s m => MonadState s (F m) | |
MonadWriter w m => MonadWriter w (F m) | |
Functor f => MonadFree f (F f) | |
Monad (F f) | |
Functor (F f) | |
MonadFix (F f) | |
MonadPlus f => MonadPlus (F f) | |
Applicative (F f) | |
Alternative f => Alternative (F f) | |
MonadCont m => MonadCont (F m) | |
Apply (F f) | |
Bind (F f) |
improve :: Functor f => (forall m. MonadFree f m => m a) -> Free f aSource
Improve the asymptotic performance of code that builds a free monad with only binds and returns by using F
behind the scenes.
This is based on the "Free Monads for Less" series of articles by Edward Kmett:
http://comonad.com/reader/2011/free-monads-for-less/ http://comonad.com/reader/2011/free-monads-for-less-2/
and "Asymptotic Improvement of Computations over Free Monads" by Janis Voightländer:
iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> F f a -> m aSource
Like iter for monadic values.
class Monad m => MonadFree f m | m -> f whereSource
Monads provide substitution (fmap
) and renormalization (join
):
m>>=
f =join
(fmap
f m)
A free Monad
is one that does no work during the normalization step beyond simply grafting the two monadic values together.
[]
is not a free Monad
(in this sense) because
smashes the lists flat.
join
[[a]]
On the other hand, consider:
data Tree a = Bin (Tree a) (Tree a) | Tip a
instanceMonad
Tree wherereturn
= Tip Tip a>>=
f = f a Bin l r>>=
f = Bin (l>>=
f) (r>>=
f)
This Monad
is the free Monad
of Pair:
data Pair a = Pair a a
And we could make an instance of MonadFree
for it directly:
instanceMonadFree
Pair Tree wherewrap
(Pair l r) = Bin l r
Or we could choose to program with
instead of Free
PairTree
and thereby avoid having to define our own Monad
instance.
Moreover, Control.Monad.Free.Church provides a MonadFree
instance that can improve the asymptotic complexity of code that
constructs free monads by effectively reassociating the use of
(>>=
). You may also want to take a look at the kan-extensions
package (http://hackage.haskell.org/package/kan-extensions).
See Free
for a more formal definition of the free Monad
for a Functor
.
(Functor f, MonadFree f m) => MonadFree f (ListT m) | |
(Functor f, MonadFree f m) => MonadFree f (IdentityT m) | |
(Functor f, MonadFree f m) => MonadFree f (MaybeT m) | |
Functor f => MonadFree f (Free f) | |
Functor f => MonadFree f (Free f) | |
Functor f => MonadFree f (F f) | |
Monad m => MonadFree Identity (IterT m) | |
(Functor f, MonadFree f m, Error e) => MonadFree f (ErrorT e m) | |
(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m) | |
(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m) | |
(Functor f, MonadFree f m) => MonadFree f (ContT r m) | |
(Functor f, MonadFree f m) => MonadFree f (StateT s m) | |
(Functor f, MonadFree f m) => MonadFree f (StateT s m) | |
(Functor f, MonadFree f m) => MonadFree f (ReaderT e m) | |
(Functor f, Monad m) => MonadFree f (FreeT f m) | |
Functor f => MonadFree f (FT f m) | |
(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m) | |
(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m) |