recursion-schemes-5.2.1: Representing common recursion patterns as higher-order functions

Copyright (C) 2008-2015 Edward Kmett BSD-style (see the file LICENSE) "Samuel Gélineau" , "Oleg Grenrus" , "Ryan Scott" experimental non-portable Safe Haskell2010

Data.Functor.Foldable

Description

Synopsis

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 non-recursive functions on a related, non-recursive datatype we call the "base functor".

For example, [a] is a recursive type, and its corresponding base functor is ListF a:

data ListF a b = Nil | Cons a b
type instance Base [a] = ListF a


The relationship between those two types is that if we replace b with ListF a, we obtain a type which is isomorphic to [a].

Instances
 type Base Natural Source # Instance detailsDefined in Data.Functor.Foldable type Base Natural = Maybe type Base [a] Source # Instance detailsDefined in Data.Functor.Foldable type Base [a] = ListF a type Base (Maybe a) Source # Example boring stub for non-recursive data types Instance detailsDefined in Data.Functor.Foldable type Base (Maybe a) = (Const (Maybe a) :: Type -> Type) type Base (NonEmpty a) Source # Instance detailsDefined in Data.Functor.Foldable type Base (NonEmpty a) = NonEmptyF a type Base (Tree a) Source # Instance detailsDefined in Data.Functor.Foldable type Base (Tree a) = TreeF a type Base (Fix f) Source # Instance detailsDefined in Data.Functor.Foldable type Base (Fix f) = f type Base (Mu f) Source # Instance detailsDefined in Data.Functor.Foldable type Base (Mu f) = f type Base (Nu f) Source # Instance detailsDefined in Data.Functor.Foldable type Base (Nu f) = f type Base (Either a b) Source # Example boring stub for non-recursive data types Instance detailsDefined in Data.Functor.Foldable type Base (Either a b) = (Const (Either a b) :: Type -> Type) type Base (Cofree f a) Source # Cofree comonads are Recursive/Corecursive Instance detailsDefined in Data.Functor.Foldable type Base (Cofree f a) = CofreeF f a type Base (F f a) Source # Church encoded free monads are Recursive/Corecursive, in the same way that Mu is. Instance detailsDefined in Data.Functor.Foldable type Base (F f a) = FreeF f a type Base (Free f a) Source # Free monads are Recursive/Corecursive Instance detailsDefined in Data.Functor.Foldable type Base (Free f a) = FreeF f a type Base (FreeT f m a) Source # Free transformations of monads are Recursive/Corecursive Instance detailsDefined in Data.Functor.Foldable type Base (FreeT f m a) = Compose m (FreeF f a) type Base (CofreeT f w a) Source # Cofree tranformations of comonads are Recursive/Corecusive Instance detailsDefined in Data.Functor.Foldable type Base (CofreeT f w a) = Compose w (CofreeF f a)

data ListF a b Source #

Base functor of [].

Constructors

 Nil Cons a b
Instances
 Source # Instance detailsDefined in Data.Functor.Base Methodsbitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> ListF a b -> f (ListF c d) # Source # Instance detailsDefined in Data.Functor.Base Methodsbifold :: 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 # Source # Instance detailsDefined in Data.Functor.Base Methodsbimap :: (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 # Source # Instance detailsDefined in Data.Functor.Base MethodsliftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> ListF a c -> ListF b d -> Bool # Source # Instance detailsDefined in Data.Functor.Base MethodsliftCompare2 :: (a -> b -> Ordering) -> (c -> d -> Ordering) -> ListF a c -> ListF b d -> Ordering # Source # Instance detailsDefined in Data.Functor.Base MethodsliftReadsPrec2 :: (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] #liftReadPrec2 :: ReadPrec a -> ReadPrec [a] -> ReadPrec b -> ReadPrec [b] -> ReadPrec (ListF a b) #liftReadListPrec2 :: ReadPrec a -> ReadPrec [a] -> ReadPrec b -> ReadPrec [b] -> ReadPrec [ListF a b] # Source # Instance detailsDefined in Data.Functor.Base MethodsliftShowsPrec2 :: (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 # Functor (ListF a) Source # Instance detailsDefined in Data.Functor.Base Methodsfmap :: (a0 -> b) -> ListF a a0 -> ListF a b #(<$) :: a0 -> ListF a b -> ListF a a0 # Source # Instance detailsDefined in Data.Functor.Base Methodsfold :: Monoid m => ListF a m -> m #foldMap :: Monoid m => (a0 -> m) -> ListF a a0 -> m #foldr :: (a0 -> b -> b) -> b -> ListF a a0 -> b #foldr' :: (a0 -> b -> b) -> b -> ListF a a0 -> b #foldl :: (b -> a0 -> b) -> b -> ListF a a0 -> b #foldl' :: (b -> a0 -> b) -> b -> ListF a a0 -> b #foldr1 :: (a0 -> a0 -> a0) -> ListF a a0 -> a0 #foldl1 :: (a0 -> a0 -> a0) -> ListF a a0 -> a0 #toList :: ListF a a0 -> [a0] #null :: ListF a a0 -> Bool #length :: ListF a a0 -> Int #elem :: Eq a0 => a0 -> ListF a a0 -> Bool #maximum :: Ord a0 => ListF a a0 -> a0 #minimum :: Ord a0 => ListF a a0 -> a0 #sum :: Num a0 => ListF a a0 -> a0 #product :: Num a0 => ListF a a0 -> a0 # Source # Instance detailsDefined in Data.Functor.Base Methodstraverse :: Applicative f => (a0 -> f b) -> ListF a a0 -> f (ListF a b) #sequenceA :: Applicative f => ListF a (f a0) -> f (ListF a a0) #mapM :: Monad m => (a0 -> m b) -> ListF a a0 -> m (ListF a b) #sequence :: Monad m => ListF a (m a0) -> m (ListF a a0) # Eq a => Eq1 (ListF a) Source # Instance detailsDefined in Data.Functor.Base MethodsliftEq :: (a0 -> b -> Bool) -> ListF a a0 -> ListF a b -> Bool # Ord a => Ord1 (ListF a) Source # Instance detailsDefined in Data.Functor.Base MethodsliftCompare :: (a0 -> b -> Ordering) -> ListF a a0 -> ListF a b -> Ordering # Read a => Read1 (ListF a) Source # Instance detailsDefined in Data.Functor.Base MethodsliftReadsPrec :: (Int -> ReadS a0) -> ReadS [a0] -> Int -> ReadS (ListF a a0) #liftReadList :: (Int -> ReadS a0) -> ReadS [a0] -> ReadS [ListF a a0] #liftReadPrec :: ReadPrec a0 -> ReadPrec [a0] -> ReadPrec (ListF a a0) #liftReadListPrec :: ReadPrec a0 -> ReadPrec [a0] -> ReadPrec [ListF a a0] # Show a => Show1 (ListF a) Source # Instance detailsDefined in Data.Functor.Base MethodsliftShowsPrec :: (Int -> a0 -> ShowS) -> ([a0] -> ShowS) -> Int -> ListF a a0 -> ShowS #liftShowList :: (Int -> a0 -> ShowS) -> ([a0] -> ShowS) -> [ListF a a0] -> ShowS # Generic1 (ListF a :: Type -> Type) Source # Instance detailsDefined in Data.Functor.Base Associated Typestype Rep1 (ListF a) :: k -> Type # Methodsfrom1 :: ListF a a0 -> Rep1 (ListF a) a0 #to1 :: Rep1 (ListF a) a0 -> ListF a a0 # (Eq a, Eq b) => Eq (ListF a b) Source # Instance detailsDefined in Data.Functor.Base Methods(==) :: ListF a b -> ListF a b -> Bool #(/=) :: ListF a b -> ListF a b -> Bool # (Ord a, Ord b) => Ord (ListF a b) Source # Instance detailsDefined in Data.Functor.Base Methodscompare :: 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 # Instance detailsDefined in Data.Functor.Base MethodsreadsPrec :: 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 # Instance detailsDefined in Data.Functor.Base MethodsshowsPrec :: Int -> ListF a b -> ShowS #show :: ListF a b -> String #showList :: [ListF a b] -> ShowS # Generic (ListF a b) Source # Instance detailsDefined in Data.Functor.Base Associated Typestype Rep (ListF a b) :: Type -> Type # Methodsfrom :: ListF a b -> Rep (ListF a b) x #to :: Rep (ListF a b) x -> ListF a b # type Rep1 (ListF a :: Type -> Type) Source # Instance detailsDefined in Data.Functor.Base type Rep1 (ListF a :: Type -> Type) = D1 (MetaData "ListF" "Data.Functor.Base" "recursion-schemes-5.2.1-8Twg0nmm5ic5UEL3bWO0RZ" False) (C1 (MetaCons "Nil" PrefixI False) (U1 :: Type -> Type) :+: C1 (MetaCons "Cons" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1)) type Rep (ListF a b) Source # Instance detailsDefined in Data.Functor.Base type Rep (ListF a b) = D1 (MetaData "ListF" "Data.Functor.Base" "recursion-schemes-5.2.1-8Twg0nmm5ic5UEL3bWO0RZ" False) (C1 (MetaCons "Nil" PrefixI False) (U1 :: Type -> Type) :+: C1 (MetaCons "Cons" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a) :*: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 b))) 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 ListF a [a]. Ifthat unrolled value is 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. Minimal complete definition Nothing Methods 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]  Arguments  :: (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 sub-tree 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 sub-tree, in addition to the result of folding that sub-tree.

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

Combinators

gapo :: Corecursive t => (b -> Base t b) -> (a -> Base t (Either b a)) -> a -> t 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, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (CofreeT (Base t) w a) -> a) -> t -> a Source #

futu :: Corecursive t => (a -> Base t (Free (Base t) a)) -> a -> t 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 #

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

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 #

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 (CofreeT f h a) -> CofreeT f 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)) -> 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 ListF a [a] can be rolled up into a [a]. This [a] can then be used in a Cons to construct another ListF a [a], which can be rolled up as well, and so on.

Typically, Corecursive types also have a Recursive instance, in which case embed and project are inverses.

Minimal complete definition

Nothing

Methods

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]


Arguments

 :: (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
 Source # Instance detailsDefined in Data.Functor.Foldable Methodsana :: (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 # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Source # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Source # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Source # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 F directly. Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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 # Instance detailsDefined in Data.Functor.Foldable Methodsembed :: 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

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 #

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

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

An alias for cata.

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 #

An alias for ana.

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 #

An alias for hylo.

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 #

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:

Effectful combinators

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

Effectful fold.

This is a type specialisation of cata.

An example terminating a recursion immediately:

>>> cataA (\alg -> case alg of { Nil -> pure (); Cons a _ -> Const [a] })  "hello"
Const "h"


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]