Copyright  (C) 20082015 Edward Kmett 

License  BSDstyle (see the file LICENSE) 
Maintainer  "Samuel Gélineau" <gelisam@gmail.com>, "Luc Tielen" <luc.tielen@gmail.com>, "Ryan Scott" <ryan.gl.scott@gmail.com> 
Stability  experimental 
Portability  nonportable 
Safe Haskell  SafeInferred 
Language  Haskell2010 
Synopsis
 type family Base t :: * > *
 data ListF a b
 class Functor (Base t) => Recursive t where
 class Functor (Base t) => Corecursive t where
 fold :: Recursive t => (Base t a > a) > t > a
 cata :: Recursive t => (Base t a > a) > t > a
 cataA :: Recursive t => (Base t (f a) > f a) > t > f a
 para :: Recursive t => (Base t (t, a) > a) > t > a
 histo :: Recursive t => (Base t (Cofree (Base t) a) > a) > t > a
 zygo :: Recursive t => (Base t b > b) > (Base t (b, a) > a) > t > a
 unfold :: Corecursive t => (a > Base t a) > a > t
 ana :: Corecursive t => (a > Base t a) > a > t
 apo :: Corecursive t => (a > Base t (Either t a)) > a > t
 futu :: Corecursive t => (a > Base t (Free (Base t) a)) > a > t
 refold :: Functor f => (f b > b) > (a > f a) > a > b
 hylo :: Functor f => (f b > b) > (a > f a) > a > b
 chrono :: Functor f => (f (Cofree f b) > b) > (a > f (Free f a)) > a > b
 refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s > t
 hoist :: (Recursive s, Corecursive t) => (forall a. Base s a > Base t a) > s > t
 transverse :: (Recursive s, Corecursive t, Functor f) => (forall a. Base s (f a) > f (Base t a)) > s > f t
 cotransverse :: (Recursive s, Corecursive t, Functor f) => (forall a. f (Base s a) > Base t (f a)) > f s > t
 mcata :: (forall y. (y > c) > f y > c) > Fix f > c
 mpara :: (forall y. (y > c) > (y > Fix f) > f y > c) > Fix f > c
 mhisto :: (forall y. (y > c) > (y > f y) > f y > c) > Fix f > c
 mzygo :: (forall y. (y > b) > f y > b) > (forall y. (y > c) > (y > b) > f y > c) > Fix f > c
 mana :: (forall y. (x > y) > x > f y) > x > Fix f
 mapo :: (forall y. (Fix f > y) > (x > y) > x > f y) > x > Fix f
 mfutu :: (forall y. (f y > y) > (x > y) > x > f y) > x > Fix f
 prepro :: (Recursive t, Corecursive t) => (forall b. Base t b > Base t b) > (Base t a > a) > t > a
 postpro :: (Corecursive t, Recursive t) => (forall b. Base t b > Base t b) > (a > Base 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
 gfold :: (Recursive t, Comonad w) => (forall b. Base t (w b) > w (Base t b)) > (Base t (w a) > a) > t > a
 gcata :: (Recursive t, Comonad w) => (forall b. Base t (w b) > w (Base t b)) > (Base t (w a) > a) > t > a
 gpara :: (Recursive t, Corecursive t, Comonad w) => (forall b. Base t (w b) > w (Base t b)) > (Base t (EnvT t w a) > a) > t > a
 ghisto :: (Recursive t, Comonad w) => (forall b. Base t (w b) > w (Base t b)) > (Base t (CofreeT (Base t) w a) > a) > t > a
 gzygo :: (Recursive 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
 gunfold :: (Corecursive t, Monad m) => (forall b. m (Base t b) > Base t (m b)) > (a > Base t (m a)) > a > t
 gana :: (Corecursive t, Monad m) => (forall b. m (Base t b) > Base t (m b)) > (a > Base t (m a)) > a > t
 gapo :: Corecursive t => (b > Base t b) > (a > Base t (Either b a)) > a > t
 gfutu :: (Corecursive t, Functor m, Monad m) => (forall b. m (Base t b) > Base t (m b)) > (a > Base t (FreeT (Base t) m a)) > a > t
 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
 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
 gchrono :: (Functor f, Functor w, Functor m, Comonad w, Monad m) => (forall c. f (w c) > w (f c)) > (forall c. m (f c) > f (m c)) > (f (CofreeT f w b) > b) > (a > f (FreeT f m a)) > a > b
 gprepro :: (Recursive t, Corecursive 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
 gpostpro :: (Corecursive t, Recursive 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
 distCata :: Functor f => f (Identity a) > Identity (f a)
 distPara :: Corecursive t => Base t (t, a) > (t, Base t a)
 distParaT :: (Corecursive 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)
 distHisto :: Functor f => f (Cofree f a) > Cofree f (f a)
 distGHisto :: (Functor f, Functor h) => (forall b. f (h b) > h (f b)) > f (CofreeT f h a) > CofreeT f h (f a)
 distZygo :: Functor f => (f b > b) > f (b, a) > (b, f a)
 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)
 distAna :: Functor f => Identity (f a) > f (Identity a)
 distApo :: Recursive t => Either t (Base t a) > Base t (Either t a)
 distGApo :: Functor f => (b > f b) > Either b (f a) > f (Either b a)
 distGApoT :: (Functor f, Functor m) => (b > f b) > (forall c. m (f c) > f (m c)) > ExceptT b m (f a) > f (ExceptT b m a)
 distFutu :: Functor f => Free f (f a) > f (Free f a)
 distGFutu :: (Functor f, Functor h) => (forall b. h (f b) > f (h b)) > FreeT f h (f a) > f (FreeT f h a)
 zygoHistoPrepro :: (Corecursive t, Recursive t) => (Base t b > b) > (forall c. Base t c > Base t c) > (Base t (EnvT b (Cofree (Base t)) a) > a) > t > a
Base functors
type family Base t :: * > * Source #
Obtain the base functor for a recursive datatype.
The core idea of this library is that instead of writing recursive functions on a recursive datatype, we prefer to write nonrecursive functions on a related, nonrecursive datatype we call the "base functor".
For example, [a]
is a recursive type, and its corresponding base functor is
:ListF
a
dataListF
a b =Nil
Cons
a b type instanceBase
[a] =ListF
a
The relationship between those two types is that if we replace b
with
, we obtain a type which is isomorphic to ListF
a[a]
.
Instances
type Base Natural Source #  
Defined in Data.Functor.Foldable  
type Base [a] Source #  
Defined in Data.Functor.Foldable  
type Base (Maybe a) Source #  Example boring stub for nonrecursive data types 
type Base (NonEmpty a) Source #  
Defined in Data.Functor.Foldable  
type Base (Tree a) Source #  
Defined in Data.Functor.Foldable  
type Base (Fix f) Source #  
Defined in Data.Functor.Foldable type Base (Fix f) = f  
type Base (Mu f) Source #  
Defined in Data.Functor.Foldable type Base (Mu f) = f  
type Base (Nu f) Source #  
Defined in Data.Functor.Foldable type Base (Nu f) = f  
type Base (Either a b) Source #  Example boring stub for nonrecursive data types 
type Base (Cofree f a) Source #  Cofree comonads are Recursive/Corecursive 
Defined in Data.Functor.Foldable type Base (Cofree f a) = CofreeF f a  
type Base (Free f a) Source #  Free monads are Recursive/Corecursive 
Defined in Data.Functor.Foldable type Base (Free f a) = FreeF f a  
type Base (F f a) Source #  Church encoded free monads are Recursive/Corecursive, in the same way that

Defined in Data.Functor.Foldable type Base (F f a) = FreeF f a  
type Base (CofreeT f w a) Source #  Cofree tranformations of comonads are Recursive/Corecusive 
Defined in Data.Functor.Foldable  
type Base (FreeT f m a) Source #  Free transformations of monads are Recursive/Corecursive 
Defined in Data.Functor.Foldable 
Base functor of []
.
Instances
Type classes
class Functor (Base t) => Recursive t where Source #
A recursive datatype which can be unrolled one recursion layer at a time.
For example, a value of type [a]
can be unrolled into a
.
Ifthat unrolled value is a ListF
a [a]Cons
, it contains another [a]
which can be
unrolled as well, and so on.
Typically, Recursive
types also have a Corecursive
instance, in which
case project
and embed
are inverses.
Nothing
Instances
Recursive Natural Source #  
Defined in Data.Functor.Foldable project :: Natural > Base Natural Natural Source # cata :: (Base Natural a > a) > Natural > a Source # para :: (Base Natural (Natural, a) > a) > Natural > a Source # gpara :: (Corecursive Natural, Comonad w) => (forall b. Base Natural (w b) > w (Base Natural b)) > (Base Natural (EnvT Natural w a) > a) > Natural > a Source # prepro :: Corecursive Natural => (forall b. Base Natural b > Base Natural b) > (Base Natural a > a) > Natural > a Source # gprepro :: (Corecursive Natural, Comonad w) => (forall b. Base Natural (w b) > w (Base Natural b)) > (forall c. Base Natural c > Base Natural c) > (Base Natural (w a) > a) > Natural > a Source #  
Recursive [a] Source #  
Defined in Data.Functor.Foldable project :: [a] > Base [a] [a] Source # cata :: (Base [a] a0 > a0) > [a] > a0 Source # para :: (Base [a] ([a], a0) > a0) > [a] > a0 Source # gpara :: (Corecursive [a], Comonad w) => (forall b. Base [a] (w b) > w (Base [a] b)) > (Base [a] (EnvT [a] w a0) > a0) > [a] > a0 Source # prepro :: Corecursive [a] => (forall b. Base [a] b > Base [a] b) > (Base [a] a0 > a0) > [a] > a0 Source # gprepro :: (Corecursive [a], Comonad w) => (forall b. Base [a] (w b) > w (Base [a] b)) > (forall c. Base [a] c > Base [a] c) > (Base [a] (w a0) > a0) > [a] > a0 Source #  
Recursive (Maybe a) Source #  
Defined in Data.Functor.Foldable project :: Maybe a > Base (Maybe a) (Maybe a) Source # cata :: (Base (Maybe a) a0 > a0) > Maybe a > a0 Source # para :: (Base (Maybe a) (Maybe a, a0) > a0) > Maybe a > a0 Source # gpara :: (Corecursive (Maybe a), Comonad w) => (forall b. Base (Maybe a) (w b) > w (Base (Maybe a) b)) > (Base (Maybe a) (EnvT (Maybe a) w a0) > a0) > Maybe a > a0 Source # prepro :: Corecursive (Maybe a) => (forall b. Base (Maybe a) b > Base (Maybe a) b) > (Base (Maybe a) a0 > a0) > Maybe a > a0 Source # gprepro :: (Corecursive (Maybe a), Comonad w) => (forall b. Base (Maybe a) (w b) > w (Base (Maybe a) b)) > (forall c. Base (Maybe a) c > Base (Maybe a) c) > (Base (Maybe a) (w a0) > a0) > Maybe a > a0 Source #  
Recursive (NonEmpty a) Source #  
Defined in Data.Functor.Foldable project :: NonEmpty a > Base (NonEmpty a) (NonEmpty a) Source # cata :: (Base (NonEmpty a) a0 > a0) > NonEmpty a > a0 Source # para :: (Base (NonEmpty a) (NonEmpty a, a0) > a0) > NonEmpty a > a0 Source # gpara :: (Corecursive (NonEmpty a), Comonad w) => (forall b. Base (NonEmpty a) (w b) > w (Base (NonEmpty a) b)) > (Base (NonEmpty a) (EnvT (NonEmpty a) w a0) > a0) > NonEmpty a > a0 Source # prepro :: Corecursive (NonEmpty a) => (forall b. Base (NonEmpty a) b > Base (NonEmpty a) b) > (Base (NonEmpty a) a0 > a0) > NonEmpty a > a0 Source # gprepro :: (Corecursive (NonEmpty a), Comonad w) => (forall b. Base (NonEmpty a) (w b) > w (Base (NonEmpty a) b)) > (forall c. Base (NonEmpty a) c > Base (NonEmpty a) c) > (Base (NonEmpty a) (w a0) > a0) > NonEmpty a > a0 Source #  
Recursive (Tree a) Source #  
Defined in Data.Functor.Foldable project :: Tree a > Base (Tree a) (Tree a) Source # cata :: (Base (Tree a) a0 > a0) > Tree a > a0 Source # para :: (Base (Tree a) (Tree a, a0) > a0) > Tree a > a0 Source # gpara :: (Corecursive (Tree a), Comonad w) => (forall b. Base (Tree a) (w b) > w (Base (Tree a) b)) > (Base (Tree a) (EnvT (Tree a) w a0) > a0) > Tree a > a0 Source # prepro :: Corecursive (Tree a) => (forall b. Base (Tree a) b > Base (Tree a) b) > (Base (Tree a) a0 > a0) > Tree a > a0 Source # gprepro :: (Corecursive (Tree a), Comonad w) => (forall b. Base (Tree a) (w b) > w (Base (Tree a) b)) > (forall c. Base (Tree a) c > Base (Tree a) c) > (Base (Tree a) (w a0) > a0) > Tree a > a0 Source #  
Functor f => Recursive (Fix f) Source #  
Defined in Data.Functor.Foldable project :: Fix f > Base (Fix f) (Fix f) Source # cata :: (Base (Fix f) a > a) > Fix f > a Source # para :: (Base (Fix f) (Fix f, a) > a) > Fix f > a Source # gpara :: (Corecursive (Fix f), Comonad w) => (forall b. Base (Fix f) (w b) > w (Base (Fix f) b)) > (Base (Fix f) (EnvT (Fix f) w a) > a) > Fix f > a Source # prepro :: Corecursive (Fix f) => (forall b. Base (Fix f) b > Base (Fix f) b) > (Base (Fix f) a > a) > Fix f > a Source # gprepro :: (Corecursive (Fix f), Comonad w) => (forall b. Base (Fix f) (w b) > w (Base (Fix f) b)) > (forall c. Base (Fix f) c > Base (Fix f) c) > (Base (Fix f) (w a) > a) > Fix f > a Source #  
Functor f => Recursive (Mu f) Source #  
Defined in Data.Functor.Foldable project :: Mu f > Base (Mu f) (Mu f) Source # cata :: (Base (Mu f) a > a) > Mu f > a Source # para :: (Base (Mu f) (Mu f, a) > a) > Mu f > a Source # gpara :: (Corecursive (Mu f), Comonad w) => (forall b. Base (Mu f) (w b) > w (Base (Mu f) b)) > (Base (Mu f) (EnvT (Mu f) w a) > a) > Mu f > a Source # prepro :: Corecursive (Mu f) => (forall b. Base (Mu f) b > Base (Mu f) b) > (Base (Mu f) a > a) > Mu f > a Source # gprepro :: (Corecursive (Mu f), Comonad w) => (forall b. Base (Mu f) (w b) > w (Base (Mu f) b)) > (forall c. Base (Mu f) c > Base (Mu f) c) > (Base (Mu f) (w a) > a) > Mu f > a Source #  
Functor f => Recursive (Nu f) Source #  
Defined in Data.Functor.Foldable project :: Nu f > Base (Nu f) (Nu f) Source # cata :: (Base (Nu f) a > a) > Nu f > a Source # para :: (Base (Nu f) (Nu f, a) > a) > Nu f > a Source # gpara :: (Corecursive (Nu f), Comonad w) => (forall b. Base (Nu f) (w b) > w (Base (Nu f) b)) > (Base (Nu f) (EnvT (Nu f) w a) > a) > Nu f > a Source # prepro :: Corecursive (Nu f) => (forall b. Base (Nu f) b > Base (Nu f) b) > (Base (Nu f) a > a) > Nu f > a Source # gprepro :: (Corecursive (Nu f), Comonad w) => (forall b. Base (Nu f) (w b) > w (Base (Nu f) b)) > (forall c. Base (Nu f) c > Base (Nu f) c) > (Base (Nu f) (w a) > a) > Nu f > a Source #  
Recursive (Either a b) Source #  
Defined in Data.Functor.Foldable project :: Either a b > Base (Either a b) (Either a b) Source # cata :: (Base (Either a b) a0 > a0) > Either a b > a0 Source # para :: (Base (Either a b) (Either a b, a0) > a0) > Either a b > a0 Source # gpara :: (Corecursive (Either a b), Comonad w) => (forall b0. Base (Either a b) (w b0) > w (Base (Either a b) b0)) > (Base (Either a b) (EnvT (Either a b) w a0) > a0) > Either a b > a0 Source # prepro :: Corecursive (Either a b) => (forall b0. Base (Either a b) b0 > Base (Either a b) b0) > (Base (Either a b) a0 > a0) > Either a b > a0 Source # gprepro :: (Corecursive (Either a b), Comonad w) => (forall b0. Base (Either a b) (w b0) > w (Base (Either a b) b0)) > (forall c. Base (Either a b) c > Base (Either a b) c) > (Base (Either a b) (w a0) > a0) > Either a b > a0 Source #  
Functor f => Recursive (Cofree f a) Source #  
Defined in Data.Functor.Foldable project :: Cofree f a > Base (Cofree f a) (Cofree f a) Source # cata :: (Base (Cofree f a) a0 > a0) > Cofree f a > a0 Source # para :: (Base (Cofree f a) (Cofree f a, a0) > a0) > Cofree f a > a0 Source # gpara :: (Corecursive (Cofree f a), Comonad w) => (forall b. Base (Cofree f a) (w b) > w (Base (Cofree f a) b)) > (Base (Cofree f a) (EnvT (Cofree f a) w a0) > a0) > Cofree f a > a0 Source # prepro :: Corecursive (Cofree f a) => (forall b. Base (Cofree f a) b > Base (Cofree f a) b) > (Base (Cofree f a) a0 > a0) > Cofree f a > a0 Source # gprepro :: (Corecursive (Cofree f a), Comonad w) => (forall b. Base (Cofree f a) (w b) > w (Base (Cofree f a) b)) > (forall c. Base (Cofree f a) c > Base (Cofree f a) c) > (Base (Cofree f a) (w a0) > a0) > Cofree f a > a0 Source #  
Functor f => Recursive (Free f a) Source #  
Defined in Data.Functor.Foldable project :: Free f a > Base (Free f a) (Free f a) Source # cata :: (Base (Free f a) a0 > a0) > Free f a > a0 Source # para :: (Base (Free f a) (Free f a, a0) > a0) > Free f a > a0 Source # gpara :: (Corecursive (Free f a), Comonad w) => (forall b. Base (Free f a) (w b) > w (Base (Free f a) b)) > (Base (Free f a) (EnvT (Free f a) w a0) > a0) > Free f a > a0 Source # prepro :: Corecursive (Free f a) => (forall b. Base (Free f a) b > Base (Free f a) b) > (Base (Free f a) a0 > a0) > Free f a > a0 Source # gprepro :: (Corecursive (Free f a), Comonad w) => (forall b. Base (Free f a) (w b) > w (Base (Free f a) b)) > (forall c. Base (Free f a) c > Base (Free f a) c) > (Base (Free f a) (w a0) > a0) > Free f a > a0 Source #  
Functor f => Recursive (F f a) Source #  
Defined in Data.Functor.Foldable project :: F f a > Base (F f a) (F f a) Source # cata :: (Base (F f a) a0 > a0) > F f a > a0 Source # para :: (Base (F f a) (F f a, a0) > a0) > F f a > a0 Source # gpara :: (Corecursive (F f a), Comonad w) => (forall b. Base (F f a) (w b) > w (Base (F f a) b)) > (Base (F f a) (EnvT (F f a) w a0) > a0) > F f a > a0 Source # prepro :: Corecursive (F f a) => (forall b. Base (F f a) b > Base (F f a) b) > (Base (F f a) a0 > a0) > F f a > a0 Source # gprepro :: (Corecursive (F f a), Comonad w) => (forall b. Base (F f a) (w b) > w (Base (F f a) b)) > (forall c. Base (F f a) c > Base (F f a) c) > (Base (F f a) (w a0) > a0) > F f a > a0 Source #  
(Functor w, Functor f) => Recursive (CofreeT f w a) Source #  
Defined in Data.Functor.Foldable project :: CofreeT f w a > Base (CofreeT f w a) (CofreeT f w a) Source # cata :: (Base (CofreeT f w a) a0 > a0) > CofreeT f w a > a0 Source # para :: (Base (CofreeT f w a) (CofreeT f w a, a0) > a0) > CofreeT f w a > a0 Source # gpara :: (Corecursive (CofreeT f w a), Comonad w0) => (forall b. Base (CofreeT f w a) (w0 b) > w0 (Base (CofreeT f w a) b)) > (Base (CofreeT f w a) (EnvT (CofreeT f w a) w0 a0) > a0) > CofreeT f w a > a0 Source # prepro :: Corecursive (CofreeT f w a) => (forall b. Base (CofreeT f w a) b > Base (CofreeT f w a) b) > (Base (CofreeT f w a) a0 > a0) > CofreeT f w a > a0 Source # gprepro :: (Corecursive (CofreeT f w a), Comonad w0) => (forall b. Base (CofreeT f w a) (w0 b) > w0 (Base (CofreeT f w a) b)) > (forall c. Base (CofreeT f w a) c > Base (CofreeT f w a) c) > (Base (CofreeT f w a) (w0 a0) > a0) > CofreeT f w a > a0 Source #  
(Functor m, Functor f) => Recursive (FreeT f m a) Source #  
Defined in Data.Functor.Foldable project :: FreeT f m a > Base (FreeT f m a) (FreeT f m a) Source # cata :: (Base (FreeT f m a) a0 > a0) > FreeT f m a > a0 Source # para :: (Base (FreeT f m a) (FreeT f m a, a0) > a0) > FreeT f m a > a0 Source # gpara :: (Corecursive (FreeT f m a), Comonad w) => (forall b. Base (FreeT f m a) (w b) > w (Base (FreeT f m a) b)) > (Base (FreeT f m a) (EnvT (FreeT f m a) w a0) > a0) > FreeT f m a > a0 Source # prepro :: Corecursive (FreeT f m a) => (forall b. Base (FreeT f m a) b > Base (FreeT f m a) b) > (Base (FreeT f m a) a0 > a0) > FreeT f m a > a0 Source # gprepro :: (Corecursive (FreeT f m a), Comonad w) => (forall b. Base (FreeT f m a) (w b) > w (Base (FreeT f m a) b)) > (forall c. Base (FreeT f m a) c > Base (FreeT f m a) c) > (Base (FreeT f m a) (w a0) > a0) > FreeT f m a > a0 Source # 
class Functor (Base t) => Corecursive t where Source #
A recursive datatype which can be rolled up one recursion layer at a time.
For example, a value of type
can be rolled up into a ListF
a [a][a]
.
This [a]
can then be used in a Cons
to construct another
,
which can be rolled up as well, and so on.ListF
a [a]
Typically, Corecursive
types also have a Recursive
instance, in which
case embed
and project
are inverses.
Nothing
Instances
Corecursive Natural Source #  
Defined in Data.Functor.Foldable embed :: Base Natural Natural > Natural Source # ana :: (a > Base Natural a) > a > Natural Source # apo :: (a > Base Natural (Either Natural a)) > a > Natural Source # postpro :: Recursive Natural => (forall b. Base Natural b > Base Natural b) > (a > Base Natural a) > a > Natural Source # gpostpro :: (Recursive Natural, Monad m) => (forall b. m (Base Natural b) > Base Natural (m b)) > (forall c. Base Natural c > Base Natural c) > (a > Base Natural (m a)) > a > Natural Source #  
Corecursive [a] Source #  
Defined in Data.Functor.Foldable embed :: Base [a] [a] > [a] Source # ana :: (a0 > Base [a] a0) > a0 > [a] Source # apo :: (a0 > Base [a] (Either [a] a0)) > a0 > [a] Source # postpro :: Recursive [a] => (forall b. Base [a] b > Base [a] b) > (a0 > Base [a] a0) > a0 > [a] Source # gpostpro :: (Recursive [a], Monad m) => (forall b. m (Base [a] b) > Base [a] (m b)) > (forall c. Base [a] c > Base [a] c) > (a0 > Base [a] (m a0)) > a0 > [a] Source #  
Corecursive (Maybe a) Source #  
Defined in Data.Functor.Foldable embed :: Base (Maybe a) (Maybe a) > Maybe a Source # ana :: (a0 > Base (Maybe a) a0) > a0 > Maybe a Source # apo :: (a0 > Base (Maybe a) (Either (Maybe a) a0)) > a0 > Maybe a Source # postpro :: Recursive (Maybe a) => (forall b. Base (Maybe a) b > Base (Maybe a) b) > (a0 > Base (Maybe a) a0) > a0 > Maybe a Source # gpostpro :: (Recursive (Maybe a), Monad m) => (forall b. m (Base (Maybe a) b) > Base (Maybe a) (m b)) > (forall c. Base (Maybe a) c > Base (Maybe a) c) > (a0 > Base (Maybe a) (m a0)) > a0 > Maybe a Source #  
Corecursive (NonEmpty a) Source #  
Defined in Data.Functor.Foldable embed :: Base (NonEmpty a) (NonEmpty a) > NonEmpty a Source # ana :: (a0 > Base (NonEmpty a) a0) > a0 > NonEmpty a Source # apo :: (a0 > Base (NonEmpty a) (Either (NonEmpty a) a0)) > a0 > NonEmpty a Source # postpro :: Recursive (NonEmpty a) => (forall b. Base (NonEmpty a) b > Base (NonEmpty a) b) > (a0 > Base (NonEmpty a) a0) > a0 > NonEmpty a Source # gpostpro :: (Recursive (NonEmpty a), Monad m) => (forall b. m (Base (NonEmpty a) b) > Base (NonEmpty a) (m b)) > (forall c. Base (NonEmpty a) c > Base (NonEmpty a) c) > (a0 > Base (NonEmpty a) (m a0)) > a0 > NonEmpty a Source #  
Corecursive (Tree a) Source #  
Defined in Data.Functor.Foldable embed :: Base (Tree a) (Tree a) > Tree a Source # ana :: (a0 > Base (Tree a) a0) > a0 > Tree a Source # apo :: (a0 > Base (Tree a) (Either (Tree a) a0)) > a0 > Tree a Source # postpro :: Recursive (Tree a) => (forall b. Base (Tree a) b > Base (Tree a) b) > (a0 > Base (Tree a) a0) > a0 > Tree a Source # gpostpro :: (Recursive (Tree a), Monad m) => (forall b. m (Base (Tree a) b) > Base (Tree a) (m b)) > (forall c. Base (Tree a) c > Base (Tree a) c) > (a0 > Base (Tree a) (m a0)) > a0 > Tree a Source #  
Functor f => Corecursive (Fix f) Source #  
Defined in Data.Functor.Foldable embed :: Base (Fix f) (Fix f) > Fix f Source # ana :: (a > Base (Fix f) a) > a > Fix f Source # apo :: (a > Base (Fix f) (Either (Fix f) a)) > a > Fix f Source # postpro :: Recursive (Fix f) => (forall b. Base (Fix f) b > Base (Fix f) b) > (a > Base (Fix f) a) > a > Fix f Source # gpostpro :: (Recursive (Fix f), Monad m) => (forall b. m (Base (Fix f) b) > Base (Fix f) (m b)) > (forall c. Base (Fix f) c > Base (Fix f) c) > (a > Base (Fix f) (m a)) > a > Fix f Source #  
Functor f => Corecursive (Mu f) Source #  
Defined in Data.Functor.Foldable embed :: Base (Mu f) (Mu f) > Mu f Source # ana :: (a > Base (Mu f) a) > a > Mu f Source # apo :: (a > Base (Mu f) (Either (Mu f) a)) > a > Mu f Source # postpro :: Recursive (Mu f) => (forall b. Base (Mu f) b > Base (Mu f) b) > (a > Base (Mu f) a) > a > Mu f Source # gpostpro :: (Recursive (Mu f), Monad m) => (forall b. m (Base (Mu f) b) > Base (Mu f) (m b)) > (forall c. Base (Mu f) c > Base (Mu f) c) > (a > Base (Mu f) (m a)) > a > Mu f Source #  
Functor f => Corecursive (Nu f) Source #  
Defined in Data.Functor.Foldable embed :: Base (Nu f) (Nu f) > Nu f Source # ana :: (a > Base (Nu f) a) > a > Nu f Source # apo :: (a > Base (Nu f) (Either (Nu f) a)) > a > Nu f Source # postpro :: Recursive (Nu f) => (forall b. Base (Nu f) b > Base (Nu f) b) > (a > Base (Nu f) a) > a > Nu f Source # gpostpro :: (Recursive (Nu f), Monad m) => (forall b. m (Base (Nu f) b) > Base (Nu f) (m b)) > (forall c. Base (Nu f) c > Base (Nu f) c) > (a > Base (Nu f) (m a)) > a > Nu f Source #  
Corecursive (Either a b) Source #  
Defined in Data.Functor.Foldable embed :: Base (Either a b) (Either a b) > Either a b Source # ana :: (a0 > Base (Either a b) a0) > a0 > Either a b Source # apo :: (a0 > Base (Either a b) (Either (Either a b) a0)) > a0 > Either a b Source # postpro :: Recursive (Either a b) => (forall b0. Base (Either a b) b0 > Base (Either a b) b0) > (a0 > Base (Either a b) a0) > a0 > Either a b Source # gpostpro :: (Recursive (Either a b), Monad m) => (forall b0. m (Base (Either a b) b0) > Base (Either a b) (m b0)) > (forall c. Base (Either a b) c > Base (Either a b) c) > (a0 > Base (Either a b) (m a0)) > a0 > Either a b Source #  
Functor f => Corecursive (Cofree f a) Source #  
Defined in Data.Functor.Foldable embed :: Base (Cofree f a) (Cofree f a) > Cofree f a Source # ana :: (a0 > Base (Cofree f a) a0) > a0 > Cofree f a Source # apo :: (a0 > Base (Cofree f a) (Either (Cofree f a) a0)) > a0 > Cofree f a Source # postpro :: Recursive (Cofree f a) => (forall b. Base (Cofree f a) b > Base (Cofree f a) b) > (a0 > Base (Cofree f a) a0) > a0 > Cofree f a Source # gpostpro :: (Recursive (Cofree f a), Monad m) => (forall b. m (Base (Cofree f a) b) > Base (Cofree f a) (m b)) > (forall c. Base (Cofree f a) c > Base (Cofree f a) c) > (a0 > Base (Cofree f a) (m a0)) > a0 > Cofree f a Source #  
Functor f => Corecursive (Free f a) Source #  It may be better to work with the instance for 
Defined in Data.Functor.Foldable embed :: Base (Free f a) (Free f a) > Free f a Source # ana :: (a0 > Base (Free f a) a0) > a0 > Free f a Source # apo :: (a0 > Base (Free f a) (Either (Free f a) a0)) > a0 > Free f a Source # postpro :: Recursive (Free f a) => (forall b. Base (Free f a) b > Base (Free f a) b) > (a0 > Base (Free f a) a0) > a0 > Free f a Source # gpostpro :: (Recursive (Free f a), Monad m) => (forall b. m (Base (Free f a) b) > Base (Free f a) (m b)) > (forall c. Base (Free f a) c > Base (Free f a) c) > (a0 > Base (Free f a) (m a0)) > a0 > Free f a Source #  
Functor f => Corecursive (F f a) Source #  
Defined in Data.Functor.Foldable embed :: Base (F f a) (F f a) > F f a Source # ana :: (a0 > Base (F f a) a0) > a0 > F f a Source # apo :: (a0 > Base (F f a) (Either (F f a) a0)) > a0 > F f a Source # postpro :: Recursive (F f a) => (forall b. Base (F f a) b > Base (F f a) b) > (a0 > Base (F f a) a0) > a0 > F f a Source # gpostpro :: (Recursive (F f a), Monad m) => (forall b. m (Base (F f a) b) > Base (F f a) (m b)) > (forall c. Base (F f a) c > Base (F f a) c) > (a0 > Base (F f a) (m a0)) > a0 > F f a Source #  
(Functor w, Functor f) => Corecursive (CofreeT f w a) Source #  
Defined in Data.Functor.Foldable embed :: Base (CofreeT f w a) (CofreeT f w a) > CofreeT f w a Source # ana :: (a0 > Base (CofreeT f w a) a0) > a0 > CofreeT f w a Source # apo :: (a0 > Base (CofreeT f w a) (Either (CofreeT f w a) a0)) > a0 > CofreeT f w a Source # postpro :: Recursive (CofreeT f w a) => (forall b. Base (CofreeT f w a) b > Base (CofreeT f w a) b) > (a0 > Base (CofreeT f w a) a0) > a0 > CofreeT f w a Source # gpostpro :: (Recursive (CofreeT f w a), Monad m) => (forall b. m (Base (CofreeT f w a) b) > Base (CofreeT f w a) (m b)) > (forall c. Base (CofreeT f w a) c > Base (CofreeT f w a) c) > (a0 > Base (CofreeT f w a) (m a0)) > a0 > CofreeT f w a Source #  
(Functor m, Functor f) => Corecursive (FreeT f m a) Source #  
Defined in Data.Functor.Foldable embed :: Base (FreeT f m a) (FreeT f m a) > FreeT f m a Source # ana :: (a0 > Base (FreeT f m a) a0) > a0 > FreeT f m a Source # apo :: (a0 > Base (FreeT f m a) (Either (FreeT f m a) a0)) > a0 > FreeT f m a Source # postpro :: Recursive (FreeT f m a) => (forall b. Base (FreeT f m a) b > Base (FreeT f m a) b) > (a0 > Base (FreeT f m a) a0) > a0 > FreeT f m a Source # gpostpro :: (Recursive (FreeT f m a), Monad m0) => (forall b. m0 (Base (FreeT f m a) b) > Base (FreeT f m a) (m0 b)) > (forall c. Base (FreeT f m a) c > Base (FreeT f m a) c) > (a0 > Base (FreeT f m a) (m0 a0)) > a0 > FreeT f m a Source # 
Folding functions
Folding functions allow you to reduce a recursive structure down to a value. The value can be a simple type such as Int
or String
, or it can also be a recursive structure. Each of the functions below will be accompanied by an example which folds the following Tree Int
down to some String
.
>>>
putStr $ drawTree $ fmap show myTree
0  + 1  + 2  ` 3  ` 31  ` 311  + 3111  ` 3112
fold :: Recursive t => (Base t a > a) > t > a Source #
Folds a recursive type down to a value, one layer at a time.
>>>
:{
let mySum :: [Int] > Int mySum = fold $ \case Nil > 0 Cons x sumXs > x + sumXs :}
>>>
mySum [10,11,12]
33
In our running example, one layer consists of an Int
and a list of recursive positions. In Tree Int
, those recursive positions contain subtrees of type Tree Int
. Since we are working one layer at a time, the Base t a > a
function is not given a Tree Int
, but a TreeF Int String
. That is, each recursive position contains the String
resulting from recursively folding the corresponding subtree.
>>>
:{
let pprint1 :: Tree Int > String pprint1 = fold $ \case NodeF i [] > show i NodeF i ss > show i ++ ": [" ++ intercalate ", " ss ++ "]" :}
>>>
putStrLn $ pprint1 myTree
0: [1, 2, 3: [31: [311: [3111, 3112]]]]
More generally, the t
argument is the recursive value, the a
is the final result, and the Base t a > a
function explains how to reduce a single layer full of recursive results down to a result.
cata :: Recursive t => (Base t a > a) > t > a Source #
An alias for fold
.
fold
is by far the most common recursionscheme, because working one layer at a time is the most common strategy for writing a recursive function. But there are also other, rarer strategies. Researchers have given names to the most common strategies, and their name for fold
is "catamorphism". They also give its Base t a > a
argument a special name, "(Base t
)algebra". More generally, a function of the form f a > a
is called an "falgebra".
The names might seem intimidating at first, but using the standard nomenclature has benefits. If you program with others, it can be useful to have a shared vocabulary to refer to those recursion patterns. For example, you can discuss which type of recursion is the most appropriate for the problem at hand. Names can also help to structure your thoughts while writing recursive functions.
The rest of this module lists a few of the other recursionschemes which are common enough to have a name. In this section, we restrict our attention to those which fold a recursive structure down to a value. In the examples all functions will be of type Tree Int > String
.
cataA :: Recursive t => (Base t (f a) > f a) > t > f a Source #
A specialization of cata
for effectful folds.
cataA
is the same as cata
, but with a more specialized type. The only
reason it exists is to make it easier to discover how to use this library
with effects.
For our running example, let's improve the output format of our
prettyprinter by using indentation. To do so, we will need to keep track of
the current indentation level. We will do so using a Reader Int
effect.
Our recursive positions will thus contain Reader Int String
actions, not
String
s. This means we need to run those actions in order to get the
results.
>>>
:{
let pprint2 :: Tree Int > String pprint2 = flip runReader 0 . cataA go where go :: TreeF Int (Reader Int String) > Reader Int String go (NodeF i rss) = do  rss :: [Reader Int String]  ss :: [String] ss < local (+ 2) $ sequence rss indent < ask let s = replicate indent ' ' ++ "* " ++ show i pure $ intercalate "\n" (s : ss) :}
>>>
putStrLn $ pprint2 myTree
* 0 * 1 * 2 * 3 * 31 * 311 * 3111 * 3112
The fact that the recursive positions contain Reader
actions instead of
String
s gives us some flexibility. Here, we are able to increase the
indentation by running those actions inside a local
block. More generally,
we can control the order of their sideeffects, interleave them with other
effects, etc.
A similar technique is to specialize cata
so that the result is a
function. This makes it possible for data to flow down in addition to up.
In this modified version of our running example, the indentation level flows
down from the root to the leaves, while the resulting strings flow up from
the leaves to the root.
>>>
:{
let pprint3 :: Tree Int > String pprint3 t = cataA go t 0 where go :: TreeF Int (Int > String) > Int > String go (NodeF i fs) indent  fs :: [Int > String] = let indent' = indent + 2 ss = map (\f > f indent') fs s = replicate indent ' ' ++ "* " ++ show i in intercalate "\n" (s : ss) :}
>>>
putStrLn $ pprint3 myTree
* 0 * 1 * 2 * 3 * 31 * 311 * 3111 * 3112
para :: Recursive t => (Base t (t, a) > a) > t > a Source #
A variant of cata
in which recursive positions also include the
original subtree, in addition to the result of folding that subtree.
For our running example, let's add a number to each node indicating how many children are below it. To do so, we will need to count those nodes from the original subtree.
>>>
:{
let pprint4 :: Tree Int > String pprint4 = flip runReader 0 . para go where go :: TreeF Int (Tree Int, Reader Int String) > Reader Int String go (NodeF i trss) = do  trss :: [(Tree Int, Reader Int String)]  ts :: [Tree Int]  rss :: [Reader Int String]  ss :: [String] let (ts, rss) = unzip trss let count = sum $ fmap length ts ss < local (+ 2) $ sequence rss indent < ask let s = replicate indent ' ' ++ "* " ++ show i ++ " (" ++ show count ++ ")" pure $ intercalate "\n" (s : ss) :}
>>>
putStrLn $ pprint4 myTree
* 0 (7) * 1 (0) * 2 (0) * 3 (4) * 31 (3) * 311 (2) * 3111 (0) * 3112 (0)
One common use for para
is to construct a new tree which reuses most of
the subtrees from the original. In the following example, we insert a new
node under the leftmost leaf. This requires allocating new nodes along a
path from the root to that leaf, while keeping every other subtree
untouched.
>>>
:{
let insertLeftmost :: Int > Tree Int > Tree Int insertLeftmost new = para go where go :: TreeF Int (Tree Int, Tree Int) > Tree Int go (NodeF i []) = Node i [Node new []] go (NodeF i ((_orig, recur) : tts))  tts :: [(Tree Int, Tree Int)] = let (origs, _recurs) = unzip tts in Node i (recur : origs) :}
>>>
putStrLn $ pprint4 $ insertLeftmost 999 myTree
* 0 (8) * 1 (1) * 999 (0) * 2 (0) * 3 (4) * 31 (3) * 311 (2) * 3111 (0) * 3112 (0)
histo :: Recursive t => (Base t (Cofree (Base t) a) > a) > t > a Source #
A variant of cata
which includes the results of all the
descendents, not just the direct children.
Like para
, a subtree is provided for each recursive position. Each
node in that subtree is annotated with the result for that
descendent. The Cofree
type is used to add those annotations.
For our running example, let's recreate GitHub's directory compression
algorithm. Notice that in the repository for this
package, GitHub
displays src/Data/Functor
, not src
:
GitHub does this because src
only contains one entry: Data
. Similarly,
Data
only contains one entry: Functor
. Functor
contains several
entries, so the compression stops there. This helps users get to the
interesting folders more quickly.
Before we use histo
, we need to define a helper function rollup
.
It collects nodes until it reaches a node which doesn't have exactly one
child. It also returns the labels of that node's children.
>>>
:{
let rollup :: [Cofree (TreeF node) label] > ([node], [label]) rollup [_ :< NodeF node cofrees] = let (nodes, label) = rollup cofrees in (node : nodes, label) rollup cofrees = ([], fmap extract cofrees) :}
>>>
let foobar xs = 1 :< NodeF "foo" [2 :< NodeF "bar" xs]
>>>
rollup [foobar []]
(["foo","bar"],[])>>>
rollup [foobar [3 :< NodeF "baz" [], 4 :< NodeF "quux" []]]
(["foo","bar"],[3,4])
The value foobar []
can be interpreted as the tree NodeF "foo"
[NodeF "bar" []]
, plus two annotations. The "foo"
node is annotated
with 1
, while the "bar"
node is annotated with 2
. When we call
histo
below, those annotations are recursive results of type Int >
String
.
>>>
:{
let pprint5 :: Tree Int > String pprint5 t = histo go t 0 where go :: TreeF Int (Cofree (TreeF Int) (Int > String)) > Int > String go (NodeF node cofrees) indent  cofrees :: [Cofree (TreeF Int) (Int > String)]  fs :: [Int > String] = let indent' = indent + 2 (nodes, fs) = rollup cofrees ss = map (\f > f indent') fs s = replicate indent ' ' ++ "* " ++ intercalate " / " (fmap show (node : nodes)) in intercalate "\n" (s : ss) :}
>>>
putStrLn $ pprint5 myTree
* 0 * 1 * 2 * 3 / 31 / 311 * 3111 * 3112
One common use for histo
is to cache the value computed for smaller
subtrees. In the Fibonacci example below, the recursive type is Natural
,
which is isomorphic to [()]
. Our annotated subtree is thus isomorphic to
a list of annotations. In our case, each annotation is the result which was
computed for a smaller number. We thus have access to a list which caches
all the Fibonacci numbers we have computed so far.
>>>
:{
let fib :: Natural > Integer fib = histo go where go :: Maybe (Cofree Maybe Integer) > Integer go Nothing = 1 go (Just (_ :< Nothing)) = 1 go (Just (fibNMinus1 :< Just (fibNMinus2 :< _))) = fibNMinus1 + fibNMinus2 :}
>>>
fmap fib [0..10]
[1,1,2,3,5,8,13,21,34,55,89]
In general, Cofree f a
can be thought of as a cache that has the same
shape as the recursive structure which was given as input.
Unfolding functions
unfold :: Corecursive t => (a > Base t a) > a > t Source #
A generalization of unfoldr
. The starting seed is expanded into a base
functor whose recursive positions contain more seeds, which are themselves
expanded, and so on.
>>>
:{
>>>
let ourEnumFromTo :: Int > Int > [Int]
>>>
ourEnumFromTo lo hi = ana go lo where
>>>
go i = if i > hi then Nil else Cons i (i + 1)
>>>
:}
>>>
ourEnumFromTo 1 4
[1,2,3,4]
:: Corecursive t  
=> (a > Base t a)  a (Base t)coalgebra 
> a  seed 
> t  resulting fixed point 
An alias for unfold
.
Combining unfolds and folds
refold :: Functor f => (f b > b) > (a > f a) > a > b Source #
An optimized version of fold f . unfold g
.
Useful when your recursion structure is shaped like a particular recursive datatype, but you're neither consuming nor producing that recursive datatype. For example, the recursion structure of quick sort is a binary tree, but its input and output is a list, not a binary tree.
>>>
data BinTreeF a b = Tip  Branch b a b deriving (Functor)
>>>
:{
>>>
let quicksort :: Ord a => [a] > [a]
>>>
quicksort = refold merge split where
>>>
split [] = Tip
>>>
split (x:xs) = let (l, r) = partition (<x) xs in Branch l x r
>>>
>>>
merge Tip = []
>>>
merge (Branch l x r) = l ++ [x] ++ r
>>>
:}
>>>
quicksort [1,5,2,8,4,9,8]
[1,2,4,5,8,8,9]
Changing representation
refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s > t Source #
Convert from one recursive representation to another.
>>>
refix ["foo", "bar"] :: Fix (ListF String)
Fix (Cons "foo" (Fix (Cons "bar" (Fix Nil))))
hoist :: (Recursive s, Corecursive t) => (forall a. Base s a > Base t a) > s > t Source #
Convert from one recursive type to another.
>>>
showTree $ hoist (\(NonEmptyF h t) > NodeF [h] (maybeToList t)) ( 'a' : "bcd")
(a (b (c d)))
transverse :: (Recursive s, Corecursive t, Functor f) => (forall a. Base s (f a) > f (Base t a)) > s > f t Source #
An effectful version of hoist
.
Properties:
transverse
sequenceA
=pure
Examples:
The weird type of first argument allows user to decide an order of sequencing:
>>>
transverse (\x > print (void x) *> sequence x) "foo" :: IO String
Cons 'f' () Cons 'o' () Cons 'o' () Nil "foo"
>>>
transverse (\x > sequence x <* print (void x)) "foo" :: IO String
Nil Cons 'o' () Cons 'o' () Cons 'f' () "foo"
cotransverse :: (Recursive s, Corecursive t, Functor f) => (forall a. f (Base s a) > Base t (f a)) > f s > t Source #
A coeffectful version of hoist
.
Properties:
cotransverse
distAna
=runIdentity
Examples:
Stateful transformations:
>>>
:{
cotransverse (\(u, b) > case b of Nil > Nil Cons x a > Cons (if u then toUpper x else x) (not u, a)) (True, "foobar") :: String :} "FoObAr"
We can implement a variant of zipWith
>>>
data Pair a = Pair a a deriving Functor
>>>
:{
let zipWith' :: forall a b. (a > a > b) > [a] > [a] > [b] zipWith' f xs ys = cotransverse g (Pair xs ys) where g :: Pair (ListF a c) > ListF b (Pair c) g (Pair Nil _) = Nil g (Pair _ Nil) = Nil g (Pair (Cons x a) (Cons y b)) = Cons (f x y) (Pair a b) :}
>>>
zipWith' (*) [1,2,3] [4,5,6]
[4,10,18]
>>>
zipWith' (*) [1,2,3] [4,5,6,8]
[4,10,18]
>>>
zipWith' (*) [1,2,3,3] [4,5,6]
[4,10,18]
Advanced usage
Mendlerstyle recursionschemes
mpara :: (forall y. (y > c) > (y > Fix f) > f y > c) > Fix f > c Source #
Mendlerstyle recursion
Since: 5.2.2
mhisto :: (forall y. (y > c) > (y > f y) > f y > c) > Fix f > c Source #
Mendlerstyle courseofvalue iteration
mzygo :: (forall y. (y > b) > f y > b) > (forall y. (y > c) > (y > b) > f y > c) > Fix f > c Source #
Mendlerstyle semimutual recursion
Since: 5.2.2
mana :: (forall y. (x > y) > x > f y) > x > Fix f Source #
Mendlerstyle coiteration
Since: 5.2.2
mapo :: (forall y. (Fix f > y) > (x > y) > x > f y) > x > Fix f Source #
Mendlerstyle corecursion
Since: 5.2.2
mfutu :: (forall y. (f y > y) > (x > y) > x > f y) > x > Fix f Source #
Mendlerstyle courseofvalues coiteration
Since: 5.2.2
Fokkinga's recursionschemes
prepro :: (Recursive t, Corecursive t) => (forall b. Base t b > Base t b) > (Base t a > a) > t > a Source #
Fokkinga's prepromorphism
postpro :: (Corecursive t, Recursive t) => (forall b. Base t b > Base t b) > (a > Base t a) > a > t Source #
Fokkinga's postpromorphism
Elgot (co)algebras
coelgot :: Functor f => ((a, f b) > b) > (a > f a) > a > b Source #
Elgot coalgebras: http://comonad.com/reader/2008/elgotcoalgebras/
Generalized recursionschemes
:: (Recursive t, Comonad w)  
=> (forall b. Base t (w b) > w (Base t b))  a distributive law 
> (Base t (w a) > a)  a (Base t)walgebra 
> t  fixed point 
> a 
A generalized catamorphism
:: (Recursive t, Comonad w)  
=> (forall b. Base t (w b) > w (Base t b))  a distributive law 
> (Base t (w a) > a)  a (Base t)walgebra 
> t  fixed point 
> a 
A generalized catamorphism
gpara :: (Recursive t, Corecursive t, Comonad w) => (forall b. Base t (w b) > w (Base t b)) > (Base t (EnvT t w a) > a) > t > a Source #
ghisto :: (Recursive t, Comonad w) => (forall b. Base t (w b) > w (Base t b)) > (Base t (CofreeT (Base t) w a) > a) > t > a Source #
gzygo :: (Recursive 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 #
:: (Corecursive t, Monad m)  
=> (forall b. m (Base t b) > Base t (m b))  a distributive law 
> (a > Base t (m a))  a (Base t)mcoalgebra 
> a  seed 
> t 
A generalized anamorphism
:: (Corecursive t, Monad m)  
=> (forall b. m (Base t b) > Base t (m b))  a distributive law 
> (a > Base t (m a))  a (Base t)mcoalgebra 
> a  seed 
> t 
A generalized anamorphism
gfutu :: (Corecursive t, Functor m, Monad m) => (forall b. m (Base t b) > Base t (m b)) > (a > Base t (FreeT (Base t) m a)) > a > t 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
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
gchrono :: (Functor f, Functor w, Functor m, Comonad w, Monad m) => (forall c. f (w c) > w (f c)) > (forall c. m (f c) > f (m c)) > (f (CofreeT f w b) > b) > (a > f (FreeT f m a)) > a > b Source #
gprepro :: (Recursive t, Corecursive 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 #
gpostpro :: (Corecursive t, Recursive 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
distParaT :: (Corecursive 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 #
distGHisto :: (Functor f, Functor h) => (forall b. f (h b) > h (f b)) > f (CofreeT f h a) > CofreeT f h (f a) Source #
:: Functor f  
=> (f b > b)  
> f (b, a) > (b, f a)  A distributive for semimutual 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 #
distGApoT :: (Functor f, Functor m) => (b > f b) > (forall c. m (f c) > f (m c)) > ExceptT b m (f a) > f (ExceptT b m a) Source #
distGFutu :: (Functor f, Functor h) => (forall b. h (f b) > f (h b)) > FreeT f h (f a) > f (FreeT f h a) Source #
Zygohistomorphic prepromorphisms
zygoHistoPrepro :: (Corecursive t, Recursive 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:
A corrected and modernized version of http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms