Copyright | (C) 2008-2013 Edward Kmett |
---|---|

License | BSD-style (see the file LICENSE) |

Maintainer | Edward Kmett <ekmett@gmail.com> |

Stability | provisional |

Portability | MPTCs, fundeps |

Safe Haskell | Safe |

Language | Haskell2010 |

Cofree comonads

## Synopsis

- data Cofree f a = a :< (f (Cofree f a))
- class (Functor f, Comonad w) => ComonadCofree f w | w -> f where
- unwrap :: w a -> f (w a)

- section :: Comonad f => f a -> Cofree f a
- coiter :: Functor f => (a -> f a) -> a -> Cofree f a
- coiterW :: (Comonad w, Functor f) => (w a -> f (w a)) -> w a -> Cofree f a
- unfold :: Functor f => (b -> (a, f b)) -> b -> Cofree f a
- unfoldM :: (Traversable f, Monad m) => (b -> m (a, f b)) -> b -> m (Cofree f a)
- hoistCofree :: Functor f => (forall x. f x -> g x) -> Cofree f a -> Cofree g a
- _extract :: Functor f => (a -> f a) -> Cofree g a -> f (Cofree g a)
- _unwrap :: Functor f => (g (Cofree g a) -> f (g (Cofree g a))) -> Cofree g a -> f (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)
- telescoped_ :: Functor f => [(Cofree g a -> f (Cofree g a)) -> g (Cofree g a) -> f (g (Cofree g a))] -> (Cofree g a -> f (Cofree g a)) -> Cofree g a -> f (Cofree g a)
- shoots :: (Applicative f, Traversable g) => (a -> f a) -> Cofree g a -> f (Cofree g a)
- leaves :: (Applicative f, Traversable g) => (a -> f a) -> Cofree g a -> f (Cofree g a)

# Documentation

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,

forms the a comonad for a non-empty list.`Cofree`

`Maybe`

is a product.`Cofree`

(`Const`

b)

forms an infinite stream.`Cofree`

`Identity`

describes a Moore machine with states labeled with values of type a, and transitions on edges of type b.`Cofree`

((->) 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.

## Instances

ComonadHoist Cofree Source # | |

Defined in Control.Comonad.Cofree | |

ComonadTrans Cofree Source # | This is not a true |

Defined in Control.Comonad.Cofree | |

Functor f => ComonadCofree f (Cofree f) Source # | |

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

Defined in Control.Comonad.Cofree | |

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

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

Defined in Control.Comonad.Cofree | |

Alternative f => Monad (Cofree f) Source # | |

Functor f => Functor (Cofree f) Source # | |

Alternative f => Applicative (Cofree f) Source # | |

Defined in Control.Comonad.Cofree | |

Foldable f => Foldable (Cofree f) Source # | |

Defined in Control.Comonad.Cofree fold :: Monoid m => Cofree f m -> m Source # foldMap :: Monoid m => (a -> m) -> Cofree f a -> m Source # foldr :: (a -> b -> b) -> b -> Cofree f a -> b Source # foldr' :: (a -> b -> b) -> b -> Cofree f a -> b Source # foldl :: (b -> a -> b) -> b -> Cofree f a -> b Source # foldl' :: (b -> a -> b) -> b -> Cofree f a -> b Source # foldr1 :: (a -> a -> a) -> Cofree f a -> a Source # foldl1 :: (a -> a -> a) -> Cofree f a -> a Source # toList :: Cofree f a -> [a] Source # null :: Cofree f a -> Bool Source # length :: Cofree f a -> Int Source # elem :: Eq a => a -> Cofree f a -> Bool Source # maximum :: Ord a => Cofree f a -> a Source # minimum :: Ord a => Cofree f a -> a Source # | |

Traversable f => Traversable (Cofree f) Source # | |

Defined in Control.Comonad.Cofree | |

Eq1 f => Eq1 (Cofree f) Source # | |

Ord1 f => Ord1 (Cofree f) Source # | |

Defined in Control.Comonad.Cofree | |

Read1 f => Read1 (Cofree f) Source # | |

Defined in Control.Comonad.Cofree liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Cofree f a) Source # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Cofree f a] Source # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Cofree f a) Source # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Cofree f a] Source # | |

Show1 f => Show1 (Cofree f) Source # | |

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

Distributive f => Distributive (Cofree f) Source # | |

Defined in Control.Comonad.Cofree | |

Apply f => Apply (Cofree f) Source # | |

Functor f => Comonad (Cofree f) Source # | |

Functor f => Extend (Cofree f) Source # | |

Defined in Control.Comonad.Cofree | |

ComonadApply f => ComonadApply (Cofree f) Source # | |

Foldable1 f => Foldable1 (Cofree f) Source # | |

Defined in Control.Comonad.Cofree | |

Traversable1 f => Traversable1 (Cofree f) Source # | |

Functor f => Generic1 (Cofree f :: Type -> Type) Source # | |

(Eq1 f, Eq a) => Eq (Cofree f a) Source # | |

(Typeable f, Data (f (Cofree f a)), Data a) => Data (Cofree f a) Source # | |

Defined in Control.Comonad.Cofree gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Cofree f a -> c (Cofree f a) Source # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Cofree f a) Source # toConstr :: Cofree f a -> Constr Source # dataTypeOf :: Cofree f a -> DataType Source # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Cofree f a)) Source # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Cofree f a)) Source # gmapT :: (forall b. Data b => b -> b) -> Cofree f a -> Cofree f a Source # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Cofree f a -> r Source # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Cofree f a -> r Source # gmapQ :: (forall d. Data d => d -> u) -> Cofree f a -> [u] Source # gmapQi :: Int -> (forall d. Data d => d -> u) -> Cofree f a -> u Source # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Cofree f a -> m (Cofree f a) Source # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Cofree f a -> m (Cofree f a) Source # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Cofree f a -> m (Cofree f a) Source # | |

(Ord1 f, Ord a) => Ord (Cofree f a) Source # | |

Defined in Control.Comonad.Cofree compare :: Cofree f a -> Cofree f a -> Ordering Source # (<) :: Cofree f a -> Cofree f a -> Bool Source # (<=) :: Cofree f a -> Cofree f a -> Bool Source # (>) :: Cofree f a -> Cofree f a -> Bool Source # (>=) :: Cofree f a -> Cofree f a -> Bool Source # | |

(Read1 f, Read a) => Read (Cofree f a) Source # | |

(Show1 f, Show a) => Show (Cofree f a) Source # | |

Generic (Cofree f a) Source # | |

type Rep1 (Cofree f :: Type -> Type) Source # | |

Defined in Control.Comonad.Cofree type Rep1 (Cofree f :: Type -> Type) = D1 (MetaData "Cofree" "Control.Comonad.Cofree" "free-5.1.3-30JDELRs8XK52CahEWQfo4" False) (C1 (MetaCons ":<" (InfixI RightAssociative 5) False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1 :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (f :.: Rec1 (Cofree f)))) | |

type Rep (Cofree f a) Source # | |

Defined in Control.Comonad.Cofree type Rep (Cofree f a) = D1 (MetaData "Cofree" "Control.Comonad.Cofree" "free-5.1.3-30JDELRs8XK52CahEWQfo4" False) (C1 (MetaCons ":<" (InfixI RightAssociative 5) False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (f (Cofree f a))))) |

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

Allows you to peel a layer off a cofree comonad.

## Instances

ComonadCofree [] Tree Source # | |

ComonadCofree Maybe NonEmpty Source # | |

Functor f => ComonadCofree f (Cofree f) Source # | |

Comonad w => ComonadCofree Identity (CoiterT w) Source # | |

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

Defined in Control.Comonad.Cofree.Class | |

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

Defined in Control.Comonad.Cofree.Class | |

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

Defined in Control.Comonad.Cofree.Class | |

ComonadCofree f w => ComonadCofree f (IdentityT w) Source # | |

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

ComonadCofree (Const b :: Type -> Type) ((,) b) Source # | |

Defined in Control.Comonad.Cofree.Class |

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

Like coiter for comonadic values.

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

Unfold a cofree comonad from a seed.

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

Unfold a cofree comonad from a seed, monadically.

# Lenses into cofree comonads

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

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) Source #

Construct an `Lens`

into a

given a list of lenses into the base functor.
When the input list is empty, this is equivalent to `Cofree`

g`_extract`

.
When the input list is non-empty, this composes the input lenses
with `_unwrap`

to walk through the

before using
`Cofree`

g`_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

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

Construct an `Lens`

into a

given a list of lenses into the base functor.
The only difference between this and `Cofree`

g`telescoped`

is that `telescoped`

focuses on a single value, but this focuses on the entire remaining subtree.
When the input list is empty, this is equivalent to `id`

.
When the input list is non-empty, this composes the input lenses
with `_unwrap`

to walk through the

.`Cofree`

g

For more on lenses see the `lens`

package on hackage.

telescoped :: [Lens' (g (`Cofree`

g a)) (`Cofree`

g a)] -> Lens' (`Cofree`

g a) (`Cofree`

g a)

telescoped :: [Traversal' (g (`Cofree`

g a)) (`Cofree`

g a)] -> Traversal' (`Cofree`

g a) (`Cofree`

g a)

telescoped :: [Getter (g (`Cofree`

g a)) (`Cofree`

g a)] -> Getter (`Cofree`

g a) (`Cofree`

g a)

telescoped :: [Fold (g (`Cofree`

g a)) (`Cofree`

g a)] -> Fold (`Cofree`

g a) (`Cofree`

g a)

telescoped :: [Setter' (g (`Cofree`

g a)) (`Cofree`

g a)] -> Setter' (`Cofree`

g a) (`Cofree`

g a)

shoots :: (Applicative f, Traversable g) => (a -> f a) -> Cofree g a -> f (Cofree g a) Source #

A `Traversal'`

that gives access to all non-leaf `a`

elements of a

a, where non-leaf is defined as `Cofree`

g`x`

from `(x :< xs)`

where
`null xs`

is `False`

.

Because this doesn't give access to all values in the

,
it cannot be used to change types.`Cofree`

g

shoots :: Traversable g => Traversal' (Cofree g a) a

N.B. On GHC < 7.9, this is slightly less flexible, as it has to
use `null (toList xs)`

instead.

leaves :: (Applicative f, Traversable g) => (a -> f a) -> Cofree g a -> f (Cofree g a) Source #

A `Traversal'`

that gives access to all leaf `a`

elements of a

a, where leaf is defined as `Cofree`

g`x`

from `(x :< xs)`

where
`null xs`

is `True`

.

Because this doesn't give access to all values in the

,
it cannot be used to change types.`Cofree`

g

shoots :: Traversable g => Traversal' (Cofree g a) a

N.B. On GHC < 7.9, this is slightly less flexible, as it has to
use `null (toList xs)`

instead.