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

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

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

Stability | experimental |

Portability | non-portable |

Safe Haskell | Safe |

Language | Haskell98 |

## Synopsis

- type family Base t :: * -> *
- data ListF a b
- newtype Fix f = Fix (f (Fix f))
- unfix :: Fix f -> f (Fix f)
- newtype Mu f = Mu (forall a. (f a -> a) -> a)
- data Nu f where
- class Functor (Base t) => Recursive t where
- gapo :: Corecursive t => (b -> Base t b) -> (a -> Base t (Either b a)) -> a -> t
- gcata :: (Recursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (w a) -> a) -> t -> a
- zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a
- gzygo :: (Recursive t, Comonad w) => (Base t b -> b) -> (forall c. Base t (w c) -> w (Base t c)) -> (Base t (EnvT b w a) -> a) -> t -> a
- histo :: Recursive t => (Base t (Cofree (Base t) a) -> a) -> t -> a
- ghisto :: (Recursive t, Functor h) => (forall b. Base t (h b) -> h (Base t b)) -> (Base t (Cofree h a) -> a) -> t -> a
- futu :: Corecursive t => (a -> Base t (Free (Base t) a)) -> a -> t
- chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> b
- gchrono :: (Functor f, Functor w, Functor m) => (forall c. f (w c) -> w (f c)) -> (forall c. m (f c) -> f (m c)) -> (f (Cofree w b) -> b) -> (a -> f (Free m a)) -> a -> b
- distCata :: Functor f => f (Identity a) -> Identity (f a)
- distPara :: Corecursive t => Base t (t, a) -> (t, Base t a)
- distParaT :: (Corecursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> Base t (EnvT t w a) -> EnvT t w (Base t a)
- distZygo :: Functor f => (f b -> b) -> f (b, a) -> (b, f a)
- distZygoT :: (Functor f, Comonad w) => (f b -> b) -> (forall c. f (w c) -> w (f c)) -> f (EnvT b w a) -> EnvT b w (f a)
- distHisto :: Functor f => f (Cofree f a) -> Cofree f (f a)
- distGHisto :: (Functor f, Functor h) => (forall b. f (h b) -> h (f b)) -> f (Cofree h a) -> Cofree h (f a)
- distFutu :: Functor f => Free f (f a) -> f (Free f a)
- distGFutu :: (Functor f, Functor h) => (forall b. h (f b) -> f (h b)) -> Free h (f a) -> f (Free h a)
- class Functor (Base t) => Corecursive t where
- gana :: (Corecursive t, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (a -> Base t (m a)) -> a -> t
- distAna :: Functor f => Identity (f a) -> f (Identity a)
- distApo :: Recursive t => Either t (Base t a) -> Base t (Either t a)
- distGApo :: Functor f => (b -> f b) -> Either b (f a) -> f (Either b a)
- distGApoT :: (Functor f, Functor m) => (b -> f b) -> (forall c. m (f c) -> f (m c)) -> ExceptT b m (f a) -> f (ExceptT b m a)
- hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
- ghylo :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b
- refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s -> t
- fold :: Recursive t => (Base t a -> a) -> t -> a
- gfold :: (Recursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (w a) -> a) -> t -> a
- unfold :: Corecursive t => (a -> Base t a) -> a -> t
- gunfold :: (Corecursive t, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (a -> Base t (m a)) -> a -> t
- refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
- grefold :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b
- mcata :: (forall y. (y -> c) -> f y -> c) -> Fix f -> c
- mhisto :: (forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c
- elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a
- coelgot :: Functor f => ((a, f b) -> b) -> (a -> f a) -> a -> b
- zygoHistoPrepro :: (Corecursive t, Recursive t) => (Base t b -> b) -> (forall c. Base t c -> Base t c) -> (Base t (EnvT b (Cofree (Base t)) a) -> a) -> t -> a

# Base functors for fixed points

type family Base t :: * -> * Source #

## Instances

type Base Natural Source # | |

Defined in Data.Functor.Foldable | |

type Base [a] Source # | |

Defined in Data.Functor.Foldable | |

type Base (Maybe a) Source # | |

type Base (NonEmpty a) Source # | |

Defined in Data.Functor.Foldable | |

type Base (Nu f) Source # | |

Defined in Data.Functor.Foldable | |

type Base (Mu f) Source # | |

Defined in Data.Functor.Foldable | |

type Base (Fix f) Source # | |

Defined in Data.Functor.Foldable | |

type Base (Either a b) Source # | |

type Base (Cofree f a) Source # | |

Defined in Data.Functor.Foldable | |

type Base (F f a) Source # | |

Defined in Data.Functor.Foldable | |

type Base (Free f a) Source # | |

Defined in Data.Functor.Foldable | |

type Base (FreeT f m a) Source # | |

Defined in Data.Functor.Foldable | |

type Base (CofreeT f w a) Source # | |

Defined in Data.Functor.Foldable |

Base functor of `[]`

.

## Instances

# Fixed points

## Instances

Eq1 f => Eq (Fix f) Source # | |

(Typeable f, Data (f (Fix f))) => Data (Fix f) Source # | |

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

Ord1 f => Ord (Fix f) Source # | |

Read1 f => Read (Fix f) Source # | |

Show1 f => Show (Fix f) Source # | |

Functor f => Corecursive (Fix f) Source # | |

Defined in Data.Functor.Foldable embed :: Base (Fix f) (Fix f) -> Fix f Source # ana :: (a -> Base (Fix f) a) -> a -> Fix f Source # apo :: (a -> Base (Fix f) (Either (Fix f) a)) -> a -> Fix f Source # postpro :: Recursive (Fix f) => (forall b. Base (Fix f) b -> Base (Fix f) b) -> (a -> Base (Fix f) a) -> a -> Fix f Source # gpostpro :: (Recursive (Fix f), Monad m) => (forall b. m (Base (Fix f) b) -> Base (Fix f) (m b)) -> (forall c. Base (Fix f) c -> Base (Fix f) c) -> (a -> Base (Fix f) (m a)) -> a -> Fix f Source # | |

Functor f => Recursive (Fix f) Source # | |

Defined in Data.Functor.Foldable project :: Fix f -> Base (Fix f) (Fix f) Source # cata :: (Base (Fix f) a -> a) -> Fix f -> a Source # para :: (Base (Fix f) (Fix f, a) -> a) -> Fix f -> a Source # gpara :: (Corecursive (Fix f), Comonad w) => (forall b. Base (Fix f) (w b) -> w (Base (Fix f) b)) -> (Base (Fix f) (EnvT (Fix f) w a) -> a) -> Fix f -> a Source # prepro :: Corecursive (Fix f) => (forall b. Base (Fix f) b -> Base (Fix f) b) -> (Base (Fix f) a -> a) -> Fix f -> a Source # gprepro :: (Corecursive (Fix f), Comonad w) => (forall b. Base (Fix f) (w b) -> w (Base (Fix f) b)) -> (forall c. Base (Fix f) c -> Base (Fix f) c) -> (Base (Fix f) (w a) -> a) -> Fix f -> a Source # | |

type Base (Fix f) Source # | |

Defined in Data.Functor.Foldable |

Mu (forall a. (f a -> a) -> a) |

## Instances

(Functor f, Eq1 f) => Eq (Mu f) Source # | |

(Functor f, Ord1 f) => Ord (Mu f) Source # | |

(Functor f, Read1 f) => Read (Mu f) Source # | |

(Functor f, Show1 f) => Show (Mu f) Source # | |

Functor f => Corecursive (Mu f) Source # | |

Defined in Data.Functor.Foldable embed :: Base (Mu f) (Mu f) -> Mu f Source # ana :: (a -> Base (Mu f) a) -> a -> Mu f Source # apo :: (a -> Base (Mu f) (Either (Mu f) a)) -> a -> Mu f Source # postpro :: Recursive (Mu f) => (forall b. Base (Mu f) b -> Base (Mu f) b) -> (a -> Base (Mu f) a) -> a -> Mu f Source # gpostpro :: (Recursive (Mu f), Monad m) => (forall b. m (Base (Mu f) b) -> Base (Mu f) (m b)) -> (forall c. Base (Mu f) c -> Base (Mu f) c) -> (a -> Base (Mu f) (m a)) -> a -> Mu f Source # | |

Functor f => Recursive (Mu f) Source # | |

Defined in Data.Functor.Foldable project :: Mu f -> Base (Mu f) (Mu f) Source # cata :: (Base (Mu f) a -> a) -> Mu f -> a Source # para :: (Base (Mu f) (Mu f, a) -> a) -> Mu f -> a Source # gpara :: (Corecursive (Mu f), Comonad w) => (forall b. Base (Mu f) (w b) -> w (Base (Mu f) b)) -> (Base (Mu f) (EnvT (Mu f) w a) -> a) -> Mu f -> a Source # prepro :: Corecursive (Mu f) => (forall b. Base (Mu f) b -> Base (Mu f) b) -> (Base (Mu f) a -> a) -> Mu f -> a Source # gprepro :: (Corecursive (Mu f), Comonad w) => (forall b. Base (Mu f) (w b) -> w (Base (Mu f) b)) -> (forall c. Base (Mu f) c -> Base (Mu f) c) -> (Base (Mu f) (w a) -> a) -> Mu f -> a Source # | |

type Base (Mu f) Source # | |

Defined in Data.Functor.Foldable |

## Instances

(Functor f, Eq1 f) => Eq (Nu f) Source # | |

(Functor f, Ord1 f) => Ord (Nu f) Source # | |

(Functor f, Read1 f) => Read (Nu f) Source # | |

(Functor f, Show1 f) => Show (Nu f) Source # | |

Functor f => Corecursive (Nu f) Source # | |

Defined in Data.Functor.Foldable embed :: Base (Nu f) (Nu f) -> Nu f Source # ana :: (a -> Base (Nu f) a) -> a -> Nu f Source # apo :: (a -> Base (Nu f) (Either (Nu f) a)) -> a -> Nu f Source # postpro :: Recursive (Nu f) => (forall b. Base (Nu f) b -> Base (Nu f) b) -> (a -> Base (Nu f) a) -> a -> Nu f Source # gpostpro :: (Recursive (Nu f), Monad m) => (forall b. m (Base (Nu f) b) -> Base (Nu f) (m b)) -> (forall c. Base (Nu f) c -> Base (Nu f) c) -> (a -> Base (Nu f) (m a)) -> a -> Nu f Source # | |

Functor f => Recursive (Nu f) Source # | |

Defined in Data.Functor.Foldable project :: Nu f -> Base (Nu f) (Nu f) Source # cata :: (Base (Nu f) a -> a) -> Nu f -> a Source # para :: (Base (Nu f) (Nu f, a) -> a) -> Nu f -> a Source # gpara :: (Corecursive (Nu f), Comonad w) => (forall b. Base (Nu f) (w b) -> w (Base (Nu f) b)) -> (Base (Nu f) (EnvT (Nu f) w a) -> a) -> Nu f -> a Source # prepro :: Corecursive (Nu f) => (forall b. Base (Nu f) b -> Base (Nu f) b) -> (Base (Nu f) a -> a) -> Nu f -> a Source # gprepro :: (Corecursive (Nu f), Comonad w) => (forall b. Base (Nu f) (w b) -> w (Base (Nu f) b)) -> (forall c. Base (Nu f) c -> Base (Nu f) c) -> (Base (Nu f) (w a) -> a) -> Nu f -> a Source # | |

type Base (Nu f) Source # | |

Defined in Data.Functor.Foldable |

# Folding

class Functor (Base t) => Recursive t where Source #

project :: t -> Base t t Source #

:: (Base t a -> a) | a (Base t)-algebra |

-> t | fixed point |

-> a | result |

para :: (Base t (t, a) -> a) -> t -> a Source #

gpara :: (Corecursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (EnvT t w a) -> a) -> t -> a Source #

prepro :: Corecursive t => (forall b. Base t b -> Base t b) -> (Base t a -> a) -> t -> a Source #

Fokkinga's prepromorphism

gprepro :: (Corecursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (forall c. Base t c -> Base t c) -> (Base t (w a) -> a) -> t -> a Source #

## Instances

Recursive Natural Source # | |

Defined in Data.Functor.Foldable project :: Natural -> Base Natural Natural Source # cata :: (Base Natural a -> a) -> Natural -> a Source # para :: (Base Natural (Natural, a) -> a) -> Natural -> a Source # gpara :: (Corecursive Natural, Comonad w) => (forall b. Base Natural (w b) -> w (Base Natural b)) -> (Base Natural (EnvT Natural w a) -> a) -> Natural -> a Source # prepro :: Corecursive Natural => (forall b. Base Natural b -> Base Natural b) -> (Base Natural a -> a) -> Natural -> a Source # gprepro :: (Corecursive Natural, Comonad w) => (forall b. Base Natural (w b) -> w (Base Natural b)) -> (forall c. Base Natural c -> Base Natural c) -> (Base Natural (w a) -> a) -> Natural -> a Source # | |

Recursive [a] Source # | |

Defined in Data.Functor.Foldable project :: [a] -> Base [a] [a] Source # cata :: (Base [a] a0 -> a0) -> [a] -> a0 Source # para :: (Base [a] ([a], a0) -> a0) -> [a] -> a0 Source # gpara :: (Corecursive [a], Comonad w) => (forall b. Base [a] (w b) -> w (Base [a] b)) -> (Base [a] (EnvT [a] w a0) -> a0) -> [a] -> a0 Source # prepro :: Corecursive [a] => (forall b. Base [a] b -> Base [a] b) -> (Base [a] a0 -> a0) -> [a] -> a0 Source # gprepro :: (Corecursive [a], Comonad w) => (forall b. Base [a] (w b) -> w (Base [a] b)) -> (forall c. Base [a] c -> Base [a] c) -> (Base [a] (w a0) -> a0) -> [a] -> a0 Source # | |

Recursive (Maybe a) Source # | |

Defined in Data.Functor.Foldable project :: Maybe a -> Base (Maybe a) (Maybe a) Source # cata :: (Base (Maybe a) a0 -> a0) -> Maybe a -> a0 Source # para :: (Base (Maybe a) (Maybe a, a0) -> a0) -> Maybe a -> a0 Source # gpara :: (Corecursive (Maybe a), Comonad w) => (forall b. Base (Maybe a) (w b) -> w (Base (Maybe a) b)) -> (Base (Maybe a) (EnvT (Maybe a) w a0) -> a0) -> Maybe a -> a0 Source # prepro :: Corecursive (Maybe a) => (forall b. Base (Maybe a) b -> Base (Maybe a) b) -> (Base (Maybe a) a0 -> a0) -> Maybe a -> a0 Source # gprepro :: (Corecursive (Maybe a), Comonad w) => (forall b. Base (Maybe a) (w b) -> w (Base (Maybe a) b)) -> (forall c. Base (Maybe a) c -> Base (Maybe a) c) -> (Base (Maybe a) (w a0) -> a0) -> Maybe a -> a0 Source # | |

Recursive (NonEmpty a) Source # | |

Defined in Data.Functor.Foldable project :: NonEmpty a -> Base (NonEmpty a) (NonEmpty a) Source # cata :: (Base (NonEmpty a) a0 -> a0) -> NonEmpty a -> a0 Source # para :: (Base (NonEmpty a) (NonEmpty a, a0) -> a0) -> NonEmpty a -> a0 Source # gpara :: (Corecursive (NonEmpty a), Comonad w) => (forall b. Base (NonEmpty a) (w b) -> w (Base (NonEmpty a) b)) -> (Base (NonEmpty a) (EnvT (NonEmpty a) w a0) -> a0) -> NonEmpty a -> a0 Source # prepro :: Corecursive (NonEmpty a) => (forall b. Base (NonEmpty a) b -> Base (NonEmpty a) b) -> (Base (NonEmpty a) a0 -> a0) -> NonEmpty a -> a0 Source # gprepro :: (Corecursive (NonEmpty a), Comonad w) => (forall b. Base (NonEmpty a) (w b) -> w (Base (NonEmpty a) b)) -> (forall c. Base (NonEmpty a) c -> Base (NonEmpty a) c) -> (Base (NonEmpty a) (w a0) -> a0) -> NonEmpty a -> a0 Source # | |

Functor f => Recursive (Nu f) Source # | |

Defined in Data.Functor.Foldable project :: Nu f -> Base (Nu f) (Nu f) Source # cata :: (Base (Nu f) a -> a) -> Nu f -> a Source # para :: (Base (Nu f) (Nu f, a) -> a) -> Nu f -> a Source # gpara :: (Corecursive (Nu f), Comonad w) => (forall b. Base (Nu f) (w b) -> w (Base (Nu f) b)) -> (Base (Nu f) (EnvT (Nu f) w a) -> a) -> Nu f -> a Source # prepro :: Corecursive (Nu f) => (forall b. Base (Nu f) b -> Base (Nu f) b) -> (Base (Nu f) a -> a) -> Nu f -> a Source # gprepro :: (Corecursive (Nu f), Comonad w) => (forall b. Base (Nu f) (w b) -> w (Base (Nu f) b)) -> (forall c. Base (Nu f) c -> Base (Nu f) c) -> (Base (Nu f) (w a) -> a) -> Nu f -> a Source # | |

Functor f => Recursive (Mu f) Source # | |

Defined in Data.Functor.Foldable project :: Mu f -> Base (Mu f) (Mu f) Source # cata :: (Base (Mu f) a -> a) -> Mu f -> a Source # para :: (Base (Mu f) (Mu f, a) -> a) -> Mu f -> a Source # gpara :: (Corecursive (Mu f), Comonad w) => (forall b. Base (Mu f) (w b) -> w (Base (Mu f) b)) -> (Base (Mu f) (EnvT (Mu f) w a) -> a) -> Mu f -> a Source # prepro :: Corecursive (Mu f) => (forall b. Base (Mu f) b -> Base (Mu f) b) -> (Base (Mu f) a -> a) -> Mu f -> a Source # gprepro :: (Corecursive (Mu f), Comonad w) => (forall b. Base (Mu f) (w b) -> w (Base (Mu f) b)) -> (forall c. Base (Mu f) c -> Base (Mu f) c) -> (Base (Mu f) (w a) -> a) -> Mu f -> a Source # | |

Functor f => Recursive (Fix f) Source # | |

Defined in Data.Functor.Foldable project :: Fix f -> Base (Fix f) (Fix f) Source # cata :: (Base (Fix f) a -> a) -> Fix f -> a Source # para :: (Base (Fix f) (Fix f, a) -> a) -> Fix f -> a Source # gpara :: (Corecursive (Fix f), Comonad w) => (forall b. Base (Fix f) (w b) -> w (Base (Fix f) b)) -> (Base (Fix f) (EnvT (Fix f) w a) -> a) -> Fix f -> a Source # prepro :: Corecursive (Fix f) => (forall b. Base (Fix f) b -> Base (Fix f) b) -> (Base (Fix f) a -> a) -> Fix f -> a Source # gprepro :: (Corecursive (Fix f), Comonad w) => (forall b. Base (Fix f) (w b) -> w (Base (Fix f) b)) -> (forall c. Base (Fix f) c -> Base (Fix f) c) -> (Base (Fix f) (w a) -> a) -> Fix f -> a Source # | |

Recursive (Either a b) Source # | |

Defined in Data.Functor.Foldable project :: Either a b -> Base (Either a b) (Either a b) Source # cata :: (Base (Either a b) a0 -> a0) -> Either a b -> a0 Source # para :: (Base (Either a b) (Either a b, a0) -> a0) -> Either a b -> a0 Source # gpara :: (Corecursive (Either a b), Comonad w) => (forall b0. Base (Either a b) (w b0) -> w (Base (Either a b) b0)) -> (Base (Either a b) (EnvT (Either a b) w a0) -> a0) -> Either a b -> a0 Source # prepro :: Corecursive (Either a b) => (forall b0. Base (Either a b) b0 -> Base (Either a b) b0) -> (Base (Either a b) a0 -> a0) -> Either a b -> a0 Source # gprepro :: (Corecursive (Either a b), Comonad w) => (forall b0. Base (Either a b) (w b0) -> w (Base (Either a b) b0)) -> (forall c. Base (Either a b) c -> Base (Either a b) c) -> (Base (Either a b) (w a0) -> a0) -> Either a b -> a0 Source # | |

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

Defined in Data.Functor.Foldable project :: Cofree f a -> Base (Cofree f a) (Cofree f a) Source # cata :: (Base (Cofree f a) a0 -> a0) -> Cofree f a -> a0 Source # para :: (Base (Cofree f a) (Cofree f a, a0) -> a0) -> Cofree f a -> a0 Source # gpara :: (Corecursive (Cofree f a), Comonad w) => (forall b. Base (Cofree f a) (w b) -> w (Base (Cofree f a) b)) -> (Base (Cofree f a) (EnvT (Cofree f a) w a0) -> a0) -> Cofree f a -> a0 Source # prepro :: Corecursive (Cofree f a) => (forall b. Base (Cofree f a) b -> Base (Cofree f a) b) -> (Base (Cofree f a) a0 -> a0) -> Cofree f a -> a0 Source # gprepro :: (Corecursive (Cofree f a), Comonad w) => (forall b. Base (Cofree f a) (w b) -> w (Base (Cofree f a) b)) -> (forall c. Base (Cofree f a) c -> Base (Cofree f a) c) -> (Base (Cofree f a) (w a0) -> a0) -> Cofree f a -> a0 Source # | |

Functor f => Recursive (F f a) Source # | |

Defined in Data.Functor.Foldable project :: F f a -> Base (F f a) (F f a) Source # cata :: (Base (F f a) a0 -> a0) -> F f a -> a0 Source # para :: (Base (F f a) (F f a, a0) -> a0) -> F f a -> a0 Source # gpara :: (Corecursive (F f a), Comonad w) => (forall b. Base (F f a) (w b) -> w (Base (F f a) b)) -> (Base (F f a) (EnvT (F f a) w a0) -> a0) -> F f a -> a0 Source # prepro :: Corecursive (F f a) => (forall b. Base (F f a) b -> Base (F f a) b) -> (Base (F f a) a0 -> a0) -> F f a -> a0 Source # gprepro :: (Corecursive (F f a), Comonad w) => (forall b. Base (F f a) (w b) -> w (Base (F f a) b)) -> (forall c. Base (F f a) c -> Base (F f a) c) -> (Base (F f a) (w a0) -> a0) -> F f a -> a0 Source # | |

Functor f => Recursive (Free f a) Source # | |

Defined in Data.Functor.Foldable project :: Free f a -> Base (Free f a) (Free f a) Source # cata :: (Base (Free f a) a0 -> a0) -> Free f a -> a0 Source # para :: (Base (Free f a) (Free f a, a0) -> a0) -> Free f a -> a0 Source # gpara :: (Corecursive (Free f a), Comonad w) => (forall b. Base (Free f a) (w b) -> w (Base (Free f a) b)) -> (Base (Free f a) (EnvT (Free f a) w a0) -> a0) -> Free f a -> a0 Source # prepro :: Corecursive (Free f a) => (forall b. Base (Free f a) b -> Base (Free f a) b) -> (Base (Free f a) a0 -> a0) -> Free f a -> a0 Source # gprepro :: (Corecursive (Free f a), Comonad w) => (forall b. Base (Free f a) (w b) -> w (Base (Free f a) b)) -> (forall c. Base (Free f a) c -> Base (Free f a) c) -> (Base (Free f a) (w a0) -> a0) -> Free f a -> a0 Source # | |

(Functor m, Functor f) => Recursive (FreeT f m a) Source # | |

Defined in Data.Functor.Foldable project :: FreeT f m a -> Base (FreeT f m a) (FreeT f m a) Source # cata :: (Base (FreeT f m a) a0 -> a0) -> FreeT f m a -> a0 Source # para :: (Base (FreeT f m a) (FreeT f m a, a0) -> a0) -> FreeT f m a -> a0 Source # gpara :: (Corecursive (FreeT f m a), Comonad w) => (forall b. Base (FreeT f m a) (w b) -> w (Base (FreeT f m a) b)) -> (Base (FreeT f m a) (EnvT (FreeT f m a) w a0) -> a0) -> FreeT f m a -> a0 Source # prepro :: Corecursive (FreeT f m a) => (forall b. Base (FreeT f m a) b -> Base (FreeT f m a) b) -> (Base (FreeT f m a) a0 -> a0) -> FreeT f m a -> a0 Source # gprepro :: (Corecursive (FreeT f m a), Comonad w) => (forall b. Base (FreeT f m a) (w b) -> w (Base (FreeT f m a) b)) -> (forall c. Base (FreeT f m a) c -> Base (FreeT f m a) c) -> (Base (FreeT f m a) (w a0) -> a0) -> FreeT f m a -> a0 Source # | |

(Functor w, Functor f) => Recursive (CofreeT f w a) Source # | |

Defined in Data.Functor.Foldable project :: CofreeT f w a -> Base (CofreeT f w a) (CofreeT f w a) Source # cata :: (Base (CofreeT f w a) a0 -> a0) -> CofreeT f w a -> a0 Source # para :: (Base (CofreeT f w a) (CofreeT f w a, a0) -> a0) -> CofreeT f w a -> a0 Source # gpara :: (Corecursive (CofreeT f w a), Comonad w0) => (forall b. Base (CofreeT f w a) (w0 b) -> w0 (Base (CofreeT f w a) b)) -> (Base (CofreeT f w a) (EnvT (CofreeT f w a) w0 a0) -> a0) -> CofreeT f w a -> a0 Source # prepro :: Corecursive (CofreeT f w a) => (forall b. Base (CofreeT f w a) b -> Base (CofreeT f w a) b) -> (Base (CofreeT f w a) a0 -> a0) -> CofreeT f w a -> a0 Source # gprepro :: (Corecursive (CofreeT f w a), Comonad w0) => (forall b. Base (CofreeT f w a) (w0 b) -> w0 (Base (CofreeT f w a) b)) -> (forall c. Base (CofreeT f w a) c -> Base (CofreeT f w a) c) -> (Base (CofreeT f w a) (w0 a0) -> a0) -> CofreeT f w a -> a0 Source # |

## Combinators

:: (Recursive t, Comonad w) | |

=> (forall b. Base t (w b) -> w (Base t b)) | a distributive law |

-> (Base t (w a) -> a) | a (Base t)-w-algebra |

-> t | fixed point |

-> a |

A generalized catamorphism

gzygo :: (Recursive t, Comonad w) => (Base t b -> b) -> (forall c. Base t (w c) -> w (Base t c)) -> (Base t (EnvT b w a) -> a) -> t -> a Source #

histo :: Recursive t => (Base t (Cofree (Base t) a) -> a) -> t -> a Source #

Course-of-value iteration

ghisto :: (Recursive t, Functor h) => (forall b. Base t (h b) -> h (Base t b)) -> (Base t (Cofree h a) -> a) -> t -> a Source #

gchrono :: (Functor f, Functor w, Functor m) => (forall c. f (w c) -> w (f c)) -> (forall c. m (f c) -> f (m c)) -> (f (Cofree w b) -> b) -> (a -> f (Free m a)) -> a -> b Source #

## Distributive laws

distParaT :: (Corecursive t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> Base t (EnvT t w a) -> EnvT t w (Base t a) Source #

:: Functor f | |

=> (f b -> b) | |

-> f (b, a) -> (b, f a) | A distributive for semi-mutual recursion |

distZygoT :: (Functor f, Comonad w) => (f b -> b) -> (forall c. f (w c) -> w (f c)) -> f (EnvT b w a) -> EnvT b w (f a) Source #

distGHisto :: (Functor f, Functor h) => (forall b. f (h b) -> h (f b)) -> f (Cofree h a) -> Cofree h (f a) Source #

distGFutu :: (Functor f, Functor h) => (forall b. h (f b) -> f (h b)) -> Free h (f a) -> f (Free h a) Source #

# Unfolding

class Functor (Base t) => Corecursive t where Source #

embed :: Base t t -> t Source #

:: (a -> Base t a) | a (Base t)-coalgebra |

-> a | seed |

-> t | resulting fixed point |

apo :: (a -> Base t (Either t a)) -> a -> t Source #

postpro :: Recursive t => (forall b. Base t b -> Base t b) -> (a -> Base t a) -> a -> t Source #

Fokkinga's postpromorphism

gpostpro :: (Recursive t, Monad m) => (forall b. m (Base t b) -> Base t (m b)) -> (forall c. Base t c -> Base t c) -> (a -> Base t (m a)) -> a -> t Source #

A generalized postpromorphism

## Instances

Corecursive Natural Source # | |

Defined in Data.Functor.Foldable embed :: Base Natural Natural -> Natural Source # ana :: (a -> Base Natural a) -> a -> Natural Source # apo :: (a -> Base Natural (Either Natural a)) -> a -> Natural Source # postpro :: Recursive Natural => (forall b. Base Natural b -> Base Natural b) -> (a -> Base Natural a) -> a -> Natural Source # gpostpro :: (Recursive Natural, Monad m) => (forall b. m (Base Natural b) -> Base Natural (m b)) -> (forall c. Base Natural c -> Base Natural c) -> (a -> Base Natural (m a)) -> a -> Natural Source # | |

Corecursive [a] Source # | |

Defined in Data.Functor.Foldable embed :: Base [a] [a] -> [a] Source # ana :: (a0 -> Base [a] a0) -> a0 -> [a] Source # apo :: (a0 -> Base [a] (Either [a] a0)) -> a0 -> [a] Source # postpro :: Recursive [a] => (forall b. Base [a] b -> Base [a] b) -> (a0 -> Base [a] a0) -> a0 -> [a] Source # gpostpro :: (Recursive [a], Monad m) => (forall b. m (Base [a] b) -> Base [a] (m b)) -> (forall c. Base [a] c -> Base [a] c) -> (a0 -> Base [a] (m a0)) -> a0 -> [a] Source # | |

Corecursive (Maybe a) Source # | |

Defined in Data.Functor.Foldable embed :: Base (Maybe a) (Maybe a) -> Maybe a Source # ana :: (a0 -> Base (Maybe a) a0) -> a0 -> Maybe a Source # apo :: (a0 -> Base (Maybe a) (Either (Maybe a) a0)) -> a0 -> Maybe a Source # postpro :: Recursive (Maybe a) => (forall b. Base (Maybe a) b -> Base (Maybe a) b) -> (a0 -> Base (Maybe a) a0) -> a0 -> Maybe a Source # gpostpro :: (Recursive (Maybe a), Monad m) => (forall b. m (Base (Maybe a) b) -> Base (Maybe a) (m b)) -> (forall c. Base (Maybe a) c -> Base (Maybe a) c) -> (a0 -> Base (Maybe a) (m a0)) -> a0 -> Maybe a Source # | |

Corecursive (NonEmpty a) Source # | |

Defined in Data.Functor.Foldable embed :: Base (NonEmpty a) (NonEmpty a) -> NonEmpty a Source # ana :: (a0 -> Base (NonEmpty a) a0) -> a0 -> NonEmpty a Source # apo :: (a0 -> Base (NonEmpty a) (Either (NonEmpty a) a0)) -> a0 -> NonEmpty a Source # postpro :: Recursive (NonEmpty a) => (forall b. Base (NonEmpty a) b -> Base (NonEmpty a) b) -> (a0 -> Base (NonEmpty a) a0) -> a0 -> NonEmpty a Source # gpostpro :: (Recursive (NonEmpty a), Monad m) => (forall b. m (Base (NonEmpty a) b) -> Base (NonEmpty a) (m b)) -> (forall c. Base (NonEmpty a) c -> Base (NonEmpty a) c) -> (a0 -> Base (NonEmpty a) (m a0)) -> a0 -> NonEmpty a Source # | |

Functor f => Corecursive (Nu f) Source # | |

Defined in Data.Functor.Foldable embed :: Base (Nu f) (Nu f) -> Nu f Source # ana :: (a -> Base (Nu f) a) -> a -> Nu f Source # apo :: (a -> Base (Nu f) (Either (Nu f) a)) -> a -> Nu f Source # postpro :: Recursive (Nu f) => (forall b. Base (Nu f) b -> Base (Nu f) b) -> (a -> Base (Nu f) a) -> a -> Nu f Source # gpostpro :: (Recursive (Nu f), Monad m) => (forall b. m (Base (Nu f) b) -> Base (Nu f) (m b)) -> (forall c. Base (Nu f) c -> Base (Nu f) c) -> (a -> Base (Nu f) (m a)) -> a -> Nu f Source # | |

Functor f => Corecursive (Mu f) Source # | |

Defined in Data.Functor.Foldable embed :: Base (Mu f) (Mu f) -> Mu f Source # ana :: (a -> Base (Mu f) a) -> a -> Mu f Source # apo :: (a -> Base (Mu f) (Either (Mu f) a)) -> a -> Mu f Source # postpro :: Recursive (Mu f) => (forall b. Base (Mu f) b -> Base (Mu f) b) -> (a -> Base (Mu f) a) -> a -> Mu f Source # gpostpro :: (Recursive (Mu f), Monad m) => (forall b. m (Base (Mu f) b) -> Base (Mu f) (m b)) -> (forall c. Base (Mu f) c -> Base (Mu f) c) -> (a -> Base (Mu f) (m a)) -> a -> Mu f Source # | |

Functor f => Corecursive (Fix f) Source # | |

Defined in Data.Functor.Foldable embed :: Base (Fix f) (Fix f) -> Fix f Source # ana :: (a -> Base (Fix f) a) -> a -> Fix f Source # apo :: (a -> Base (Fix f) (Either (Fix f) a)) -> a -> Fix f Source # postpro :: Recursive (Fix f) => (forall b. Base (Fix f) b -> Base (Fix f) b) -> (a -> Base (Fix f) a) -> a -> Fix f Source # gpostpro :: (Recursive (Fix f), Monad m) => (forall b. m (Base (Fix f) b) -> Base (Fix f) (m b)) -> (forall c. Base (Fix f) c -> Base (Fix f) c) -> (a -> Base (Fix f) (m a)) -> a -> Fix f Source # | |

Corecursive (Either a b) Source # | |

Defined in Data.Functor.Foldable embed :: Base (Either a b) (Either a b) -> Either a b Source # ana :: (a0 -> Base (Either a b) a0) -> a0 -> Either a b Source # apo :: (a0 -> Base (Either a b) (Either (Either a b) a0)) -> a0 -> Either a b Source # postpro :: Recursive (Either a b) => (forall b0. Base (Either a b) b0 -> Base (Either a b) b0) -> (a0 -> Base (Either a b) a0) -> a0 -> Either a b Source # gpostpro :: (Recursive (Either a b), Monad m) => (forall b0. m (Base (Either a b) b0) -> Base (Either a b) (m b0)) -> (forall c. Base (Either a b) c -> Base (Either a b) c) -> (a0 -> Base (Either a b) (m a0)) -> a0 -> Either a b Source # | |

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

Defined in Data.Functor.Foldable embed :: Base (Cofree f a) (Cofree f a) -> Cofree f a Source # ana :: (a0 -> Base (Cofree f a) a0) -> a0 -> Cofree f a Source # apo :: (a0 -> Base (Cofree f a) (Either (Cofree f a) a0)) -> a0 -> Cofree f a Source # postpro :: Recursive (Cofree f a) => (forall b. Base (Cofree f a) b -> Base (Cofree f a) b) -> (a0 -> Base (Cofree f a) a0) -> a0 -> Cofree f a Source # gpostpro :: (Recursive (Cofree f a), Monad m) => (forall b. m (Base (Cofree f a) b) -> Base (Cofree f a) (m b)) -> (forall c. Base (Cofree f a) c -> Base (Cofree f a) c) -> (a0 -> Base (Cofree f a) (m a0)) -> a0 -> Cofree f a Source # | |

Functor f => Corecursive (F f a) Source # | |

Defined in Data.Functor.Foldable embed :: Base (F f a) (F f a) -> F f a Source # ana :: (a0 -> Base (F f a) a0) -> a0 -> F f a Source # apo :: (a0 -> Base (F f a) (Either (F f a) a0)) -> a0 -> F f a Source # postpro :: Recursive (F f a) => (forall b. Base (F f a) b -> Base (F f a) b) -> (a0 -> Base (F f a) a0) -> a0 -> F f a Source # gpostpro :: (Recursive (F f a), Monad m) => (forall b. m (Base (F f a) b) -> Base (F f a) (m b)) -> (forall c. Base (F f a) c -> Base (F f a) c) -> (a0 -> Base (F f a) (m a0)) -> a0 -> F f a Source # | |

Functor f => Corecursive (Free f a) Source # | It may be better to work with the instance for |

Defined in Data.Functor.Foldable embed :: Base (Free f a) (Free f a) -> Free f a Source # ana :: (a0 -> Base (Free f a) a0) -> a0 -> Free f a Source # apo :: (a0 -> Base (Free f a) (Either (Free f a) a0)) -> a0 -> Free f a Source # postpro :: Recursive (Free f a) => (forall b. Base (Free f a) b -> Base (Free f a) b) -> (a0 -> Base (Free f a) a0) -> a0 -> Free f a Source # gpostpro :: (Recursive (Free f a), Monad m) => (forall b. m (Base (Free f a) b) -> Base (Free f a) (m b)) -> (forall c. Base (Free f a) c -> Base (Free f a) c) -> (a0 -> Base (Free f a) (m a0)) -> a0 -> Free f a Source # | |

(Functor m, Functor f) => Corecursive (FreeT f m a) Source # | |

Defined in Data.Functor.Foldable embed :: Base (FreeT f m a) (FreeT f m a) -> FreeT f m a Source # ana :: (a0 -> Base (FreeT f m a) a0) -> a0 -> FreeT f m a Source # apo :: (a0 -> Base (FreeT f m a) (Either (FreeT f m a) a0)) -> a0 -> FreeT f m a Source # postpro :: Recursive (FreeT f m a) => (forall b. Base (FreeT f m a) b -> Base (FreeT f m a) b) -> (a0 -> Base (FreeT f m a) a0) -> a0 -> FreeT f m a Source # gpostpro :: (Recursive (FreeT f m a), Monad m0) => (forall b. m0 (Base (FreeT f m a) b) -> Base (FreeT f m a) (m0 b)) -> (forall c. Base (FreeT f m a) c -> Base (FreeT f m a) c) -> (a0 -> Base (FreeT f m a) (m0 a0)) -> a0 -> FreeT f m a Source # | |

(Functor w, Functor f) => Corecursive (CofreeT f w a) Source # | |

Defined in Data.Functor.Foldable embed :: Base (CofreeT f w a) (CofreeT f w a) -> CofreeT f w a Source # ana :: (a0 -> Base (CofreeT f w a) a0) -> a0 -> CofreeT f w a Source # apo :: (a0 -> Base (CofreeT f w a) (Either (CofreeT f w a) a0)) -> a0 -> CofreeT f w a Source # postpro :: Recursive (CofreeT f w a) => (forall b. Base (CofreeT f w a) b -> Base (CofreeT f w a) b) -> (a0 -> Base (CofreeT f w a) a0) -> a0 -> CofreeT f w a Source # gpostpro :: (Recursive (CofreeT f w a), Monad m) => (forall b. m (Base (CofreeT f w a) b) -> Base (CofreeT f w a) (m b)) -> (forall c. Base (CofreeT f w a) c -> Base (CofreeT f w a) c) -> (a0 -> Base (CofreeT f w a) (m a0)) -> a0 -> CofreeT f w a Source # |

## Combinators

:: (Corecursive t, Monad m) | |

=> (forall b. m (Base t b) -> Base t (m b)) | a distributive law |

-> (a -> Base t (m a)) | a (Base t)-m-coalgebra |

-> a | seed |

-> t |

A generalized anamorphism

## Distributive laws

distGApoT :: (Functor f, Functor m) => (b -> f b) -> (forall c. m (f c) -> f (m c)) -> ExceptT b m (f a) -> f (ExceptT b m a) Source #

# Refolding

ghylo :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b Source #

A generalized hylomorphism

## Changing representation

# Common names

:: (Recursive t, Comonad w) | |

=> (forall b. Base t (w b) -> w (Base t b)) | a distributive law |

-> (Base t (w a) -> a) | a (Base t)-w-algebra |

-> t | fixed point |

-> a |

A generalized catamorphism

unfold :: Corecursive t => (a -> Base t a) -> a -> t Source #

:: (Corecursive t, Monad m) | |

=> (forall b. m (Base t b) -> Base t (m b)) | a distributive law |

-> (a -> Base t (m a)) | a (Base t)-m-coalgebra |

-> a | seed |

-> t |

A generalized anamorphism

grefold :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b Source #

A generalized hylomorphism

# Mendler-style

mhisto :: (forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c Source #

Mendler-style course-of-value iteration

# Elgot (co)algebras

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

Elgot coalgebras: http://comonad.com/reader/2008/elgot-coalgebras/

# Zygohistomorphic prepromorphisms

zygoHistoPrepro :: (Corecursive t, Recursive t) => (Base t b -> b) -> (forall c. Base t c -> Base t c) -> (Base t (EnvT b (Cofree (Base t)) a) -> a) -> t -> a Source #

Zygohistomorphic prepromorphisms:

A corrected and modernized version of http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms