Control.Recursion

Typeclasses

type family Base t :: * -> *

Instances

type Base Natural

Defined in Control.Recursion

type Base Natural = Maybe

type Base [a]

Defined in Control.Recursion

type Base [a] = ListF a

type Base (NonEmpty a)

Defined in Control.Recursion

type Base (NonEmpty a) = NonEmptyF a

type Base (Mu f)

Defined in Control.Recursion

type Base (Mu f) = f

type Base (Nu f)

Defined in Control.Recursion

type Base (Nu f) = f

type Base (Fix f)

Defined in Control.Recursion

type Base (Fix f) = f

class Functor (Base t) => Recursive t where

Minimal complete definition

project

Methods

project :: t -> Base t t

Instances

Recursive Natural

Defined in Control.Recursion

Methods

project :: Natural -> Base Natural Natural

Recursive [a]

Defined in Control.Recursion

Methods

project :: [a] -> Base [a] [a]

Recursive (NonEmpty a)

Defined in Control.Recursion

Methods

project :: NonEmpty a -> Base (NonEmpty a) (NonEmpty a)

Functor f => Recursive (Mu f)

Defined in Control.Recursion

Methods

project :: Mu f -> Base (Mu f) (Mu f)

Functor f => Recursive (Nu f)

Defined in Control.Recursion

Methods

project :: Nu f -> Base (Nu f) (Nu f)

class Functor (Base t) => Corecursive t where

Minimal complete definition

embed

Methods

embed :: Base t t -> t

Instances

Corecursive Natural

Defined in Control.Recursion

Methods

embed :: Base Natural Natural -> Natural

Corecursive [a]

Defined in Control.Recursion

Methods

embed :: Base [a] [a] -> [a]

Corecursive (NonEmpty a)

Defined in Control.Recursion

Methods

embed :: Base (NonEmpty a) (NonEmpty a) -> NonEmpty a

Functor f => Corecursive (Mu f)

Defined in Control.Recursion

Methods

embed :: Base (Mu f) (Mu f) -> Mu f

Functor f => Corecursive (Nu f)

Defined in Control.Recursion

Methods

embed :: Base (Nu f) (Nu f) -> Nu f

Types

newtype Fix f

Constructors

Fix

Fields

• unFix :: f (Fix f)

Instances

type Base (Fix f)

Defined in Control.Recursion

type Base (Fix f) = f

newtype Mu f

Constructors

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

Instances

Functor f => Corecursive (Mu f)

Defined in Control.Recursion

Methods

embed :: Base (Mu f) (Mu f) -> Mu f

Functor f => Recursive (Mu f)

Defined in Control.Recursion

Methods

project :: Mu f -> Base (Mu f) (Mu f)

type Base (Mu f)

Defined in Control.Recursion

type Base (Mu f) = f

data Nu f

Constructors

Nu (a -> f a) a

Instances

Functor f => Corecursive (Nu f)

Defined in Control.Recursion

Methods

embed :: Base (Nu f) (Nu f) -> Nu f

Functor f => Recursive (Nu f)

Defined in Control.Recursion

Methods

project :: Nu f -> Base (Nu f) (Nu f)

type Base (Nu f)

Defined in Control.Recursion

type Base (Nu f) = f

data ListF a b

Constructors

Cons a b

Nil

Instances

Functor (ListF a)

Defined in Control.Recursion

Methods

fmap :: (a0 -> b) -> ListF a a0 -> ListF a b

(<$) :: a0 -> ListF a b -> ListF a a0

data NonEmptyF a b

Constructors

NonEmptyF a (Maybe b)

Instances

Functor (NonEmptyF a)

Defined in Control.Recursion

Methods

fmap :: (a0 -> b) -> NonEmptyF a a0 -> NonEmptyF a b

(<$) :: a0 -> NonEmptyF a b -> NonEmptyF a a0

Recursion schemes

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

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

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

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

A mutumorphism.

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

Zygomorphism (see here for a neat example)

para :: (Recursive t, Corecursive t) => (Base t (t, a) -> a) -> t -> a

Paramorphism

apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t

Apomorphism. Compare micro.

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

Elgot algebra (see this paper)

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

Elgot coalgebra

micro :: Corecursive a => (b -> Either a (Base a b)) -> b -> a

Anamorphism allowing shortcuts. Compare apo

meta :: (Corecursive t', Recursive t) => (a -> Base t' a) -> (b -> a) -> (Base t b -> b) -> t -> t'

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

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

Catamorphism collapsing along two data types simultaneously. Basically a fancy zygomorphism.

Mendler-style recursion schemes

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

Mendler's histomorphism

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

Mendler's catamorphism

Monadic recursion schemes

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

Helper functions

lambek :: (Recursive t, Corecursive t) => t -> Base t t

colambek :: (Recursive t, Corecursive t) => Base t t -> t