Copyright (C) 2008-2013 Edward Kmett BSD-style (see the file LICENSE) Edward Kmett provisional MPTCs, fundeps Safe Haskell2010

Description

Synopsis

The base functor

data FreeF f a b #

The base functor for a free monad.

Constructors

 Pure a Free (f b)

Instances

 Functor f => Bifunctor (FreeF f) # Methodsbimap :: (a -> b) -> (c -> d) -> FreeF f a c -> FreeF f b d #first :: (a -> b) -> FreeF f a c -> FreeF f b c #second :: (b -> c) -> FreeF f a b -> FreeF f a c # # Methodsbitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> FreeF f a b -> f (FreeF f c d) # Foldable f => Bifoldable (FreeF f) # Methodsbifold :: Monoid m => FreeF f m m -> m #bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> FreeF f a b -> m #bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> FreeF f a b -> c #bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> FreeF f a b -> c # Eq1 f => Eq2 (FreeF f) # Methods(==##) :: (Eq a, Eq b) => FreeF f a b -> FreeF f a b -> Bool # Ord1 f => Ord2 (FreeF f) # Methodscompare2 :: (Ord a, Ord b) => FreeF f a b -> FreeF f a b -> Ordering # Show1 f => Show2 (FreeF f) # MethodsshowsPrec2 :: (Show a, Show b) => Int -> FreeF f a b -> ShowS #showList2 :: (Show a, Show b) => [FreeF f a b] -> ShowS # Read1 f => Read2 (FreeF f) # MethodsreadsPrec2 :: (Read a, Read b) => Int -> ReadS (FreeF f a b) #readList2 :: (Read a, Read b) => ReadS [FreeF f a b] # Functor f => Functor (FreeF f a) # Methodsfmap :: (a -> b) -> FreeF f a a -> FreeF f a b #(<$) :: a -> FreeF f a b -> FreeF f a a # Foldable f => Foldable (FreeF f a) # Methodsfold :: Monoid m => FreeF f a m -> m #foldMap :: Monoid m => (a -> m) -> FreeF f a a -> m #foldr :: (a -> b -> b) -> b -> FreeF f a a -> b #foldr' :: (a -> b -> b) -> b -> FreeF f a a -> b #foldl :: (b -> a -> b) -> b -> FreeF f a a -> b #foldl' :: (b -> a -> b) -> b -> FreeF f a a -> b #foldr1 :: (a -> a -> a) -> FreeF f a a -> a #foldl1 :: (a -> a -> a) -> FreeF f a a -> a #toList :: FreeF f a a -> [a] #null :: FreeF f a a -> Bool #length :: FreeF f a a -> Int #elem :: Eq a => a -> FreeF f a a -> Bool #maximum :: Ord a => FreeF f a a -> a #minimum :: Ord a => FreeF f a a -> a #sum :: Num a => FreeF f a a -> a #product :: Num a => FreeF f a a -> a # Traversable f => Traversable (FreeF f a) # Methodstraverse :: Applicative f => (a -> f b) -> FreeF f a a -> f (FreeF f a b) #sequenceA :: Applicative f => FreeF f a (f a) -> f (FreeF f a a) #mapM :: Monad m => (a -> m b) -> FreeF f a a -> m (FreeF f a b) #sequence :: Monad m => FreeF f a (m a) -> m (FreeF f a a) # (Eq1 f, Eq a) => Eq1 (FreeF f a) # Methods(==#) :: Eq a => FreeF f a a -> FreeF f a a -> Bool # (Ord1 f, Ord a) => Ord1 (FreeF f a) # Methodscompare1 :: Ord a => FreeF f a a -> FreeF f a a -> Ordering # (Show1 f, Show a) => Show1 (FreeF f a) # MethodsshowsPrec1 :: Show a => Int -> FreeF f a a -> ShowS #showList1 :: Show a => [FreeF f a a] -> ShowS # (Read1 f, Read a) => Read1 (FreeF f a) # MethodsreadsPrec1 :: Read a => Int -> ReadS (FreeF f a a) #readList1 :: Read a => ReadS [FreeF f a a] # (Eq (f b), Eq a) => Eq (FreeF f a b) # Methods(==) :: FreeF f a b -> FreeF f a b -> Bool #(/=) :: FreeF f a b -> FreeF f a b -> Bool # (Ord (f b), Ord a) => Ord (FreeF f a b) # Methodscompare :: FreeF f a b -> FreeF f a b -> Ordering #(<) :: FreeF f a b -> FreeF f a b -> Bool #(<=) :: FreeF f a b -> FreeF f a b -> Bool #(>) :: FreeF f a b -> FreeF f a b -> Bool #(>=) :: FreeF f a b -> FreeF f a b -> Bool #max :: FreeF f a b -> FreeF f a b -> FreeF f a b #min :: FreeF f a b -> FreeF f a b -> FreeF f a b # (Read (f b), Read a) => Read (FreeF f a b) # MethodsreadsPrec :: Int -> ReadS (FreeF f a b) #readList :: ReadS [FreeF f a b] #readPrec :: ReadPrec (FreeF f a b) #readListPrec :: ReadPrec [FreeF f a b] # (Show (f b), Show a) => Show (FreeF f a b) # MethodsshowsPrec :: Int -> FreeF f a b -> ShowS #show :: FreeF f a b -> String #showList :: [FreeF f a b] -> ShowS # The free monad transformer newtype FreeT f m a # The "free monad transformer" for a functor f Constructors  FreeT FieldsrunFreeT :: m (FreeF f a (FreeT f m a)) Instances  (Functor f, MonadError e m) => MonadError e (FreeT f m) # MethodsthrowError :: e -> FreeT f m a #catchError :: FreeT f m a -> (e -> FreeT f m a) -> FreeT f m a # (Functor f, MonadReader r m) => MonadReader r (FreeT f m) # Methodsask :: FreeT f m r #local :: (r -> r) -> FreeT f m a -> FreeT f m a #reader :: (r -> a) -> FreeT f m a # (Functor f, MonadState s m) => MonadState s (FreeT f m) # Methodsget :: FreeT f m s #put :: s -> FreeT f m () #state :: (s -> (a, s)) -> FreeT f m a # (Functor f, MonadWriter w m) => MonadWriter w (FreeT f m) # Methodswriter :: (a, w) -> FreeT f m a #tell :: w -> FreeT f m () #listen :: FreeT f m a -> FreeT f m (a, w) #pass :: FreeT f m (a, w -> w) -> FreeT f m a # (Functor f, Monad m) => MonadFree f (FreeT f m) # Methodswrap :: f (FreeT f m a) -> FreeT f m a # # Methodslift :: Monad m => m a -> FreeT f m a # (Functor f, Monad m) => Monad (FreeT f m) # Methods(>>=) :: FreeT f m a -> (a -> FreeT f m b) -> FreeT f m b #(>>) :: FreeT f m a -> FreeT f m b -> FreeT f m b #return :: a -> FreeT f m a #fail :: String -> FreeT f m a # (Functor f, Monad m) => Functor (FreeT f m) # Methodsfmap :: (a -> b) -> FreeT f m a -> FreeT f m b #(<$) :: a -> FreeT f m b -> FreeT f m a # (Functor f, Monad m) => Applicative (FreeT f m) # Methodspure :: a -> FreeT f m a #(<*>) :: FreeT f m (a -> b) -> FreeT f m a -> FreeT f m b #(*>) :: FreeT f m a -> FreeT f m b -> FreeT f m b #(<*) :: FreeT f m a -> FreeT f m b -> FreeT f m a # (Foldable m, Foldable f) => Foldable (FreeT f m) # Methodsfold :: Monoid m => FreeT f m m -> m #foldMap :: Monoid m => (a -> m) -> FreeT f m a -> m #foldr :: (a -> b -> b) -> b -> FreeT f m a -> b #foldr' :: (a -> b -> b) -> b -> FreeT f m a -> b #foldl :: (b -> a -> b) -> b -> FreeT f m a -> b #foldl' :: (b -> a -> b) -> b -> FreeT f m a -> b #foldr1 :: (a -> a -> a) -> FreeT f m a -> a #foldl1 :: (a -> a -> a) -> FreeT f m a -> a #toList :: FreeT f m a -> [a] #null :: FreeT f m a -> Bool #length :: FreeT f m a -> Int #elem :: Eq a => a -> FreeT f m a -> Bool #maximum :: Ord a => FreeT f m a -> a #minimum :: Ord a => FreeT f m a -> a #sum :: Num a => FreeT f m a -> a #product :: Num a => FreeT f m a -> a # (Monad m, Traversable m, Traversable f) => Traversable (FreeT f m) # Methodstraverse :: Applicative f => (a -> f b) -> FreeT f m a -> f (FreeT f m b) #sequenceA :: Applicative f => FreeT f m (f a) -> f (FreeT f m a) #mapM :: Monad m => (a -> m b) -> FreeT f m a -> m (FreeT f m b) #sequence :: Monad m => FreeT f m (m a) -> m (FreeT f m a) # (Functor f, MonadIO m) => MonadIO (FreeT f m) # MethodsliftIO :: IO a -> FreeT f m a # (Functor f, MonadPlus m) => Alternative (FreeT f m) # Methodsempty :: FreeT f m a #(<|>) :: FreeT f m a -> FreeT f m a -> FreeT f m a #some :: FreeT f m a -> FreeT f m [a] #many :: FreeT f m a -> FreeT f m [a] # (Functor f, MonadPlus m) => MonadPlus (FreeT f m) # Methodsmzero :: FreeT f m a #mplus :: FreeT f m a -> FreeT f m a -> FreeT f m a # (Functor f, MonadThrow m) => MonadThrow (FreeT f m) # MethodsthrowM :: Exception e => e -> FreeT f m a # (Functor f, MonadCatch m) => MonadCatch (FreeT f m) # Methodscatch :: Exception e => FreeT f m a -> (e -> FreeT f m a) -> FreeT f m a # (Functor f, MonadCont m) => MonadCont (FreeT f m) # MethodscallCC :: ((a -> FreeT f m b) -> FreeT f m a) -> FreeT f m a # (Functor f, Eq1 f, Functor m, Eq1 m) => Eq1 (FreeT f m) # Methods(==#) :: Eq a => FreeT f m a -> FreeT f m a -> Bool # (Functor f, Ord1 f, Functor m, Ord1 m) => Ord1 (FreeT f m) # Methodscompare1 :: Ord a => FreeT f m a -> FreeT f m a -> Ordering # (Functor f, Show1 f, Functor m, Show1 m) => Show1 (FreeT f m) # MethodsshowsPrec1 :: Show a => Int -> FreeT f m a -> ShowS #showList1 :: Show a => [FreeT f m a] -> ShowS # (Functor f, Read1 f, Functor m, Read1 m) => Read1 (FreeT f m) # MethodsreadsPrec1 :: Read a => Int -> ReadS (FreeT f m a) #readList1 :: Read a => ReadS [FreeT f m a] # (Functor f, Monad m) => Apply (FreeT f m) # Methods(<.>) :: FreeT f m (a -> b) -> FreeT f m a -> FreeT f m b #(.>) :: FreeT f m a -> FreeT f m b -> FreeT f m b #(<.) :: FreeT f m a -> FreeT f m b -> FreeT f m a # (Functor f, Monad m) => Bind (FreeT f m) # Methods(>>-) :: FreeT f m a -> (a -> FreeT f m b) -> FreeT f m b #join :: FreeT f m (FreeT f m a) -> FreeT f m a # Eq (m (FreeF f a (FreeT f m a))) => Eq (FreeT f m a) # Methods(==) :: FreeT f m a -> FreeT f m a -> Bool #(/=) :: FreeT f m a -> FreeT f m a -> Bool # Ord (m (FreeF f a (FreeT f m a))) => Ord (FreeT f m a) # Methodscompare :: FreeT f m a -> FreeT f m a -> Ordering #(<) :: FreeT f m a -> FreeT f m a -> Bool #(<=) :: FreeT f m a -> FreeT f m a -> Bool #(>) :: FreeT f m a -> FreeT f m a -> Bool #(>=) :: FreeT f m a -> FreeT f m a -> Bool #max :: FreeT f m a -> FreeT f m a -> FreeT f m a #min :: FreeT f m a -> FreeT f m a -> FreeT f m a # Read (m (FreeF f a (FreeT f m a))) => Read (FreeT f m a) # MethodsreadsPrec :: Int -> ReadS (FreeT f m a) #readList :: ReadS [FreeT f m a] #readPrec :: ReadPrec (FreeT f m a) #readListPrec :: ReadPrec [FreeT f m a] # Show (m (FreeF f a (FreeT f m a))) => Show (FreeT f m a) # MethodsshowsPrec :: Int -> FreeT f m a -> ShowS #show :: FreeT f m a -> String #showList :: [FreeT f m a] -> ShowS #

type Free f = FreeT f Identity #

The "free monad" for a functor f.

free :: FreeF f a (Free f a) -> Free f a #

Pushes a layer into a free monad value.

runFree :: Free f a -> FreeF f a (Free f a) #

Evaluates the first layer out of a free monad value.

Operations

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

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

iterT :: (Functor f, Monad m) => (f (m a) -> m a) -> FreeT f m a -> m a #

Tear down a free monad transformer using iteration.

iterTM :: (Functor f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) -> t m a) -> FreeT f m a -> t m a #

Tear down a free monad transformer using iteration over a transformer.

hoistFreeT :: (Monad m, Functor f) => (forall a. m a -> n a) -> FreeT f m b -> FreeT f n b #

Lift a monad homomorphism from m to n into a monad homomorphism from FreeT f m to FreeT f n

hoistFreeT :: (Monad m, Functor f) => (m ~> n) -> FreeT f m ~> FreeT f n

transFreeT :: (Monad m, Functor g) => (forall a. f a -> g a) -> FreeT f m b -> FreeT g m b #

Lift a natural transformation from f to g into a monad homomorphism from FreeT f m to FreeT g m

joinFreeT :: (Monad m, Traversable f) => FreeT f m a -> m (Free f a) #

Pull out and join m layers of FreeT f m a.

cutoff :: (Functor f, Monad m) => Integer -> FreeT f m a -> FreeT f m (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.

partialIterT :: Monad m => Integer -> (forall a. f a -> m a) -> FreeT f m b -> FreeT f m b #

partialIterT n phi m interprets first n layers of m using phi. This is sort of the opposite for cutoff.

Some examples (n ≥ 0):

partialIterT 0 _ m              ≡ m
partialIterT (n+1) phi . return ≡ return
partialIterT (n+1) phi . lift   ≡ lift
partialIterT (n+1) phi . wrap   ≡ join . lift . phi


intersperseT :: (Monad m, Functor f) => f a -> FreeT f m b -> FreeT f m b #

intersperseT f m inserts a layer f between every two layers in m.

intersperseT f . return ≡ return
intersperseT f . lift   ≡ lift
intersperseT f . wrap   ≡ wrap . fmap (iterTM (wrap . (<\$ f) . wrap))


intercalateT :: (Monad m, MonadTrans t, Monad (t m)) => t m a -> FreeT (t m) m b -> t m b #

intercalateT f m inserts a layer f between every two layers in m and then retracts the result.

intercalateT f ≡ retractT . intersperseT f


retractT :: (MonadTrans t, Monad (t m), Monad m) => FreeT (t m) m a -> t m a #

Tear down a free monad transformer using Monad instance for t m.

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

retract is the left inverse of liftF

retract . liftF = id


iter :: Functor f => (f a -> a) -> Free f a -> a #

Tear down a Free Monad using iteration.

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

Like iter for monadic values.

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.

Methods

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

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


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

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