micro-recursion-schemes-5.0.2.2: Simple recursion schemes

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)

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

 (Functor f, Eq1 f) => Eq (Mu f) Source # Methods(==) :: Mu f -> Mu f -> Bool #(/=) :: Mu f -> Mu f -> Bool # (Functor f, Ord1 f) => Ord (Mu f) Source # Methodscompare :: Mu f -> Mu f -> Ordering #(<) :: Mu f -> Mu f -> Bool #(<=) :: Mu f -> Mu f -> Bool #(>) :: Mu f -> Mu f -> Bool #(>=) :: Mu f -> Mu f -> Bool #max :: Mu f -> Mu f -> Mu f #min :: Mu f -> Mu f -> Mu f # (Functor f, Read1 f) => Read (Mu f) Source # MethodsreadsPrec :: Int -> ReadS (Mu f) #readList :: ReadS [Mu f] #readPrec :: ReadPrec (Mu f) # (Functor f, Show1 f) => Show (Mu f) Source # MethodsshowsPrec :: Int -> Mu f -> ShowS #show :: Mu f -> String #showList :: [Mu f] -> ShowS # 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 => Recursive (Mu f) Source # Methodsproject :: 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 #prepro :: Corecursive (Mu f) => (forall b. Base (Mu f) b -> Base (Mu f) b) -> (Base (Mu f) a -> a) -> Mu f -> a Source # type Base (Mu f) Source # type Base (Mu f) = f

data Nu f where Source #

Constructors

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

Instances

 (Functor f, Eq1 f) => Eq (Nu f) Source # Methods(==) :: Nu f -> Nu f -> Bool #(/=) :: Nu f -> Nu f -> Bool # (Functor f, Ord1 f) => Ord (Nu f) Source # Methodscompare :: Nu f -> Nu f -> Ordering #(<) :: Nu f -> Nu f -> Bool #(<=) :: Nu f -> Nu f -> Bool #(>) :: Nu f -> Nu f -> Bool #(>=) :: Nu f -> Nu f -> Bool #max :: Nu f -> Nu f -> Nu f #min :: Nu f -> Nu f -> Nu f # (Functor f, Read1 f) => Read (Nu f) Source # MethodsreadsPrec :: Int -> ReadS (Nu f) #readList :: ReadS [Nu f] #readPrec :: ReadPrec (Nu f) # (Functor f, Show1 f) => Show (Nu f) Source # MethodsshowsPrec :: Int -> Nu f -> ShowS #show :: Nu f -> String #showList :: [Nu f] -> ShowS # 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 => Recursive (Nu f) Source # Methodsproject :: 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 #prepro :: Corecursive (Nu f) => (forall b. Base (Nu f) b -> Base (Nu f) b) -> (Base (Nu f) a -> a) -> Nu f -> a Source # type Base (Nu f) Source # type Base (Nu f) = f

# Folding

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

Minimal complete definition

project

Methods

project :: t -> Base t t Source #

Arguments

 :: (Base t a -> a) a (Base t)-algebra -> t fixed point -> a result

para :: (Base t (t, 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

Instances

 Source # Methodscata :: (Base Natural a -> a) -> Natural -> a Source #para :: (Base Natural (Natural, a) -> a) -> Natural -> a Source #prepro :: Corecursive Natural => (forall b. Base Natural b -> Base Natural b) -> (Base Natural a -> a) -> Natural -> a Source # Recursive [a] Source # Methodsproject :: [a] -> Base [a] [a] Source #cata :: (Base [a] a -> a) -> [a] -> a Source #para :: (Base [a] ([a], a) -> a) -> [a] -> a Source #prepro :: Corecursive [a] => (forall b. Base [a] b -> Base [a] b) -> (Base [a] a -> a) -> [a] -> a Source # Source # Methodsproject :: Maybe a -> Base (Maybe a) (Maybe a) Source #cata :: (Base (Maybe a) a -> a) -> Maybe a -> a Source #para :: (Base (Maybe a) (Maybe a, a) -> a) -> Maybe a -> a Source #prepro :: Corecursive (Maybe a) => (forall b. Base (Maybe a) b -> Base (Maybe a) b) -> (Base (Maybe a) a -> a) -> Maybe a -> a Source # Source # Methodsproject :: NonEmpty a -> Base (NonEmpty a) (NonEmpty a) Source #cata :: (Base (NonEmpty a) a -> a) -> NonEmpty a -> a Source #para :: (Base (NonEmpty a) (NonEmpty a, a) -> a) -> NonEmpty a -> a Source #prepro :: Corecursive (NonEmpty a) => (forall b. Base (NonEmpty a) b -> Base (NonEmpty a) b) -> (Base (NonEmpty a) a -> a) -> NonEmpty a -> a Source # Functor f => Recursive (Nu f) Source # Methodsproject :: 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 #prepro :: Corecursive (Nu f) => (forall b. Base (Nu f) b -> Base (Nu f) b) -> (Base (Nu f) a -> a) -> Nu f -> a Source # Functor f => Recursive (Mu f) Source # Methodsproject :: 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 #prepro :: Corecursive (Mu f) => (forall b. Base (Mu f) b -> Base (Mu f) b) -> (Base (Mu f) a -> a) -> Mu f -> a Source # Functor f => Recursive (Fix f) Source # Methodsproject :: 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 #prepro :: Corecursive (Fix f) => (forall b. Base (Fix f) b -> Base (Fix f) b) -> (Base (Fix f) a -> a) -> Fix f -> a Source # Recursive (Either a b) Source # Methodsproject :: Either a b -> Base (Either a b) (Either a b) Source #cata :: (Base (Either a b) a -> a) -> Either a b -> a Source #para :: (Base (Either a b) (Either a b, a) -> a) -> Either a b -> a Source #prepro :: Corecursive (Either a b) => (forall c. Base (Either a b) c -> Base (Either a b) c) -> (Base (Either a b) a -> a) -> Either a b -> a Source #

## Combinators

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

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

# Unfolding

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

Minimal complete definition

embed

Methods

embed :: Base t t -> t Source #

Arguments

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

 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 #

# Refolding

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

## Changing representation

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

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