Control.Monad.Free.Ap

"Applicative Effects in Free Monads"

Often times, the (\<*\>) operator can be more efficient than ap. Conventional free monads don't provide any means of modeling this. The free monad can be modified to make use of an underlying applicative. But it does require some laws, or else the (\<*\>) = ap law is broken. When interpreting this free monad with foldFree, the natural transformation must be an applicative homomorphism. An applicative homomorphism hm :: (Applicative f, Applicative g) => f x -> g x will satisfy these laws.

• hm (pure a) = pure a

• hm (f <*> a) = hm f <*> hm a

This is based on the "Applicative Effects in Free Monads" series of articles by Will Fancher

• Applicative Effects in Free Monads
• More on Applicative Effects in Free Monads

Documentation

class Monad m => MonadFree f m | m -> f where

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 join [[a]] smashes the lists flat.

On the other hand, consider:

data Tree a = Bin (Tree a) (Tree a) | Tip a

instance Monad Tree where
  return = 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:

instance MonadFree Pair Tree where
   wrap (Pair l r) = Bin l r

Or we could choose to program with Free Pair instead of Tree 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.

Minimal complete definition

Nothing

Methods

wrap :: f (m a) -> m a

Add a layer.

wrap (fmap f x) ≡ wrap (fmap return x) >>= f

default wrap :: (m ~ t n, MonadTrans t, MonadFree f n, Functor f) => f (m a) -> m a

Instances

Monad m => MonadFree Identity (IterT m)

Defined in Control.Monad.Trans.Iter

Methods

wrap :: Identity (IterT m a) -> IterT m a

Functor f => MonadFree f (Free f)

Defined in Control.Monad.Free

Methods

wrap :: f (Free f a) -> Free f a

Applicative f => MonadFree f (Free f)

Defined in Control.Monad.Free.Ap

Methods

wrap :: f (Free f a) -> Free f a

Functor f => MonadFree f (F f)

Defined in Control.Monad.Free.Church

Methods

wrap :: f (F f a) -> F f a

(Functor f, MonadFree f m) => MonadFree f (ListT m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (ListT m a) -> ListT m a

(Functor f, MonadFree f m) => MonadFree f (MaybeT m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (MaybeT m a) -> MaybeT m a

(Functor f, Monad m) => MonadFree f (FreeT f m)

Defined in Control.Monad.Trans.Free

Methods

wrap :: f (FreeT f m a) -> FreeT f m a

(Applicative f, Monad m) => MonadFree f (FreeT f m)

Defined in Control.Monad.Trans.Free.Ap

Methods

wrap :: f (FreeT f m a) -> FreeT f m a

MonadFree f (FT f m)

Defined in Control.Monad.Trans.Free.Church

Methods

wrap :: f (FT f m a) -> FT f m a

(Functor f, MonadFree f m, Error e) => MonadFree f (ErrorT e m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (ErrorT e m a) -> ErrorT e m a

(Functor f, MonadFree f m) => MonadFree f (ExceptT e m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (ExceptT e m a) -> ExceptT e m a

(Functor f, MonadFree f m) => MonadFree f (IdentityT m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (IdentityT m a) -> IdentityT m a

(Functor f, MonadFree f m) => MonadFree f (ReaderT e m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (ReaderT e m a) -> ReaderT e m a

(Functor f, MonadFree f m) => MonadFree f (StateT s m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (StateT s m a) -> StateT s m a

(Functor f, MonadFree f m) => MonadFree f (StateT s m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (StateT s m a) -> StateT s m a

(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (WriterT w m a) -> WriterT w m a

(Functor f, MonadFree f m, Monoid w) => MonadFree f (WriterT w m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (WriterT w m a) -> WriterT w m a

(Functor f, MonadFree f m) => MonadFree f (ContT r m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (ContT r m a) -> ContT r m a

(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (RWST r w s m a) -> RWST r w s m a

(Functor f, MonadFree f m, Monoid w) => MonadFree f (RWST r w s m)

Defined in Control.Monad.Free.Class

Methods

wrap :: f (RWST r w s m a) -> RWST r w s m a

data Free f a

A free monad given an applicative

Constructors

Pure a

Free (f (Free f a))

Instances

MonadTrans Free

This is not a true monad transformer. It is only a monad transformer "up to retract".

Defined in Control.Monad.Free.Ap

Methods

lift :: Monad m => m a -> Free m a

Functor f => Generic1 (Free f :: Type -> Type)

Defined in Control.Monad.Free.Ap

Associated Types

type Rep1 (Free f) :: k -> Type

Methods

from1 :: forall (a :: k). Free f a -> Rep1 (Free f) a

to1 :: forall (a :: k). Rep1 (Free f) a -> Free f a

Applicative f => MonadFree f (Free f)

Defined in Control.Monad.Free.Ap

Methods

wrap :: f (Free f a) -> Free f a

MonadError e m => MonadError e (Free m)

Defined in Control.Monad.Free.Ap

Methods

throwError :: e -> Free m a

catchError :: Free m a -> (e -> Free m a) -> Free m a

MonadReader e m => MonadReader e (Free m)

Defined in Control.Monad.Free.Ap

Methods

ask :: Free m e

local :: (e -> e) -> Free m a -> Free m a

reader :: (e -> a) -> Free m a

MonadState s m => MonadState s (Free m)

Defined in Control.Monad.Free.Ap

Methods

get :: Free m s

put :: s -> Free m ()

state :: (s -> (a, s)) -> Free m a

MonadWriter e m => MonadWriter e (Free m)

Defined in Control.Monad.Free.Ap

Methods

writer :: (a, e) -> Free m a

tell :: e -> Free m ()

listen :: Free m a -> Free m (a, e)

pass :: Free m (a, e -> e) -> Free m a

Applicative f => MonadFix (Free f)

Defined in Control.Monad.Free.Ap

Methods

mfix :: (a -> Free f a) -> Free f a

Foldable f => Foldable (Free f)

Defined in Control.Monad.Free.Ap

Methods

fold :: Monoid m => Free f m -> m

foldMap :: Monoid m => (a -> m) -> Free f a -> m

foldMap' :: Monoid m => (a -> m) -> Free f a -> m

foldr :: (a -> b -> b) -> b -> Free f a -> b

foldr' :: (a -> b -> b) -> b -> Free f a -> b

foldl :: (b -> a -> b) -> b -> Free f a -> b

foldl' :: (b -> a -> b) -> b -> Free f a -> b

foldr1 :: (a -> a -> a) -> Free f a -> a

foldl1 :: (a -> a -> a) -> Free f a -> a

toList :: Free f a -> [a]

null :: Free f a -> Bool

length :: Free f a -> Int

elem :: Eq a => a -> Free f a -> Bool

maximum :: Ord a => Free f a -> a

minimum :: Ord a => Free f a -> a

sum :: Num a => Free f a -> a

product :: Num a => Free f a -> a

Eq1 f => Eq1 (Free f)

Defined in Control.Monad.Free.Ap

Methods

liftEq :: (a -> b -> Bool) -> Free f a -> Free f b -> Bool

Ord1 f => Ord1 (Free f)

Defined in Control.Monad.Free.Ap

Methods

liftCompare :: (a -> b -> Ordering) -> Free f a -> Free f b -> Ordering

Read1 f => Read1 (Free f)

Defined in Control.Monad.Free.Ap

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Free f a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Free f a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Free f a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Free f a]

Show1 f => Show1 (Free f)

Defined in Control.Monad.Free.Ap

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Free f a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Free f a] -> ShowS

Traversable f => Traversable (Free f)

Defined in Control.Monad.Free.Ap

Methods

traverse :: Applicative f0 => (a -> f0 b) -> Free f a -> f0 (Free f b)

sequenceA :: Applicative f0 => Free f (f0 a) -> f0 (Free f a)

mapM :: Monad m => (a -> m b) -> Free f a -> m (Free f b)

sequence :: Monad m => Free f (m a) -> m (Free f a)

Alternative v => Alternative (Free v)

This violates the Alternative laws, handle with care.

Defined in Control.Monad.Free.Ap

Methods

empty :: Free v a

(<|>) :: Free v a -> Free v a -> Free v a

some :: Free v a -> Free v [a]

many :: Free v a -> Free v [a]

Applicative f => Applicative (Free f)

Defined in Control.Monad.Free.Ap

Methods

pure :: a -> Free f a

(<*>) :: Free f (a -> b) -> Free f a -> Free f b

liftA2 :: (a -> b -> c) -> Free f a -> Free f b -> Free f c

(*>) :: Free f a -> Free f b -> Free f b

(<*) :: Free f a -> Free f b -> Free f a

Functor f => Functor (Free f)

Defined in Control.Monad.Free.Ap

Methods

fmap :: (a -> b) -> Free f a -> Free f b

(<$) :: a -> Free f b -> Free f a

Applicative f => Monad (Free f)

Defined in Control.Monad.Free.Ap

Methods

(>>=) :: Free f a -> (a -> Free f b) -> Free f b

(>>) :: Free f a -> Free f b -> Free f b

return :: a -> Free f a

MonadPlus v => MonadPlus (Free v)

This violates the MonadPlus laws, handle with care.

Defined in Control.Monad.Free.Ap

Methods

mzero :: Free v a

mplus :: Free v a -> Free v a -> Free v a

MonadCont m => MonadCont (Free m)

Defined in Control.Monad.Free.Ap

Methods

callCC :: ((a -> Free m b) -> Free m a) -> Free m a

Apply f => Apply (Free f)

Defined in Control.Monad.Free.Ap

Methods

(<.>) :: Free f (a -> b) -> Free f a -> Free f b

(.>) :: Free f a -> Free f b -> Free f b

(<.) :: Free f a -> Free f b -> Free f a

liftF2 :: (a -> b -> c) -> Free f a -> Free f b -> Free f c

Apply f => Bind (Free f)

Defined in Control.Monad.Free.Ap

Methods

(>>-) :: Free f a -> (a -> Free f b) -> Free f b

join :: Free f (Free f a) -> Free f a

Foldable1 f => Foldable1 (Free f)

Defined in Control.Monad.Free.Ap

Methods

fold1 :: Semigroup m => Free f m -> m

foldMap1 :: Semigroup m => (a -> m) -> Free f a -> m

toNonEmpty :: Free f a -> NonEmpty a

Traversable1 f => Traversable1 (Free f)

Defined in Control.Monad.Free.Ap

Methods

traverse1 :: Apply f0 => (a -> f0 b) -> Free f a -> f0 (Free f b)

sequence1 :: Apply f0 => Free f (f0 b) -> f0 (Free f b)

(Typeable f, Data a, Data (f (Free f a))) => Data (Free f a)

Defined in Control.Monad.Free.Ap

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Free f a -> c (Free f a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Free f a)

toConstr :: Free f a -> Constr

dataTypeOf :: Free f a -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Free f a))

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Free f a))

gmapT :: (forall b. Data b => b -> b) -> Free f a -> Free f a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Free f a -> r

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Free f a -> r

gmapQ :: (forall d. Data d => d -> u) -> Free f a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> Free f a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Free f a -> m (Free f a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Free f a -> m (Free f a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Free f a -> m (Free f a)

Generic (Free f a)

Defined in Control.Monad.Free.Ap

Associated Types

type Rep (Free f a) :: Type -> Type

Methods

from :: Free f a -> Rep (Free f a) x

to :: Rep (Free f a) x -> Free f a

(Read1 f, Read a) => Read (Free f a)

Defined in Control.Monad.Free.Ap

Methods

readsPrec :: Int -> ReadS (Free f a)

readList :: ReadS [Free f a]

readPrec :: ReadPrec (Free f a)

readListPrec :: ReadPrec [Free f a]

(Show1 f, Show a) => Show (Free f a)

Defined in Control.Monad.Free.Ap

Methods

showsPrec :: Int -> Free f a -> ShowS

show :: Free f a -> String

showList :: [Free f a] -> ShowS

(Eq1 f, Eq a) => Eq (Free f a)

Defined in Control.Monad.Free.Ap

Methods

(==) :: Free f a -> Free f a -> Bool

(/=) :: Free f a -> Free f a -> Bool

(Ord1 f, Ord a) => Ord (Free f a)

Defined in Control.Monad.Free.Ap

Methods

compare :: Free f a -> Free f a -> Ordering

(<) :: Free f a -> Free f a -> Bool

(<=) :: Free f a -> Free f a -> Bool

(>) :: Free f a -> Free f a -> Bool

(>=) :: Free f a -> Free f a -> Bool

max :: Free f a -> Free f a -> Free f a

min :: Free f a -> Free f a -> Free f a

type Rep1 (Free f :: Type -> Type)

Defined in Control.Monad.Free.Ap

type Rep1 (Free f :: Type -> Type) = D1 ('MetaData "Free" "Control.Monad.Free.Ap" "free-5.2-8yEobwXBbzsEnejCWouYBv" 'False) (C1 ('MetaCons "Pure" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: C1 ('MetaCons "Free" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (f :.: Rec1 (Free f))))

type Rep (Free f a)

Defined in Control.Monad.Free.Ap

type Rep (Free f a) = D1 ('MetaData "Free" "Control.Monad.Free.Ap" "free-5.2-8yEobwXBbzsEnejCWouYBv" 'False) (C1 ('MetaCons "Pure" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "Free" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (f (Free f a)))))

retract :: Monad f => Free f a -> f a

retract is the left inverse of lift and liftF

retract . lift = id
retract . liftF = id

liftF :: (Functor f, MonadFree f m) => f a -> m a

A version of lift that can be used with just a Functor for f.

iter :: Applicative f => (f a -> a) -> Free f a -> a

Given an applicative homomorphism from f to Identity, tear down a Free Monad using iteration.

iterA :: (Applicative p, Applicative f) => (f (p a) -> p a) -> Free f a -> p a

Like iter for applicative values.

iterM :: (Monad m, Applicative f) => (f (m a) -> m a) -> Free f a -> m a

Like iter for monadic values.

hoistFree :: (Applicative f, Applicative g) => (forall a. f a -> g a) -> Free f b -> Free g b

Lift an applicative homomorphism from f to g into a monad homomorphism from Free f to Free g.

foldFree :: (Applicative f, Monad m) => (forall x. f x -> m x) -> Free f a -> m a

Given an applicative homomorphism, you get a monad homomorphism.

toFreeT :: (Applicative f, Monad m) => Free f a -> FreeT f m a

Convert a Free monad from Control.Monad.Free.Ap to a FreeT monad from Control.Monad.Trans.Free.Ap. WARNING: This assumes that liftF is an applicative homomorphism.

cutoff :: Applicative f => Integer -> Free f a -> Free f (Maybe a)

Cuts off a tree of computations at a given depth. If the depth is 0 or less, no computation nor monadic effects will take place.

Some examples (n ≥ 0):

cutoff 0     _        == return Nothing

cutoff (n+1) . return == return . Just

cutoff (n+1) . lift   ==   lift . liftM Just

cutoff (n+1) . wrap   ==  wrap . fmap (cutoff n)

Calling 'retract . cutoff n' is always terminating, provided each of the steps in the iteration is terminating.

unfold :: Applicative f => (b -> Either a (f b)) -> b -> Free f a

Unfold a free monad from a seed.

unfoldM :: (Applicative f, Traversable f, Monad m) => (b -> m (Either a (f b))) -> b -> m (Free f a)

Unfold a free monad from a seed, monadically.

_Pure :: forall f m a p. (Choice p, Applicative m) => p a (m a) -> p (Free f a) (m (Free f a))

This is Prism' (Free f a) a in disguise

>>> preview _Pure (Pure 3)
Just 3

>>> review _Pure 3 :: Free Maybe Int
Pure 3

_Free :: forall f m a p. (Choice p, Applicative m) => p (f (Free f a)) (m (f (Free f a))) -> p (Free f a) (m (Free f a))

This is Prism' (Free f a) (f (Free f a)) in disguise

>>> preview _Free (review _Free (Just (Pure 3)))
Just (Just (Pure 3))

>>> review _Free (Just (Pure 3))
Free (Just (Pure 3))