Copyright	(C) 2008-2015 Edward Kmett
License	BSD-style (see the file LICENSE)
Maintainer	Edward Kmett <ekmett@gmail.com>
Stability	experimental
Portability	non-portable
Safe Haskell	Safe
Language	Haskell98

Data.Functor.Foldable

Contents

Base functors for fixed points
Fixed points
Folding
- Combinators
- Distributive laws
Unfolding
- Combinators
- Distributive laws
Refolding
- Changing representation
Common names
Mendler-style
Elgot (co)algebras
Zygohistomorphic prepromorphisms

Description

Synopsis

Base functors for fixed points

type family Base t :: * -> * Source #

Instances

type Base [a] Source #
type Base [a] = ListF a
type Base (Maybe a) Source #
type Base (Maybe a) = Const * (Maybe a)
type Base (Nu f) Source #
type Base (Nu f) = f
type Base (Mu f) Source #
type Base (Mu f) = f
type Base (Fix f) Source #
type Base (Fix f) = f
type Base (Either a b) Source #
type Base (Either a b) = Const * (Either a b)

data ListF a b Source #

Base functor of [].

Constructors

Nil
Cons a b

Instances

Eq2 ListF Source #
Methods liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> ListF a c -> ListF b d -> Bool #
Ord2 ListF Source #
Methods liftCompare2 :: (a -> b -> Ordering) -> (c -> d -> Ordering) -> ListF a c -> ListF b d -> Ordering #
Read2 ListF Source #
Methods liftReadsPrec2 :: (Int -> ReadS a) -> ReadS [a] -> (Int -> ReadS b) -> ReadS [b] -> Int -> ReadS (ListF a b) # liftReadList2 :: (Int -> ReadS a) -> ReadS [a] -> (Int -> ReadS b) -> ReadS [b] -> ReadS [ListF a b] #
Show2 ListF Source #
Methods liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> ListF a b -> ShowS # liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [ListF a b] -> ShowS #
Bifunctor ListF Source #
Methods bimap :: (a -> b) -> (c -> d) -> ListF a c -> ListF b d # first :: (a -> b) -> ListF a c -> ListF b c # second :: (b -> c) -> ListF a b -> ListF a c #
Bitraversable ListF Source #
Methods bitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> ListF a b -> f (ListF c d) #
Bifoldable ListF Source #
Methods bifold :: Monoid m => ListF m m -> m # bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> ListF a b -> m # bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> ListF a b -> c # bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> ListF a b -> c #
Functor (ListF a) Source #
Methods fmap :: (a -> b) -> ListF a a -> ListF a b # (<$) :: a -> ListF a b -> ListF a a #
Foldable (ListF a) Source #
Methods fold :: Monoid m => ListF a m -> m # foldMap :: Monoid m => (a -> m) -> ListF a a -> m # foldr :: (a -> b -> b) -> b -> ListF a a -> b # foldr' :: (a -> b -> b) -> b -> ListF a a -> b # foldl :: (b -> a -> b) -> b -> ListF a a -> b # foldl' :: (b -> a -> b) -> b -> ListF a a -> b # foldr1 :: (a -> a -> a) -> ListF a a -> a # foldl1 :: (a -> a -> a) -> ListF a a -> a # toList :: ListF a a -> [a] # null :: ListF a a -> Bool # length :: ListF a a -> Int # elem :: Eq a => a -> ListF a a -> Bool # maximum :: Ord a => ListF a a -> a # minimum :: Ord a => ListF a a -> a # sum :: Num a => ListF a a -> a # product :: Num a => ListF a a -> a #
Traversable (ListF a) Source #
Methods traverse :: Applicative f => (a -> f b) -> ListF a a -> f (ListF a b) # sequenceA :: Applicative f => ListF a (f a) -> f (ListF a a) # mapM :: Monad m => (a -> m b) -> ListF a a -> m (ListF a b) # sequence :: Monad m => ListF a (m a) -> m (ListF a a) #
Generic1 (ListF a) Source #
Associated Types type Rep1 (ListF a :: * -> ) :: -> * # Methods from1 :: ListF a a -> Rep1 (ListF a) a # to1 :: Rep1 (ListF a) a -> ListF a a #
Eq a => Eq1 (ListF a) Source #
Methods liftEq :: (a -> b -> Bool) -> ListF a a -> ListF a b -> Bool #
Ord a => Ord1 (ListF a) Source #
Methods liftCompare :: (a -> b -> Ordering) -> ListF a a -> ListF a b -> Ordering #
Read a => Read1 (ListF a) Source #
Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (ListF a a) # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [ListF a a] #
Show a => Show1 (ListF a) Source #
Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> ListF a a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [ListF a a] -> ShowS #
(Eq a, Eq b) => Eq (ListF a b) Source #
Methods (==) :: ListF a b -> ListF a b -> Bool # (/=) :: ListF a b -> ListF a b -> Bool #
(Ord a, Ord b) => Ord (ListF a b) Source #
Methods compare :: ListF a b -> ListF a b -> Ordering # (<) :: ListF a b -> ListF a b -> Bool # (<=) :: ListF a b -> ListF a b -> Bool # (>) :: ListF a b -> ListF a b -> Bool # (>=) :: ListF a b -> ListF a b -> Bool # max :: ListF a b -> ListF a b -> ListF a b # min :: ListF a b -> ListF a b -> ListF a b #
(Read a, Read b) => Read (ListF a b) Source #
Methods readsPrec :: Int -> ReadS (ListF a b) # readList :: ReadS [ListF a b] # readPrec :: ReadPrec (ListF a b) # readListPrec :: ReadPrec [ListF a b] #
(Show a, Show b) => Show (ListF a b) Source #
Methods showsPrec :: Int -> ListF a b -> ShowS # show :: ListF a b -> String # showList :: [ListF a b] -> ShowS #
Generic (ListF a b) Source #
Associated Types type Rep (ListF a b) :: * -> * # Methods from :: ListF a b -> Rep (ListF a b) x # to :: Rep (ListF a b) x -> ListF a b #
type Rep1 (ListF a) Source #
type Rep1 (ListF a) = D1 (MetaData "ListF" "Data.Functor.Foldable" "recursion-schemes-5-2sRVANWzguL1rJr22PJcSh" False) ((:+:) (C1 (MetaCons "Nil" PrefixI False) U1) (C1 (MetaCons "Cons" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1))))
type Rep (ListF a b) Source #
type Rep (ListF a b) = D1 (MetaData "ListF" "Data.Functor.Foldable" "recursion-schemes-5-2sRVANWzguL1rJr22PJcSh" False) ((:+:) (C1 (MetaCons "Nil" PrefixI False) U1) (C1 (MetaCons "Cons" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 b)))))

Fixed points

newtype Fix f Source #

Constructors

Fix (f (Fix f))

Instances

Eq1 f => Eq (Fix f) Source #
Methods (==) :: Fix f -> Fix f -> Bool # (/=) :: Fix f -> Fix f -> Bool #
(Typeable (* -> *) f, Data (f (Fix f))) => Data (Fix f) Source #
Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Fix f -> c (Fix f) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Fix f) # toConstr :: Fix f -> Constr # dataTypeOf :: Fix f -> DataType # dataCast1 :: Typeable (* -> ) t => (forall d. Data d => c (t d)) -> Maybe (c (Fix f)) # dataCast2 :: Typeable ( -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Fix f)) # gmapT :: (forall b. Data b => b -> b) -> Fix f -> Fix f # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Fix f -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Fix f -> r # gmapQ :: (forall d. Data d => d -> u) -> Fix f -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Fix f -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Fix f -> m (Fix f) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Fix f -> m (Fix f) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Fix f -> m (Fix f) #
Ord1 f => Ord (Fix f) Source #
Methods compare :: Fix f -> Fix f -> Ordering # (<) :: Fix f -> Fix f -> Bool # (<=) :: Fix f -> Fix f -> Bool # (>) :: Fix f -> Fix f -> Bool # (>=) :: Fix f -> Fix f -> Bool # max :: Fix f -> Fix f -> Fix f # min :: Fix f -> Fix f -> Fix f #
Read1 f => Read (Fix f) Source #
Methods readsPrec :: Int -> ReadS (Fix f) # readList :: ReadS [Fix f] # readPrec :: ReadPrec (Fix f) # readListPrec :: ReadPrec [Fix f] #
Show1 f => Show (Fix f) Source #
Methods showsPrec :: Int -> Fix f -> ShowS # show :: Fix f -> String # showList :: [Fix f] -> ShowS #
Functor f => Corecursive (Fix f) Source #
Methods 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 => Recursive (Fix f) Source #
Methods 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 #
type Base (Fix f) Source #
type Base (Fix f) = f

unfix :: Fix f -> f (Fix f) Source #

newtype Mu f Source #

Constructors

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

Instances

(Functor f, Eq1 f) => Eq (Mu f) Source #
Methods (==) :: Mu f -> Mu f -> Bool # (/=) :: Mu f -> Mu f -> Bool #
(Functor f, Ord1 f) => Ord (Mu f) Source #
Methods compare :: Mu f -> Mu f -> Ordering # (<) :: Mu f -> Mu f -> Bool # (<=) :: Mu f -> Mu f -> Bool # (>) :: Mu f -> Mu f -> Bool # (>=) :: Mu f -> Mu f -> Bool # max :: Mu f -> Mu f -> Mu f # min :: Mu f -> Mu f -> Mu f #
(Functor f, Read1 f) => Read (Mu f) Source #
Methods readsPrec :: Int -> ReadS (Mu f) # readList :: ReadS [Mu f] # readPrec :: ReadPrec (Mu f) # readListPrec :: ReadPrec [Mu f] #
(Functor f, Show1 f) => Show (Mu f) Source #
Methods showsPrec :: Int -> Mu f -> ShowS # show :: Mu f -> String # showList :: [Mu f] -> ShowS #
Functor f => Corecursive (Mu f) Source #
Methods 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 => Recursive (Mu f) Source #
Methods 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 #
type Base (Mu f) Source #
type Base (Mu f) = f

data Nu f where Source #

Constructors

Nu :: (a -> f a) -> a -> Nu f

Instances

(Functor f, Eq1 f) => Eq (Nu f) Source #
Methods (==) :: Nu f -> Nu f -> Bool # (/=) :: Nu f -> Nu f -> Bool #
(Functor f, Ord1 f) => Ord (Nu f) Source #
Methods compare :: Nu f -> Nu f -> Ordering # (<) :: Nu f -> Nu f -> Bool # (<=) :: Nu f -> Nu f -> Bool # (>) :: Nu f -> Nu f -> Bool # (>=) :: Nu f -> Nu f -> Bool # max :: Nu f -> Nu f -> Nu f # min :: Nu f -> Nu f -> Nu f #
(Functor f, Read1 f) => Read (Nu f) Source #
Methods readsPrec :: Int -> ReadS (Nu f) # readList :: ReadS [Nu f] # readPrec :: ReadPrec (Nu f) # readListPrec :: ReadPrec [Nu f] #
(Functor f, Show1 f) => Show (Nu f) Source #
Methods showsPrec :: Int -> Nu f -> ShowS # show :: Nu f -> String # showList :: [Nu f] -> ShowS #
Functor f => Corecursive (Nu f) Source #
Methods 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 #
Functor f => Recursive (Nu f) Source #
Methods 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 #
type Base (Nu f) Source #
type Base (Nu f) = f

Folding

class Functor (Base t) => Recursive t where Source #

Minimal complete definition

project

Methods

project :: t -> Base t t Source #

cata :: (Base t a -> a) -> t -> a Source #

para :: (Base t (t, a) -> a) -> t -> a Source #

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 [a] Source #
Methods project :: [a] -> Base [a] [a] Source # cata :: (Base [a] a -> a) -> [a] -> a Source # para :: (Base [a] ([a], a) -> a) -> [a] -> a Source # gpara :: (Corecursive [a], Comonad w) => (forall b. Base [a] (w b) -> w (Base [a] b)) -> (Base [a] (EnvT [a] w a) -> a) -> [a] -> a Source # prepro :: Corecursive [a] => (forall b. Base [a] b -> Base [a] b) -> (Base [a] a -> a) -> [a] -> a 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 a) -> a) -> [a] -> a Source #
Recursive (Maybe a) Source #
Methods project :: Maybe a -> Base (Maybe a) (Maybe a) Source # cata :: (Base (Maybe a) a -> a) -> Maybe a -> a Source # para :: (Base (Maybe a) (Maybe a, a) -> a) -> Maybe a -> a 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 a) -> a) -> Maybe a -> a Source # prepro :: Corecursive (Maybe a) => (forall b. Base (Maybe a) b -> Base (Maybe a) b) -> (Base (Maybe a) a -> a) -> Maybe a -> a 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 a) -> a) -> Maybe a -> a Source #
Functor f => Recursive (Nu f) Source #
Methods 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 #
Functor f => Recursive (Mu f) Source #
Methods 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 (Fix f) Source #
Methods 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 #
Recursive (Either a b) Source #
Methods project :: Either a b -> Base (Either a b) (Either a b) Source # cata :: (Base (Either a b) a -> a) -> Either a b -> a Source # para :: (Base (Either a b) (Either a b, a) -> a) -> Either a b -> a Source # gpara :: (Corecursive (Either a b), Comonad w) => (forall c. Base (Either a b) (w c) -> w (Base (Either a b) c)) -> (Base (Either a b) (EnvT (Either a b) w a) -> a) -> Either a b -> a Source # prepro :: Corecursive (Either a b) => (forall c. Base (Either a b) c -> Base (Either a b) c) -> (Base (Either a b) a -> a) -> Either a b -> a Source # gprepro :: (Corecursive (Either a b), Comonad w) => (forall c. Base (Either a b) (w c) -> w (Base (Either a b) c)) -> (forall c. Base (Either a b) c -> Base (Either a b) c) -> (Base (Either a b) (w a) -> a) -> Either a b -> a Source #

Combinators

gapo :: Corecursive t => (b -> Base t b) -> (a -> Base t (Either b a)) -> a -> t Source #

gcata Source #

Arguments

:: (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)-w-algebra
-> t	fixed point
-> a

A generalized catamorphism

zygo :: Recursive t => (Base t b -> b) -> (Base t (b, 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 #

histo :: Recursive t => (Base t (Cofree (Base t) a) -> a) -> t -> a Source #

Course-of-value iteration

ghisto :: (Recursive t, Functor h) => (forall b. Base t (h b) -> h (Base t b)) -> (Base t (Cofree h a) -> a) -> t -> a Source #

futu :: Corecursive t => (a -> Base t (Free (Base t) a)) -> a -> t Source #

chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> b Source #

gchrono :: (Functor f, Functor w, Functor m) => (forall c. f (w c) -> w (f c)) -> (forall c. m (f c) -> f (m c)) -> (f (Cofree w b) -> b) -> (a -> f (Free m a)) -> a -> b Source #

Distributive laws

distCata :: Functor f => f (Identity a) -> Identity (f a) Source #

distPara :: Corecursive t => Base t (t, a) -> (t, Base t a) Source #

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 #

distZygo Source #

Arguments

:: Functor f
=> (f b -> b)
-> f (b, a) -> (b, f a)	A distributive for semi-mutual 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 #

distHisto :: Functor f => f (Cofree f a) -> Cofree f (f a) Source #

distGHisto :: (Functor f, Functor h) => (forall b. f (h b) -> h (f b)) -> f (Cofree h a) -> Cofree h (f a) Source #

distFutu :: Functor f => Free f (f a) -> f (Free f a) Source #

distGFutu :: (Functor f, Functor h) => (forall b. h (f b) -> f (h b)) -> Free h (f a) -> f (Free h a) Source #

Unfolding

class Functor (Base t) => Corecursive t where Source #

Minimal complete definition

embed

Methods

embed :: Base t t -> t Source #

ana :: (a -> Base t a) -> a -> t Source #

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 [a] Source #
Methods embed :: Base [a] [a] -> [a] Source # ana :: (a -> Base [a] a) -> a -> [a] Source # apo :: (a -> Base [a] (Either [a] a)) -> a -> [a] Source # postpro :: Recursive [a] => (forall b. Base [a] b -> Base [a] b) -> (a -> Base [a] a) -> a -> [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) -> (a -> Base [a] (m a)) -> a -> [a] Source #
Corecursive (Maybe a) Source #
Methods embed :: Base (Maybe a) (Maybe a) -> Maybe a Source # ana :: (a -> Base (Maybe a) a) -> a -> Maybe a Source # apo :: (a -> Base (Maybe a) (Either (Maybe a) a)) -> a -> Maybe a Source # postpro :: Recursive (Maybe a) => (forall b. Base (Maybe a) b -> Base (Maybe a) b) -> (a -> Base (Maybe a) a) -> a -> 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) -> (a -> Base (Maybe a) (m a)) -> a -> Maybe a Source #
Functor f => Corecursive (Nu f) Source #
Methods 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 #
Functor f => Corecursive (Mu f) Source #
Methods 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 (Fix f) Source #
Methods 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 #
Corecursive (Either a b) Source #
Methods embed :: Base (Either a b) (Either a b) -> Either a b Source # ana :: (a -> Base (Either a b) a) -> a -> Either a b Source # apo :: (a -> Base (Either a b) (Either (Either a b) a)) -> a -> Either a b Source # postpro :: Recursive (Either a b) => (forall c. Base (Either a b) c -> Base (Either a b) c) -> (a -> Base (Either a b) a) -> a -> Either a b Source # gpostpro :: (Recursive (Either a b), Monad m) => (forall c. m (Base (Either a b) c) -> Base (Either a b) (m c)) -> (forall c. Base (Either a b) c -> Base (Either a b) c) -> (a -> Base (Either a b) (m a)) -> a -> Either a b Source #

Combinators

gana Source #

Arguments

:: (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)-m-coalgebra
-> a	seed
-> t

A generalized anamorphism

Distributive laws

distAna :: Functor f => Identity (f a) -> f (Identity a) Source #

distApo :: Recursive t => Either t (Base t a) -> Base t (Either t a) Source #

distGApo :: Functor f => (b -> f b) -> Either b (f a) -> f (Either b 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 #

Refolding

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

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

refix :: (Recursive s, Corecursive t, Base s ~ Base t) => s -> t Source #

Common names

fold :: Recursive t => (Base t a -> a) -> t -> a Source #

gfold Source #

Arguments

:: (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)-w-algebra
-> t	fixed point
-> a

A generalized catamorphism

unfold :: Corecursive t => (a -> Base t a) -> a -> t Source #

gunfold Source #

Arguments

:: (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)-m-coalgebra
-> a	seed
-> t

A generalized anamorphism

refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b 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

Mendler-style

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

Mendler-style iteration

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

Mendler-style course-of-value iteration

Elgot (co)algebras

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

Elgot algebras

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

Elgot coalgebras: http://comonad.com/reader/2008/elgot-coalgebras/

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