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

Copyright | (C) 2008-2015 Edward Kmett
License | BSD-style (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 | non-portable
Safe Haskell | Safe-Inferred
Language | Haskell2010

Data.Functor.Foldable

Contents

- Base functors
- Type classes
- Folding functions
- Unfolding functions
- Combining unfolds and folds
- Changing representation
- Advanced usage
  - Mendler-style recursion-schemes
  - Fokkinga's recursion-schemes
  - Elgot (co)algebras
  - Generalized recursion-schemes
  - Zygohistomorphic prepromorphisms

Description

Synopsis

- type family Base t :: Type -> Type
- data ListF a b
  - = Nil
  - | Cons a b
- class Functor (Base t) => Recursive t where
  - project :: t -> Base t t
- class Functor (Base t) => Corecursive t where
  - embed :: Base t t -> t
- 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 :: Type -> Type 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

Instances details

type Base Natural Source # |
Instance details Defined in Data.Functor.Foldable type Base Natural = Maybe
type Base (Tree a) Source # |
Instance details Defined in Data.Functor.Foldable type Base (Tree a) = TreeF a
type Base (Fix f) Source # |
Instance details Defined in Data.Functor.Foldable type Base (Fix f) = f
type Base (Mu f) Source # |
Instance details Defined in Data.Functor.Foldable type Base (Mu f) = f
type Base (Nu f) Source # |
Instance details Defined in Data.Functor.Foldable type Base (Nu f) = f
type Base (NonEmpty a) Source # |
Instance details Defined in Data.Functor.Foldable type Base (NonEmpty a) = NonEmptyF a
type Base (Maybe a) Source # | Example boring stub for non-recursive data types
Instance details Defined in Data.Functor.Foldable type Base (Maybe a) = Const (Maybe a) :: Type -> Type
type Base [a] Source # |
Instance details Defined in Data.Functor.Foldable type Base [a] = ListF a
type Base (Cofree f a) Source # | Cofree comonads are Recursive/Corecursive
Instance details Defined in Data.Functor.Foldable type Base (Cofree f a) = CofreeF f a
type Base (Free f a) Source # | Free monads are Recursive/Corecursive
Instance details 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 `Mu` is.
Instance details Defined in Data.Functor.Foldable type Base (F f a) = FreeF f a
type Base (Either a b) Source # | Example boring stub for non-recursive data types
Instance details Defined in Data.Functor.Foldable type Base (Either a b) = Const (Either a b) :: Type -> Type
type Base (CofreeT f w a) Source # | Cofree tranformations of comonads are Recursive/Corecusive
Instance details Defined in Data.Functor.Foldable type Base (CofreeT f w a) = Compose w (CofreeF f a)
type Base (FreeT f m a) Source # | Free transformations of monads are Recursive/Corecursive
Instance details Defined in Data.Functor.Foldable type Base (FreeT f m a) = Compose m (FreeF f a)

data ListF a b Source #

Base functor of `[]`.

Constructors

Nil |
Cons a b |

#### Instances

Instances details

Bifoldable ListF Source # |
Instance details Defined in Data.Functor.Base Methods bifold :: Monoid m => ListF m m -> m Source # bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> ListF a b -> m Source # bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> ListF a b -> c Source # bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> ListF a b -> c Source #
Bifunctor ListF Source # |
Instance details Defined in Data.Functor.Base Methods bimap :: (a -> b) -> (c -> d) -> ListF a c -> ListF b d Source # first :: (a -> b) -> ListF a c -> ListF b c Source # second :: (b -> c) -> ListF a b -> ListF a c Source #
Bitraversable ListF Source # |
Instance details Defined in Data.Functor.Base Methods bitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> ListF a b -> f (ListF c d) Source #
Eq2 ListF Source # |
Instance details Defined in Data.Functor.Base Methods liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> ListF a c -> ListF b d -> Bool Source #
Ord2 ListF Source # |
Instance details Defined in Data.Functor.Base Methods liftCompare2 :: (a -> b -> Ordering) -> (c -> d -> Ordering) -> ListF a c -> ListF b d -> Ordering Source #
Read2 ListF Source # |

Instance details

Defined in Data.Functor.Base

Methods

liftReadsPrec2 :: (Int -> ReadS a) -> ReadS [a] -> (Int -> ReadS b) -> ReadS [b] -> Int -> ReadS (ListF a b) Source #

liftReadList2 :: (Int -> ReadS a) -> ReadS [a] -> (Int -> ReadS b) -> ReadS [b] -> ReadS [ListF a b] Source #

liftReadPrec2 :: ReadPrec a -> ReadPrec [a] -> ReadPrec b -> ReadPrec [b] -> ReadPrec (ListF a b) Source #

liftReadListPrec2 :: ReadPrec a -> ReadPrec [a] -> ReadPrec b -> ReadPrec [b] -> ReadPrec [ListF a b] Source #

Show2 ListF Source # |
Instance details Defined in Data.Functor.Base Methods liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> ListF a b -> ShowS Source # liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [ListF a b] -> ShowS Source #
Generic1 (ListF a :: Type -> Type) Source # |

Instance details

Defined in Data.Functor.Base

Associated Types

type Rep1 (ListF a :: Type -> Type) |

Instance details

Defined in Data.Functor.Base

type Rep1 (ListF a :: Type -> Type) = D1 ('MetaData "ListF" "Data.Functor.Base" "recursion-schemes-5.2.3-K3D9dDpBcte1cy2ppH5E3C" '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))

Methods

from1 :: ListF a a0 -> Rep1 (ListF a) a0 Source #

to1 :: Rep1 (ListF a) a0 -> ListF a a0 Source #

Eq a => Eq1 (ListF a) Source # |
Instance details Defined in Data.Functor.Base Methods liftEq :: (a0 -> b -> Bool) -> ListF a a0 -> ListF a b -> Bool Source #
Ord a => Ord1 (ListF a) Source # |
Instance details Defined in Data.Functor.Base Methods liftCompare :: (a0 -> b -> Ordering) -> ListF a a0 -> ListF a b -> Ordering Source #
Read a => Read1 (ListF a) Source # |
Instance details Defined in Data.Functor.Base Methods liftReadsPrec :: (Int -> ReadS a0) -> ReadS [a0] -> Int -> ReadS (ListF a a0) Source # liftReadList :: (Int -> ReadS a0) -> ReadS [a0] -> ReadS [ListF a a0] Source # liftReadPrec :: ReadPrec a0 -> ReadPrec [a0] -> ReadPrec (ListF a a0) Source # liftReadListPrec :: ReadPrec a0 -> ReadPrec [a0] -> ReadPrec [ListF a a0] Source #
Show a => Show1 (ListF a) Source # |
Instance details Defined in Data.Functor.Base Methods liftShowsPrec :: (Int -> a0 -> ShowS) -> ([a0] -> ShowS) -> Int -> ListF a a0 -> ShowS Source # liftShowList :: (Int -> a0 -> ShowS) -> ([a0] -> ShowS) -> [ListF a a0] -> ShowS Source #
Functor (ListF a) Source # |
Instance details Defined in Data.Functor.Base Methods fmap :: (a0 -> b) -> ListF a a0 -> ListF a b Source # (<$) :: a0 -> ListF a b -> ListF a a0 Source #
Foldable (ListF a) Source # |

Instance details

Defined in Data.Functor.Base

Methods

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

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

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

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

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

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

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

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

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

toList :: ListF a a0 -> [a0] Source #

null :: ListF a a0 -> Bool Source #

length :: ListF a a0 -> Int Source #

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

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

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

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

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

Traversable (ListF a) Source # |
Instance details Defined in Data.Functor.Base Methods traverse :: Applicative f => (a0 -> f b) -> ListF a a0 -> f (ListF a b) Source # sequenceA :: Applicative f => ListF a (f a0) -> f (ListF a a0) Source # mapM :: Monad m => (a0 -> m b) -> ListF a a0 -> m (ListF a b) Source # sequence :: Monad m => ListF a (m a0) -> m (ListF a a0) Source #
Generic (ListF a b) Source # |

Instance details

Defined in Data.Functor.Base

Associated Types

type Rep (ListF a b) |

Instance details

Defined in Data.Functor.Base

type Rep (ListF a b) = D1 ('MetaData "ListF" "Data.Functor.Base" "recursion-schemes-5.2.3-K3D9dDpBcte1cy2ppH5E3C" '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)))

Methods

from :: ListF a b -> Rep (ListF a b) x Source #

to :: Rep (ListF a b) x -> ListF a b Source #

(Read a, Read b) => Read (ListF a b) Source # |
Instance details Defined in Data.Functor.Base Methods readsPrec :: Int -> ReadS (ListF a b) Source # readList :: ReadS [ListF a b] Source # readPrec :: ReadPrec (ListF a b) Source # readListPrec :: ReadPrec [ListF a b] Source #
(Show a, Show b) => Show (ListF a b) Source # |
Instance details Defined in Data.Functor.Base Methods showsPrec :: Int -> ListF a b -> ShowS Source # show :: ListF a b -> String Source # showList :: [ListF a b] -> ShowS Source #
(Eq a, Eq b) => Eq (ListF a b) Source # |
Instance details Defined in Data.Functor.Base Methods (==) :: ListF a b -> ListF a b -> Bool Source # (/=) :: ListF a b -> ListF a b -> Bool Source #
(Ord a, Ord b) => Ord (ListF a b) Source # |

Instance details

Defined in Data.Functor.Base

Methods

compare :: ListF a b -> ListF a b -> Ordering Source #

(<) :: ListF a b -> ListF a b -> Bool Source #

(<=) :: ListF a b -> ListF a b -> Bool Source #

(>) :: ListF a b -> ListF a b -> Bool Source #

(>=) :: ListF a b -> ListF a b -> Bool Source #

max :: ListF a b -> ListF a b -> ListF a b Source #

min :: ListF a b -> ListF a b -> ListF a b Source #

type Rep1 (ListF a :: Type -> Type) Source # |

Instance details

Defined in Data.Functor.Base

type Rep1 (ListF a :: Type -> Type) = D1 ('MetaData "ListF" "Data.Functor.Base" "recursion-schemes-5.2.3-K3D9dDpBcte1cy2ppH5E3C" '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 details

Defined in Data.Functor.Base

type Rep (ListF a b) = D1 ('MetaData "ListF" "Data.Functor.Base" "recursion-schemes-5.2.3-K3D9dDpBcte1cy2ppH5E3C" '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)))

# 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 ``ListF` a [a]`. If that 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]

default project :: (Generic t, Generic (Base t t), GCoerce (Rep t) (Rep (Base t t))) => t -> Base t t Source #

#### Instances

Instances details

Recursive Natural Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 (Tree a) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 # |

Instance details

Defined in Data.Functor.Foldable

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 #

Functor f => Recursive (Mu f) Source # |

Instance details

Defined in Data.Functor.Foldable

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 (Nu f) Source # |

Instance details

Defined in Data.Functor.Foldable

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 #

Recursive (NonEmpty a) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 (Maybe a) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 [a] Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 #

Functor f => Recursive (Cofree f a) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 #

Recursive (Either a b) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 w, Functor f) => Recursive (CofreeT f w a) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 ``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]

default embed :: (Generic t, Generic (Base t t), GCoerce (Rep (Base t t)) (Rep t)) => Base t t -> t Source #

#### Instances

Instances details

Corecursive Natural Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 (Tree a) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 # |

Instance details

Defined in Data.Functor.Foldable

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 => Corecursive (Mu f) Source # |

Instance details

Defined in Data.Functor.Foldable

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 (Nu f) Source # |

Instance details

Defined in Data.Functor.Foldable

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 #

Corecursive (NonEmpty a) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 (Maybe a) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 [a] Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 #

Functor f => Corecursive (Cofree f a) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 `F` directly.

Instance details

Defined in Data.Functor.Foldable

Methods

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 # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 #

Corecursive (Either a b) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 w, Functor f) => Corecursive (CofreeT f w a) Source # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 # |

Instance details

Defined in Data.Functor.Foldable

Methods

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 sub-trees 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 sub-tree.

    >>> :{
    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 recursion-scheme, 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 "f-algebra".

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 recursion-schemes 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 pretty-printer 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 side-effects, 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 sub-tree, in addition to the result of folding that sub-tree.

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 sub-tree.

    >>> :{
    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 sub-trees 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 sub-tree 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 sub-tree is provided for each recursive position. Each node in that sub-tree 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 sub-trees. In the Fibonacci example below, the recursive type is `Natural`, which is isomorphic to `[()]`. Our annotated sub-tree 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.

zygo :: Recursive t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a Source #

# 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]

ana Source #

Arguments

:: Corecursive t |
=> (a -> Base t a) | a (Base t)-coalgebra
-> a | seed
-> t | resulting fixed point

An alias for `unfold`.

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

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

# 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]

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

An alias for `refold`.

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

# 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

## Mendler-style recursion-schemes

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

Mendler-style iteration

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

Mendler-style recursion

Since: 5.2.2

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

Mendler-style course-of-value iteration

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

Mendler-style semi-mutual recursion

Since: 5.2.2

mana :: (forall y. (x -> y) -> x -> f y) -> x -> Fix f Source #

Mendler-style coiteration

Since: 5.2.2

mapo :: (forall y. (Fix f -> y) -> (x -> y) -> x -> f y) -> x -> Fix f Source #

Mendler-style corecursion

Since: 5.2.2

mfutu :: (forall y. (f y -> y) -> (x -> y) -> x -> f y) -> x -> Fix f Source #

Mendler-style course-of-values coiteration

Since: 5.2.2

## Fokkinga's recursion-schemes

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

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/

## Generalized recursion-schemes

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

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

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 #

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

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

gapo :: Corecursive t => (b -> Base t b) -> (a -> Base t (Either b 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 #

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

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 #

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 #

distZygo Source #

Arguments

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

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 #

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 #

## 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