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

type Base (Fix f)

Defined in Control.Recursion

type Base (Fix f) = f

class Functor (Base t) => Recursive t where

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)

Functor f => Recursive (Fix f)

Defined in Control.Recursion

Methods

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

class Functor (Base t) => Corecursive t where

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

Functor f => Corecursive (Fix f)

Defined in Control.Recursion

Methods

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

Types

newtype Fix f

Constructors

Fix

Fields

• unFix :: f (Fix f)

Instances

Functor f => Corecursive (Fix f)

Defined in Control.Recursion

Methods

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

Functor f => Recursive (Fix f)

Defined in Control.Recursion

Methods

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

type Base (Fix f)

Defined in Control.Recursion

type Base (Fix f) = f

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

Base functor for a list of type [a].

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

Foldable (ListF a)

Defined in Control.Recursion

Methods

fold :: Monoid m => ListF a m -> m

foldMap :: Monoid m => (a0 -> m) -> ListF a a0 -> m

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

foldr' :: (a0 -> b -> b) -> b -> ListF a a0 -> b

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

foldl' :: (b -> a0 -> b) -> b -> ListF a a0 -> b

foldr1 :: (a0 -> a0 -> a0) -> ListF a a0 -> a0

foldl1 :: (a0 -> a0 -> a0) -> ListF a a0 -> a0

toList :: ListF a a0 -> [a0]

null :: ListF a a0 -> Bool

length :: ListF a a0 -> Int

elem :: Eq a0 => a0 -> ListF a a0 -> Bool

maximum :: Ord a0 => ListF a a0 -> a0

minimum :: Ord a0 => ListF a a0 -> a0

sum :: Num a0 => ListF a a0 -> a0

product :: Num a0 => ListF a a0 -> a0

Traversable (ListF a)

Defined in Control.Recursion

Methods

traverse :: Applicative f => (a0 -> f b) -> ListF a a0 -> f (ListF a b)

sequenceA :: Applicative f => ListF a (f a0) -> f (ListF a a0)

mapM :: Monad m => (a0 -> m b) -> ListF a a0 -> m (ListF a b)

sequence :: Monad m => ListF a (m a0) -> m (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

Foldable (NonEmptyF a)

Defined in Control.Recursion

Methods

fold :: Monoid m => NonEmptyF a m -> m

foldMap :: Monoid m => (a0 -> m) -> NonEmptyF a a0 -> m

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

foldr' :: (a0 -> b -> b) -> b -> NonEmptyF a a0 -> b

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

foldl' :: (b -> a0 -> b) -> b -> NonEmptyF a a0 -> b

foldr1 :: (a0 -> a0 -> a0) -> NonEmptyF a a0 -> a0

foldl1 :: (a0 -> a0 -> a0) -> NonEmptyF a a0 -> a0

toList :: NonEmptyF a a0 -> [a0]

null :: NonEmptyF a a0 -> Bool

length :: NonEmptyF a a0 -> Int

elem :: Eq a0 => a0 -> NonEmptyF a a0 -> Bool

maximum :: Ord a0 => NonEmptyF a a0 -> a0

minimum :: Ord a0 => NonEmptyF a a0 -> a0

sum :: Num a0 => NonEmptyF a a0 -> a0

product :: Num a0 => NonEmptyF a a0 -> a0

Traversable (NonEmptyF a)

Defined in Control.Recursion

Methods

traverse :: Applicative f => (a0 -> f b) -> NonEmptyF a a0 -> f (NonEmptyF a b)

sequenceA :: Applicative f => NonEmptyF a (f a0) -> f (NonEmptyF a a0)

mapM :: Monad m => (a0 -> m b) -> NonEmptyF a a0 -> m (NonEmptyF a b)

sequence :: Monad m => NonEmptyF a (m a0) -> m (NonEmptyF a a0)

Recursion schemes

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

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

Co-(Elgot algebra)

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.

scolio :: Recursive t => (Base t (a, t) -> a) -> (Base t (a, t) -> t) -> t -> a

Catamorphism collaψng along two data types simultaneously.

cata :: Recursive t => (Base t a -> a) -> t -> a

Catamorphism. Folds a structure. (see here)

ana :: Corecursive t => (a -> Base t a) -> a -> t

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

Mendler's histomorφsm

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

zygoM :: (Recursive t, Traversable (Base t), Monad m) => (Base t b -> m b) -> (Base t (b, a) -> m a) -> t -> m a

zygoM' :: (Recursive t, Traversable (Base t), Monad m) => (Base t b -> m b) -> (Base t (b, a) -> m a) -> t -> m a

scolioM :: (Recursive t, Traversable (Base t), Monad m) => (Base t (t, a) -> m t) -> (Base t (t, a) -> m a) -> t -> m a

scolioM' :: (Recursive t, Traversable (Base t), Monad m) => (Base t (t, a) -> m t) -> (Base t (t, a) -> m a) -> t -> m a

coelgotM :: (Traversable f, Monad m) => ((a, f b) -> m b) -> (a -> m (f a)) -> a -> m b

elgotM :: (Traversable f, Monad m) => (f a -> m a) -> (b -> m (Either a (f b))) -> b -> m a

paraM :: (Recursive t, Corecursive t, Traversable (Base t), Monad m) => (Base t (t, a) -> m a) -> t -> m a

mutuM :: (Recursive t, Traversable (Base t), Monad m) => (Base t (a, a) -> m a) -> (Base t (a, a) -> m a) -> t -> m a

mutuM' :: (Recursive t, Traversable (Base t), Monad m) => (Base t (a, a) -> m a) -> (Base t (a, a) -> m a) -> t -> m a

microM :: (Corecursive a, Traversable (Base a), Monad m) => (b -> m (Either a (Base a b))) -> b -> m a

Helper functions

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