Copyright  (C) 20082015 Edward Kmett 

License  BSDstyle (see the file LICENSE) 
Maintainer  "Samuel Gélineau" <gelisam@gmail.com>, "Oleg Grenrus" <oleg.grenrus@iki.fi>, "Ryan Scott" <ryan.gl.scott@gmail.com> 
Stability  experimental 
Portability  nonportable 
Safe Haskell  Safe 
Language  Haskell2010 
Synopsis
 type family Base t :: * > *
 data ListF a b
 class Functor (Base t) => Recursive t where
 project :: t > Base t t
 cata :: (Base t a > a) > t > a
 para :: (Base t (t, a) > a) > t > a
 gpara :: (Corecursive t, Comonad w) => (forall b. Base t (w b) > w (Base t b)) > (Base t (EnvT t w a) > a) > t > a
 prepro :: Corecursive t => (forall b. Base t b > Base t b) > (Base t a > a) > t > a
 gprepro :: (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
 gapo :: Corecursive t => (b > Base t b) > (a > Base t (Either b a)) > a > t
 gcata :: (Recursive t, Comonad w) => (forall b. Base t (w b) > w (Base t b)) > (Base t (w a) > a) > t > a
 zygo :: Recursive t => (Base t b > b) > (Base t (b, 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
 histo :: Recursive t => (Base t (Cofree (Base t) 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
 futu :: Corecursive t => (a > Base t (Free (Base t) 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
 chrono :: Functor f => (f (Cofree f b) > b) > (a > f (Free f 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
 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)
 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)
 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)
 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)
 class Functor (Base t) => Corecursive t where
 embed :: Base t t > t
 ana :: (a > Base t a) > a > t
 apo :: (a > Base t (Either t a)) > a > t
 postpro :: Recursive t => (forall b. Base t b > Base t b) > (a > Base t a) > a > t
 gpostpro :: (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
 gana :: (Corecursive t, Monad m) => (forall b. m (Base t b) > Base t (m b)) > (a > Base t (m a)) > a > t
 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)
 hylo :: Functor f => (f b > b) > (a > f 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
 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
 fold :: Recursive t => (Base t a > a) > t > a
 gfold :: (Recursive t, Comonad w) => (forall b. Base t (w b) > w (Base t b)) > (Base t (w a) > a) > t > a
 unfold :: Corecursive t => (a > Base t a) > a > t
 gunfold :: (Corecursive t, Monad m) => (forall b. m (Base t b) > Base t (m b)) > (a > Base t (m a)) > a > t
 refold :: Functor f => (f b > b) > (a > f a) > a > b
 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
 mcata :: (forall y. (y > c) > f y > c) > Fix f > c
 mhisto :: (forall y. (y > c) > (y > f y) > f y > c) > Fix f > c
 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
 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
 cataA :: Recursive t => (Base t (f a) > f a) > t > f a
 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
Base functors for fixed points
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 (Mu f) Source #  
Defined in Data.Functor.Foldable  
type Base (Nu f) Source #  
Defined in Data.Functor.Foldable  
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 (F f a) Source #  Church encoded free monads are Recursive/Corecursive, in the same way that

Defined in Data.Functor.Foldable  
type Base (Free f a) Source #  Free monads are Recursive/Corecursive 
Defined in Data.Functor.Foldable  
type Base (FreeT f m a) Source #  Free transformations of monads are Recursive/Corecursive 
Defined in Data.Functor.Foldable  
type Base (CofreeT f w a) Source #  Cofree tranformations of comonads are Recursive/Corecusive 
Defined in Data.Functor.Foldable 
Base functor of []
.
Instances
Folding
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
project :: t > Base t t Source #
Unroll a single recursion layer.
>>>
project [1,2,3]
Cons 1 [2,3]
project :: (Generic t, Generic (Base t t), GCoerce (Rep t) (Rep (Base t t))) => t > Base t t Source #
Unroll a single recursion layer.
>>>
project [1,2,3]
Cons 1 [2,3]
:: (Base t a > a)  a (Base t)algebra 
> t  fixed point 
> a  result 
A generalization of foldr
. The elements of the base functor, called the
"recursive positions", give the result of folding the subtree at that
position.
>>>
:{
>>>
let oursum = cata $ \case
>>>
Nil > 0
>>>
Cons x acc > x + acc
>>>
:}
>>>
oursum [1,2,3]
6
para :: (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.
gpara :: (Corecursive t, Comonad w) => (forall b. Base t (w b) > w (Base t b)) > (Base t (EnvT t w a) > a) > t > a Source #
prepro :: Corecursive t => (forall b. Base t b > Base t b) > (Base t a > a) > t > a Source #
Fokkinga's prepromorphism
gprepro :: (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 #
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 (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 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 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 #  
(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 # 
Combinators
:: (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
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 #
histo :: Recursive t => (Base t (Cofree (Base t) a) > a) > t > a Source #
Courseofvalue iteration
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 #
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 #
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 #
Distributive laws
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 #
:: 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 #
distGHisto :: (Functor f, Functor h) => (forall b. f (h b) > h (f b)) > f (CofreeT f h a) > CofreeT f h (f 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 #
Unfolding
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
embed :: Base t t > t Source #
Roll up a single recursion layer.
>>>
embed (Cons 1 [2,3])
[1,2,3]
embed :: (Generic t, Generic (Base t t), GCoerce (Rep (Base t t)) (Rep t)) => Base t t > t Source #
Roll up a single recursion layer.
>>>
embed (Cons 1 [2,3])
[1,2,3]
:: (a > Base t a)  a (Base t)coalgebra 
> a  seed 
> t  resulting fixed point 
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]
apo :: (a > Base t (Either t a)) > a > t Source #
postpro :: Recursive t => (forall b. Base t b > Base t b) > (a > Base t a) > a > t Source #
Fokkinga's postpromorphism
gpostpro :: (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
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 (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 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 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 #  
(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 # 
Combinators
:: (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
Distributive laws
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 #
Refolding
hylo :: Functor f => (f b > b) > (a > f a) > a > b Source #
An optimized version of cata f . ana 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 = hylo 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]
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
Changing representation
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)))
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))))
Common names
:: (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
:: (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
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
Mendlerstyle
mhisto :: (forall y. (y > c) > (y > f y) > f y > c) > Fix f > c Source #
Mendlerstyle courseofvalue iteration
Elgot (co)algebras
coelgot :: Functor f => ((a, f b) > b) > (a > f a) > a > b Source #
Elgot coalgebras: http://comonad.com/reader/2008/elgotcoalgebras/
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
Effectful combinators
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]