recursion-schemes-4.1.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 [a] = Prim [a] type Base (Maybe a) = Const (Maybe a) Example boring stub for non-recursive data types type Base (Nu f) = f type Base (Mu f) = f type Base (Fix f) = f type Base (Either a b) = Const (Either a b) Example boring stub for non-recursive data types

# Fixed points

newtype Fix f Source

Constructors

 Fix (f (Fix f))

Instances

 Eq (f (Fix f)) => Eq (Fix f) Ord (f (Fix f)) => Ord (Fix f) Read (f (Fix f)) => Read (Fix f) Show (f (Fix f)) => Show (Fix f) Functor f => Unfoldable (Fix f) Functor f => Foldable (Fix f) Typeable ((* -> *) -> *) Fix type Base (Fix f) = f

newtype Mu f Source

Constructors

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

Instances

 (Functor f, Eq (f (Fix f)), Eq (Fix f)) => Eq (Mu f) (Functor f, Ord (f (Fix f)), Ord (Fix f)) => Ord (Mu f) (Functor f, Read (f (Fix f)), Read (Fix f)) => Read (Mu f) (Functor f, Show (f (Fix f)), Show (Fix f)) => Show (Mu f) Functor f => Unfoldable (Mu f) Functor f => Foldable (Mu f) type Base (Mu f) = f

data Nu f where Source

Constructors

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

Instances

 (Functor f, Eq (f (Fix f)), Eq (Fix f)) => Eq (Nu f) (Functor f, Ord (f (Fix f)), Ord (Fix f)) => Ord (Nu f) (Functor f, Read (f (Fix f)), Read (Fix f)) => Read (Nu f) (Functor f, Show (f (Fix f)), Show (Fix f)) => Show (Nu f) Functor f => Unfoldable (Nu f) Functor f => Foldable (Nu f) type Base (Nu f) = f

data family Prim t :: * -> * Source

Instances

 Functor (Prim [a]) (Eq a, Eq b) => Eq (Prim [a] b) (Ord a, Ord b) => Ord (Prim [a] b) (Read a, Read b) => Read (Prim [a] b) (Show a, Show b) => Show (Prim [a] b) data Prim [a] = Cons a b| Nil

# Folding

class Functor (Base t) => Foldable 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

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

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

Fokkinga's prepromorphism

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

 Foldable [a] Foldable (Maybe a) Functor f => Foldable (Nu f) Functor f => Foldable (Mu f) Functor f => Foldable (Fix f) Foldable (Either a b)

## Combinators

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

Arguments

 :: (Foldable 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 :: Foldable t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a Source

gzygo :: (Foldable 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 :: Foldable t => (Base t (Cofree (Base t) a) -> a) -> t -> a Source

Course-of-value iteration

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

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

## Distributive laws

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

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

distParaT :: (Unfoldable 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) => Unfoldable 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 :: Foldable t => (a -> Base t (Either t a)) -> a -> t Source

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

Fokkinga's postpromorphism

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

 Unfoldable [a] Unfoldable (Maybe a) Functor f => Unfoldable (Nu f) Functor f => Unfoldable (Mu f) Functor f => Unfoldable (Fix f) Unfoldable (Either a b)

## Combinators

Arguments

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

# 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 :: (Foldable s, Unfoldable t, Base s ~ Base t) => s -> t Source

# Common names

fold :: Foldable t => (Base t a -> a) -> t -> a Source

Arguments

 :: (Foldable 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 :: Unfoldable t => (a -> Base t a) -> a -> t Source

Arguments

 :: (Unfoldable 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 :: (Unfoldable t, Foldable 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: