free-4.12.4: Monads for free

Copyright(C) 2008-2013 Edward Kmett
LicenseBSD-style (see the file LICENSE)
MaintainerEdward Kmett <ekmett@gmail.com>
Stabilityprovisional
PortabilityMPTCs, fundeps
Safe HaskellSafe
LanguageHaskell2010

Control.Comonad.Cofree

Contents

Description

Cofree comonads

Synopsis

Documentation

data Cofree f a #

The Cofree Comonad of a functor f.

Formally

A Comonad v is a cofree Comonad for f if every comonad homomorphism from another comonad w to v is equivalent to a natural transformation from w to f.

A cofree functor is right adjoint to a forgetful functor.

Cofree is a functor from the category of functors to the category of comonads that is right adjoint to the forgetful functor from the category of comonads to the category of functors that forgets how to extract and duplicate, leaving you with only a Functor.

In practice, cofree comonads are quite useful for annotating syntax trees, or talking about streams.

A number of common comonads arise directly as cofree comonads.

For instance,

  • Cofree Maybe forms the a comonad for a non-empty list.
  • Cofree (Const b) is a product.
  • Cofree Identity forms an infinite stream.
  • Cofree ((->) b)' describes a Moore machine with states labeled with values of type a, and transitions on edges of type b.

Furthermore, if the functor f forms a monoid (for example, by being an instance of Alternative), the resulting Comonad is also a Monad. See Monadic Augment and Generalised Shortcut Fusion by Neil Ghani et al., Section 4.3 for more details.

In particular, if f a ≡ [a], the resulting data structure is a Rose tree. For a practical application, check Higher Dimensional Trees, Algebraically by Neil Ghani et al.

Constructors

a :< (f (Cofree f a)) infixr 5 

Instances

ComonadTrans Cofree #

This is not a true Comonad transformer, but this instance is convenient.

Methods

lower :: Comonad w => Cofree w a -> w a #

ComonadHoist Cofree # 

Methods

cohoist :: (Comonad w, Comonad v) => (forall x. w x -> v x) -> Cofree w a -> Cofree v a #

ComonadTraced m w => ComonadTraced m (Cofree w) # 

Methods

trace :: m -> Cofree w a -> a #

ComonadStore s w => ComonadStore s (Cofree w) # 

Methods

pos :: Cofree w a -> s #

peek :: s -> Cofree w a -> a #

peeks :: (s -> s) -> Cofree w a -> a #

seek :: s -> Cofree w a -> Cofree w a #

seeks :: (s -> s) -> Cofree w a -> Cofree w a #

experiment :: Functor f => (s -> f s) -> Cofree w a -> f a #

ComonadEnv e w => ComonadEnv e (Cofree w) # 

Methods

ask :: Cofree w a -> e #

Functor f => ComonadCofree f (Cofree f) # 

Methods

unwrap :: Cofree f a -> f (Cofree f a) #

Alternative f => Monad (Cofree f) # 

Methods

(>>=) :: Cofree f a -> (a -> Cofree f b) -> Cofree f b #

(>>) :: Cofree f a -> Cofree f b -> Cofree f b #

return :: a -> Cofree f a #

fail :: String -> Cofree f a #

Functor f => Functor (Cofree f) # 

Methods

fmap :: (a -> b) -> Cofree f a -> Cofree f b #

(<$) :: a -> Cofree f b -> Cofree f a #

Alternative f => Applicative (Cofree f) # 

Methods

pure :: a -> Cofree f a #

(<*>) :: Cofree f (a -> b) -> Cofree f a -> Cofree f b #

(*>) :: Cofree f a -> Cofree f b -> Cofree f b #

(<*) :: Cofree f a -> Cofree f b -> Cofree f a #

Foldable f => Foldable (Cofree f) # 

Methods

fold :: Monoid m => Cofree f m -> m #

foldMap :: Monoid m => (a -> m) -> Cofree f a -> m #

foldr :: (a -> b -> b) -> b -> Cofree f a -> b #

foldr' :: (a -> b -> b) -> b -> Cofree f a -> b #

foldl :: (b -> a -> b) -> b -> Cofree f a -> b #

foldl' :: (b -> a -> b) -> b -> Cofree f a -> b #

foldr1 :: (a -> a -> a) -> Cofree f a -> a #

foldl1 :: (a -> a -> a) -> Cofree f a -> a #

toList :: Cofree f a -> [a] #

null :: Cofree f a -> Bool #

length :: Cofree f a -> Int #

elem :: Eq a => a -> Cofree f a -> Bool #

maximum :: Ord a => Cofree f a -> a #

minimum :: Ord a => Cofree f a -> a #

sum :: Num a => Cofree f a -> a #

product :: Num a => Cofree f a -> a #

Traversable f => Traversable (Cofree f) # 

Methods

traverse :: Applicative f => (a -> f b) -> Cofree f a -> f (Cofree f b) #

sequenceA :: Applicative f => Cofree f (f a) -> f (Cofree f a) #

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

sequence :: Monad m => Cofree f (m a) -> m (Cofree f a) #

(Alternative f, MonadZip f) => MonadZip (Cofree f) # 

Methods

mzip :: Cofree f a -> Cofree f b -> Cofree f (a, b) #

mzipWith :: (a -> b -> c) -> Cofree f a -> Cofree f b -> Cofree f c #

munzip :: Cofree f (a, b) -> (Cofree f a, Cofree f b) #

Functor f => Comonad (Cofree f) # 

Methods

extract :: Cofree f a -> a #

duplicate :: Cofree f a -> Cofree f (Cofree f a) #

extend :: (Cofree f a -> b) -> Cofree f a -> Cofree f b #

ComonadApply f => ComonadApply (Cofree f) # 

Methods

(<@>) :: Cofree f (a -> b) -> Cofree f a -> Cofree f b #

(@>) :: Cofree f a -> Cofree f b -> Cofree f b #

(<@) :: Cofree f a -> Cofree f b -> Cofree f a #

Distributive f => Distributive (Cofree f) # 

Methods

distribute :: Functor f => f (Cofree f a) -> Cofree f (f a) #

collect :: Functor f => (a -> Cofree f b) -> f a -> Cofree f (f b) #

distributeM :: Monad m => m (Cofree f a) -> Cofree f (m a) #

collectM :: Monad m => (a -> Cofree f b) -> m a -> Cofree f (m b) #

(Functor f, Eq1 f) => Eq1 (Cofree f) # 

Methods

(==#) :: Eq a => Cofree f a -> Cofree f a -> Bool #

(Functor f, Ord1 f) => Ord1 (Cofree f) # 

Methods

compare1 :: Ord a => Cofree f a -> Cofree f a -> Ordering #

(Functor f, Show1 f) => Show1 (Cofree f) # 

Methods

showsPrec1 :: Show a => Int -> Cofree f a -> ShowS #

showList1 :: Show a => [Cofree f a] -> ShowS #

(Functor f, Read1 f) => Read1 (Cofree f) # 

Methods

readsPrec1 :: Read a => Int -> ReadS (Cofree f a) #

readList1 :: Read a => ReadS [Cofree f a] #

Traversable1 f => Traversable1 (Cofree f) # 

Methods

traverse1 :: Apply f => (a -> f b) -> Cofree f a -> f (Cofree f b) #

sequence1 :: Apply f => Cofree f (f b) -> f (Cofree f b) #

Apply f => Apply (Cofree f) # 

Methods

(<.>) :: Cofree f (a -> b) -> Cofree f a -> Cofree f b #

(.>) :: Cofree f a -> Cofree f b -> Cofree f b #

(<.) :: Cofree f a -> Cofree f b -> Cofree f a #

Functor f => Extend (Cofree f) # 

Methods

duplicated :: Cofree f a -> Cofree f (Cofree f a) #

extended :: (Cofree f a -> b) -> Cofree f a -> Cofree f b #

Foldable1 f => Foldable1 (Cofree f) # 

Methods

fold1 :: Semigroup m => Cofree f m -> m #

foldMap1 :: Semigroup m => (a -> m) -> Cofree f a -> m #

(Eq (f (Cofree f a)), Eq a) => Eq (Cofree f a) # 

Methods

(==) :: Cofree f a -> Cofree f a -> Bool #

(/=) :: Cofree f a -> Cofree f a -> Bool #

(Ord (f (Cofree f a)), Ord a) => Ord (Cofree f a) # 

Methods

compare :: Cofree f a -> Cofree f a -> Ordering #

(<) :: Cofree f a -> Cofree f a -> Bool #

(<=) :: Cofree f a -> Cofree f a -> Bool #

(>) :: Cofree f a -> Cofree f a -> Bool #

(>=) :: Cofree f a -> Cofree f a -> Bool #

max :: Cofree f a -> Cofree f a -> Cofree f a #

min :: Cofree f a -> Cofree f a -> Cofree f a #

(Read (f (Cofree f a)), Read a) => Read (Cofree f a) # 
(Show (f (Cofree f a)), Show a) => Show (Cofree f a) # 

Methods

showsPrec :: Int -> Cofree f a -> ShowS #

show :: Cofree f a -> String #

showList :: [Cofree f a] -> ShowS #

class (Functor f, Comonad w) => ComonadCofree f w | w -> f where #

Allows you to peel a layer off a cofree comonad.

Minimal complete definition

unwrap

Methods

unwrap :: w a -> f (w a) #

Remove a layer.

Instances

ComonadCofree [] Tree # 

Methods

unwrap :: Tree a -> [Tree a] #

ComonadCofree Maybe NonEmpty # 

Methods

unwrap :: NonEmpty a -> Maybe (NonEmpty a) #

Functor f => ComonadCofree f (Cofree f) # 

Methods

unwrap :: Cofree f a -> f (Cofree f a) #

Comonad w => ComonadCofree Identity (CoiterT w) # 

Methods

unwrap :: CoiterT w a -> Identity (CoiterT w a) #

(ComonadCofree f w, Monoid m) => ComonadCofree f (TracedT m w) # 

Methods

unwrap :: TracedT m w a -> f (TracedT m w a) #

ComonadCofree f w => ComonadCofree f (StoreT s w) # 

Methods

unwrap :: StoreT s w a -> f (StoreT s w a) #

ComonadCofree f w => ComonadCofree f (EnvT e w) # 

Methods

unwrap :: EnvT e w a -> f (EnvT e w a) #

ComonadCofree f w => ComonadCofree f (IdentityT * w) # 

Methods

unwrap :: IdentityT * w a -> f (IdentityT * w a) #

(Functor f, Comonad w) => ComonadCofree f (CofreeT f w) # 

Methods

unwrap :: CofreeT f w a -> f (CofreeT f w a) #

ComonadCofree (Const * b) ((,) b) # 

Methods

unwrap :: (b, a) -> Const * b (b, a) #

section :: Comonad f => f a -> Cofree f a #

coiter :: Functor f => (a -> f a) -> a -> Cofree f a #

Use coiteration to generate a cofree comonad from a seed.

coiter f = unfold (id &&& f)

coiterW :: (Comonad w, Functor f) => (w a -> f (w a)) -> w a -> Cofree f a #

Like coiter for comonadic values.

unfold :: Functor f => (b -> (a, f b)) -> b -> Cofree f a #

Unfold a cofree comonad from a seed.

unfoldM :: (Traversable f, Monad m) => (b -> m (a, f b)) -> b -> m (Cofree f a) #

Unfold a cofree comonad from a seed, monadically.

hoistCofree :: Functor f => (forall x. f x -> g x) -> Cofree f a -> Cofree g a #

Lenses into cofree comonads

_extract :: Functor f => (a -> f a) -> Cofree g a -> f (Cofree g a) #

This is a lens that can be used to read or write from the target of extract.

Using (^.) from the lens package:

foo ^. _extract == extract foo

For more on lenses see the lens package on hackage

_extract :: Lens' (Cofree g a) a

_unwrap :: Functor f => (g (Cofree g a) -> f (g (Cofree g a))) -> Cofree g a -> f (Cofree g a) #

This is a lens that can be used to read or write to the tails of a Cofree Comonad.

Using (^.) from the lens package:

foo ^. _unwrap == unwrap foo

For more on lenses see the lens package on hackage

_unwrap :: Lens' (Cofree g a) (g (Cofree g a))

telescoped :: Functor f => [(Cofree g a -> f (Cofree g a)) -> g (Cofree g a) -> f (g (Cofree g a))] -> (a -> f a) -> Cofree g a -> f (Cofree g a) #

Construct an Lens into a Cofree g given a list of lenses into the base functor. When the input list is empty, this is equivalent to _extract. When the input list is non-empty, this composes the input lenses with _unwrap to walk through the Cofree g before using _extract to get the element at the final location.

For more on lenses see the lens package on hackage.

telescoped :: [Lens' (g (Cofree g a)) (Cofree g a)]      -> Lens' (Cofree g a) a
telescoped :: [Traversal' (g (Cofree g a)) (Cofree g a)] -> Traversal' (Cofree g a) a
telescoped :: [Getter (g (Cofree g a)) (Cofree g a)]     -> Getter (Cofree g a) a
telescoped :: [Fold (g (Cofree g a)) (Cofree g a)]       -> Fold (Cofree g a) a
telescoped :: [Setter' (g (Cofree g a)) (Cofree g a)]    -> Setter' (Cofree g a) a