Safe Haskell | None |
---|---|
Language | Haskell2010 |
Synopsis
- type family Base t :: * -> *
- class Functor (Base t) => Recursive t where
- class Functor (Base t) => Corecursive t where
- newtype Fix f = Fix {}
- newtype Mu f = Mu (forall a. (f a -> a) -> a)
- data Nu f = Nu (a -> f a) a
- data ListF a b
- data NonEmptyF a b = NonEmptyF a (Maybe b)
- hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
- prepro :: (Recursive t, Corecursive t) => (Base t t -> Base t t) -> (Base t a -> a) -> t -> a
- postpro :: (Recursive t, Corecursive t) => (Base t t -> Base t t) -> (a -> Base t a) -> a -> t
- mutu :: Recursive t => (Base t (a, a) -> a) -> (Base t (a, a) -> a) -> t -> a
- zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a
- para :: (Recursive t, Corecursive t) => (Base t (t, a) -> a) -> t -> a
- apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t
- 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
- micro :: Corecursive a => (b -> Either a (Base a b)) -> b -> a
- meta :: (Corecursive t', Recursive t) => (a -> Base t' a) -> (b -> a) -> (Base t b -> b) -> t -> t'
- meta' :: Functor g => (f a -> a) -> (forall c. g c -> f c) -> (b -> g b) -> b -> a
- dicata :: Recursive t => (Base t (a, t) -> a) -> (Base t (a, t) -> t) -> t -> a
- cata :: Recursive t => (Base t a -> a) -> t -> a
- ana :: Corecursive t => (a -> Base t a) -> a -> t
- mhisto :: (forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c
- mcata :: (forall y. (y -> c) -> f y -> c) -> Fix f -> c
- cataM :: (Recursive t, Traversable (Base t), Monad m) => (Base t a -> m a) -> t -> m a
- anaM :: (Corecursive t, Traversable (Base t), Monad m) => (a -> m (Base t a)) -> a -> m t
- hyloM :: (Traversable f, Monad m) => (f b -> m b) -> (a -> m (f a)) -> a -> m b
- scolio :: Functor g => ((f b -> b) -> Trans b b) -> ((a -> f a) -> Lens a a) -> (g b -> b) -> (a -> g a) -> (f b -> b) -> (a -> f a) -> a -> b
- dendro :: Recursive t' => ((f a -> a) -> Trans b b) -> (f a -> a) -> (Base t' b -> b) -> t' -> b
- chema :: Corecursive t' => ((a -> f a) -> Lens b b) -> (a -> f a) -> (b -> Base t' b) -> b -> t'
- lambek :: (Recursive t, Corecursive t) => t -> Base t t
- colambek :: (Recursive t, Corecursive t) => Base t t -> t
- hoist :: (Recursive s, Corecursive t) => (forall a. Base s a -> Base t a) -> s -> t
- refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s -> t
Typeclasses
type family Base t :: * -> * Source #
Instances
type Base Natural Source # | |
Defined in Control.Recursion | |
type Base [a] Source # | |
Defined in Control.Recursion | |
type Base (NonEmpty a) Source # | |
Defined in Control.Recursion | |
type Base (Mu f) Source # | |
Defined in Control.Recursion | |
type Base (Nu f) Source # | |
Defined in Control.Recursion | |
type Base (Fix f) Source # | |
Defined in Control.Recursion | |
type Base (Fix f) Source # | |
Defined in Control.Recursion |
class Functor (Base t) => Corecursive t where Source #
Instances
Corecursive Natural Source # | |
Corecursive [a] Source # | |
Defined in Control.Recursion | |
Corecursive (NonEmpty a) Source # | |
Functor f => Corecursive (Mu f) Source # | |
Functor f => Corecursive (Nu f) Source # | |
Functor f => Corecursive (Fix f) Source # | |
Types
Mu (forall a. (f a -> a) -> a) |
Nu (a -> f a) a |
Recursion schemes
hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b Source #
Base functor for a list of type [a]
.
| Hylomorphism; fold a structure while buildiung it up.
prepro :: (Recursive t, Corecursive t) => (Base t t -> Base t t) -> (Base t a -> a) -> t -> a Source #
Prepromorphism. Fold a structure while applying a natural transformation at each step.
postpro :: (Recursive t, Corecursive t) => (Base t t -> Base t t) -> (a -> Base t a) -> a -> t Source #
Postpromorphism. Build up a structure, applying a natural transformation along the way.
mutu :: Recursive t => (Base t (a, a) -> a) -> (Base t (a, a) -> a) -> t -> a Source #
A mutumorphism.
zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a Source #
Zygomorphism (see here for a neat example)
elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a Source #
Elgot algebra (see this paper)
micro :: Corecursive a => (b -> Either a (Base a b)) -> b -> a Source #
Anamorphism allowing shortcuts. Compare apo
meta :: (Corecursive t', Recursive t) => (a -> Base t' a) -> (b -> a) -> (Base t b -> b) -> t -> t' Source #
Gibbons' metamorphism. Tear down a structure, transform it, and then build up a new structure
meta' :: Functor g => (f a -> a) -> (forall c. g c -> f c) -> (b -> g b) -> b -> a Source #
Erwig's metamorphism. Essentially a hylomorphism with a natural transformation in between. This allows us to use more than one functor in a hylomorphism.
dicata :: Recursive t => (Base t (a, t) -> a) -> (Base t (a, t) -> t) -> t -> a Source #
Catamorphism collapsing along two data types simultaneously. Basically a fancy zygomorphism.
cata :: Recursive t => (Base t a -> a) -> t -> a Source #
Catamorphism. Folds a structure. (see here)
ana :: Corecursive t => (a -> Base t a) -> a -> t Source #
Anamorphism, meant to build up a structure recursively.
Mendler-style recursion schemes
mhisto :: (forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c Source #
Mendler's histomorphism
Monadic recursion schemes
anaM :: (Corecursive t, Traversable (Base t), Monad m) => (a -> m (Base t a)) -> a -> m t Source #
hyloM :: (Traversable f, Monad m) => (f b -> m b) -> (a -> m (f a)) -> a -> m b Source #
Mutual recursion
:: Functor g | |
=> ((f b -> b) -> Trans b b) | A pseudoprism parametric in an \( F \)-algebra that allows |
-> ((a -> f a) -> Lens a a) | A lens parametric in an \( F \)-coalgebra that allows |
-> (g b -> b) | A |
-> (a -> g a) | A |
-> (f b -> b) | An |
-> (a -> f a) | An |
-> a | |
-> b |
Entangle two hylomorphisms.
:: Recursive t' | |
=> ((f a -> a) -> Trans b b) | A pseudoprism parametric in an \(F \)-algebra that allows |
-> (f a -> a) | A |
-> (Base t' b -> b) | A |
-> t' | |
-> b |
A dendromorphism entangles two catamorphisms
:: Corecursive t' | |
=> ((a -> f a) -> Lens b b) | A lens parametric in an \( F \)-coalgebra that allows |
-> (a -> f a) | A |
-> (b -> Base t' b) | A |
-> b | |
-> t' |