recursion-schemes-5.0.2: Generalized bananas, lenses and barbed wire

Data.Functor.Foldable

Description

Synopsis

# Base functors for fixed points

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

Instances

 type Base Natural Source # type Base Natural = Maybe type Base [a] Source # type Base [a] = ListF a type Base (Maybe a) Source # type Base (Maybe a) = Const * (Maybe a) type Base (NonEmpty a) Source # type Base (NonEmpty a) = NonEmptyF a type Base (Nu f) Source # type Base (Nu f) = f type Base (Mu f) Source # type Base (Mu f) = f type Base (Fix f) Source # type Base (Fix f) = f type Base (Either a b) Source # type Base (Either a b) = Const * (Either a b) type Base (Cofree f a) Source # type Base (Cofree f a) = CofreeF f a type Base (F f a) Source # type Base (F f a) = FreeF f a type Base (Free f a) Source # type Base (Free f a) = FreeF f a type Base (CofreeT f w a) Source # type Base (CofreeT f w a) = Compose * * w (CofreeF f a) type Base (FreeT f m a) Source # type Base (FreeT f m a) = Compose * * m (FreeF f a)

data ListF a b Source #

Base functor of [].

Constructors

 Nil Cons a b

Instances

# Fixed points

newtype Fix f Source #

Constructors

 Fix (f (Fix f))

Instances

unfix :: Fix f -> f (Fix f) Source #

newtype Mu f Source #

Constructors

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

Instances

data Nu f where Source #

Constructors

 Nu :: (a -> f a) -> a -> Nu f

Instances

# Folding

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

Minimal complete definition

project

Methods

project :: t -> Base t t Source #

cata :: (Base t a -> a) -> t -> a Source #

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

## Combinators

gapo :: Corecursive t => (b -> Base t b) -> (a -> Base t (Either b a)) -> a -> t Source #

Arguments

 :: (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

zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a Source #

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 #

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

chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> b 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

distCata :: Functor f => f (Identity a) -> Identity (f a) Source #

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

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 #

Arguments

 :: 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 #

distHisto :: Functor f => f (Cofree f a) -> Cofree f (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 #

distFutu :: Functor f => Free f (f a) -> f (Free 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 #

Minimal complete definition

embed

Methods

embed :: Base t t -> t Source #

ana :: (a -> Base t a) -> a -> t Source #

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

 Source # Methodsana :: (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 # Methodsembed :: Base [a] [a] -> [a] Source #ana :: (a -> Base [a] a) -> a -> [a] Source #apo :: (a -> Base [a] (Either [a] a)) -> a -> [a] Source #postpro :: Recursive [a] => (forall b. Base [a] b -> Base [a] b) -> (a -> Base [a] a) -> a -> [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) -> (a -> Base [a] (m a)) -> a -> [a] Source # Source # Methodsembed :: Base (Maybe a) (Maybe a) -> Maybe a Source #ana :: (a -> Base (Maybe a) a) -> a -> Maybe a Source #apo :: (a -> Base (Maybe a) (Either (Maybe a) a)) -> a -> Maybe a Source #postpro :: Recursive (Maybe a) => (forall b. Base (Maybe a) b -> Base (Maybe a) b) -> (a -> Base (Maybe a) a) -> a -> 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) -> (a -> Base (Maybe a) (m a)) -> a -> Maybe a Source # Source # Methodsembed :: Base (NonEmpty a) (NonEmpty a) -> NonEmpty a Source #ana :: (a -> Base (NonEmpty a) a) -> a -> NonEmpty a Source #apo :: (a -> Base (NonEmpty a) (Either (NonEmpty a) a)) -> a -> NonEmpty a Source #postpro :: Recursive (NonEmpty a) => (forall b. Base (NonEmpty a) b -> Base (NonEmpty a) b) -> (a -> Base (NonEmpty a) a) -> a -> 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) -> (a -> Base (NonEmpty a) (m a)) -> a -> NonEmpty a Source # Functor f => Corecursive (Nu f) Source # Methodsembed :: 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 # Methodsembed :: 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 # Methodsembed :: 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 # Methodsembed :: Base (Either a b) (Either a b) -> Either a b Source #ana :: (a -> Base (Either a b) a) -> a -> Either a b Source #apo :: (a -> Base (Either a b) (Either (Either a b) a)) -> a -> Either a b Source #postpro :: Recursive (Either a b) => (forall c. Base (Either a b) c -> Base (Either a b) c) -> (a -> Base (Either a b) a) -> a -> Either a b Source #gpostpro :: (Recursive (Either a b), Monad m) => (forall c. m (Base (Either a b) c) -> Base (Either a b) (m c)) -> (forall c. Base (Either a b) c -> Base (Either a b) c) -> (a -> Base (Either a b) (m a)) -> a -> Either a b Source # Functor f => Corecursive (Cofree f a) Source # Methodsembed :: Base (Cofree f a) (Cofree f a) -> Cofree f a Source #ana :: (a -> Base (Cofree f a) a) -> a -> Cofree f a Source #apo :: (a -> Base (Cofree f a) (Either (Cofree f a) a)) -> a -> Cofree f a Source #postpro :: Recursive (Cofree f a) => (forall b. Base (Cofree f a) b -> Base (Cofree f a) b) -> (a -> Base (Cofree f a) a) -> a -> 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) -> (a -> Base (Cofree f a) (m a)) -> a -> Cofree f a Source # Functor f => Corecursive (F f a) Source # Methodsembed :: Base (F f a) (F f a) -> F f a Source #ana :: (a -> Base (F f a) a) -> a -> F f a Source #apo :: (a -> Base (F f a) (Either (F f a) a)) -> a -> F f a Source #postpro :: Recursive (F f a) => (forall b. Base (F f a) b -> Base (F f a) b) -> (a -> Base (F f a) a) -> a -> 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) -> (a -> Base (F f a) (m a)) -> a -> F f a Source # Functor f => Corecursive (Free f a) Source # It may be better to work with the instance for F directly. Methodsembed :: Base (Free f a) (Free f a) -> Free f a Source #ana :: (a -> Base (Free f a) a) -> a -> Free f a Source #apo :: (a -> Base (Free f a) (Either (Free f a) a)) -> a -> Free f a Source #postpro :: Recursive (Free f a) => (forall b. Base (Free f a) b -> Base (Free f a) b) -> (a -> Base (Free f a) a) -> a -> 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) -> (a -> Base (Free f a) (m a)) -> a -> Free f a Source # (Functor w, Functor f) => Corecursive (CofreeT f w a) Source # Methodsembed :: Base (CofreeT f w a) (CofreeT f w a) -> CofreeT f w a Source #ana :: (a -> Base (CofreeT f w a) a) -> a -> CofreeT f w a Source #apo :: (a -> Base (CofreeT f w a) (Either (CofreeT f w a) a)) -> a -> 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) -> (a -> Base (CofreeT f w a) a) -> a -> 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) -> (a -> Base (CofreeT f w a) (m a)) -> a -> CofreeT f w a Source # (Functor m, Functor f) => Corecursive (FreeT f m a) Source # Methodsembed :: Base (FreeT f m a) (FreeT f m a) -> FreeT f m a Source #ana :: (a -> Base (FreeT f m a) a) -> a -> FreeT f m a Source #apo :: (a -> Base (FreeT f m a) (Either (FreeT f m a) a)) -> a -> 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) -> (a -> Base (FreeT f m a) a) -> a -> FreeT f m a Source #gpostpro :: (Recursive (FreeT f m a), Monad m) => (forall b. m (Base (FreeT f m a) b) -> Base (FreeT f m a) (m b)) -> (forall c. Base (FreeT f m a) c -> Base (FreeT f m a) c) -> (a -> Base (FreeT f m a) (m a)) -> a -> FreeT f m a Source #

## Combinators

Arguments

 :: (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

distAna :: Functor f => Identity (f a) -> f (Identity a) Source #

distApo :: Recursive t => Either t (Base t a) -> Base t (Either t a) Source #

distGApo :: Functor f => (b -> f b) -> Either b (f a) -> f (Either b a) Source #

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

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

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

refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s -> t Source #

# Common names

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

Arguments

 :: (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 #

Arguments

 :: (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

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

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

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

Mendler-style iteration

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

Mendler-style course-of-value iteration

# Elgot (co)algebras

elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a Source #

Elgot algebras

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

# 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: