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
- lambek :: (Recursive t, Corecursive t) => t -> Base t t
- colambek :: (Recursive t, Corecursive t) => Base t t -> 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 |

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

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