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
Description
Synopsis
- type family Base t :: * -> *
- data ListF a b
- class Functor ( Base t) => Recursive t where
- class Functor ( Base t) => Corecursive t where
- fold :: Recursive t => ( Base t a -> a) -> t -> a
- cata :: Recursive t => ( Base t a -> a) -> t -> a
- cataA :: Recursive t => ( Base t (f a) -> f a) -> t -> f a
- para :: Recursive t => ( Base t (t, a) -> a) -> t -> a
- histo :: Recursive t => ( Base t ( Cofree ( Base t) a) -> a) -> t -> a
- zygo :: Recursive t => ( Base t b -> b) -> ( Base t (b, a) -> a) -> t -> a
- unfold :: Corecursive t => (a -> Base t a) -> a -> t
- ana :: Corecursive t => (a -> Base t a) -> a -> t
- apo :: Corecursive t => (a -> Base t ( Either t a)) -> a -> t
- futu :: Corecursive t => (a -> Base t ( Free ( Base t) a)) -> a -> t
- refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
- hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
- chrono :: Functor f => (f ( Cofree f b) -> b) -> (a -> f ( Free f a)) -> a -> b
- refix :: ( Recursive s, Corecursive t, Base s ~ Base t) => s -> t
- hoist :: ( Recursive s, Corecursive t) => ( forall a. Base s a -> Base t a) -> s -> t
- transverse :: ( Recursive s, Corecursive t, Functor f) => ( forall a. Base s (f a) -> f ( Base t a)) -> s -> f t
- cotransverse :: ( Recursive s, Corecursive t, Functor f) => ( forall a. f ( Base s a) -> Base t (f a)) -> f s -> t
- mcata :: ( forall y. (y -> c) -> f y -> c) -> Fix f -> c
- mpara :: ( forall y. (y -> c) -> (y -> Fix f) -> f y -> c) -> Fix f -> c
- mhisto :: ( forall y. (y -> c) -> (y -> f y) -> f y -> c) -> Fix f -> c
- mzygo :: ( forall y. (y -> b) -> f y -> b) -> ( forall y. (y -> c) -> (y -> b) -> f y -> c) -> Fix f -> c
- mana :: ( forall y. (x -> y) -> x -> f y) -> x -> Fix f
- mapo :: ( forall y. ( Fix f -> y) -> (x -> y) -> x -> f y) -> x -> Fix f
- mfutu :: ( forall y. (f y -> y) -> (x -> y) -> x -> f y) -> x -> Fix f
- prepro :: ( Recursive t, Corecursive t) => ( forall b. Base t b -> Base t b) -> ( Base t a -> a) -> t -> a
- postpro :: ( Corecursive t, Recursive t) => ( forall b. Base t b -> Base t b) -> (a -> Base t a) -> a -> t
- elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a
- coelgot :: Functor f => ((a, f b) -> b) -> (a -> f a) -> a -> b
- gfold :: ( Recursive t, Comonad w) => ( forall b. Base t (w b) -> w ( Base t b)) -> ( Base t (w a) -> a) -> t -> a
- gcata :: ( Recursive t, Comonad w) => ( forall b. Base t (w b) -> w ( Base t b)) -> ( Base t (w a) -> a) -> t -> a
- gpara :: ( Recursive t, Corecursive t, Comonad w) => ( forall b. Base t (w b) -> w ( Base t b)) -> ( Base t ( EnvT t w a) -> a) -> t -> a
- ghisto :: ( Recursive t, Comonad w) => ( forall b. Base t (w b) -> w ( Base t b)) -> ( Base t ( CofreeT ( Base t) w a) -> a) -> t -> a
- gzygo :: ( Recursive t, Comonad w) => ( Base t b -> b) -> ( forall c. Base t (w c) -> w ( Base t c)) -> ( Base t ( EnvT b w a) -> a) -> t -> a
- gunfold :: ( Corecursive t, Monad m) => ( forall b. m ( Base t b) -> Base t (m b)) -> (a -> Base t (m a)) -> a -> t
- gana :: ( Corecursive t, Monad m) => ( forall b. m ( Base t b) -> Base t (m b)) -> (a -> Base t (m a)) -> a -> t
- gapo :: Corecursive t => (b -> Base t b) -> (a -> Base t ( Either b a)) -> a -> t
- gfutu :: ( Corecursive t, Functor m, Monad m) => ( forall b. m ( Base t b) -> Base t (m b)) -> (a -> Base t ( FreeT ( Base t) m a)) -> a -> t
- grefold :: ( Comonad w, Functor f, Monad m) => ( forall c. f (w c) -> w (f c)) -> ( forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b
- ghylo :: ( Comonad w, Functor f, Monad m) => ( forall c. f (w c) -> w (f c)) -> ( forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b
- gchrono :: ( Functor f, Functor w, Functor m, Comonad w, Monad m) => ( forall c. f (w c) -> w (f c)) -> ( forall c. m (f c) -> f (m c)) -> (f ( CofreeT f w b) -> b) -> (a -> f ( FreeT f m a)) -> a -> b
- gprepro :: ( Recursive t, Corecursive t, Comonad w) => ( forall b. Base t (w b) -> w ( Base t b)) -> ( forall c. Base t c -> Base t c) -> ( Base t (w a) -> a) -> t -> a
- gpostpro :: ( Corecursive t, Recursive t, Monad m) => ( forall b. m ( Base t b) -> Base t (m b)) -> ( forall c. Base t c -> Base t c) -> (a -> Base t (m a)) -> a -> t
- distCata :: Functor f => f ( Identity a) -> Identity (f a)
- distPara :: Corecursive t => Base t (t, a) -> (t, Base t a)
- distParaT :: ( Corecursive t, Comonad w) => ( forall b. Base t (w b) -> w ( Base t b)) -> Base t ( EnvT t w a) -> EnvT t w ( Base t a)
- distHisto :: Functor f => f ( Cofree f a) -> Cofree f (f a)
- distGHisto :: ( Functor f, Functor h) => ( forall b. f (h b) -> h (f b)) -> f ( CofreeT f h a) -> CofreeT f h (f a)
- distZygo :: Functor f => (f b -> b) -> f (b, a) -> (b, f a)
- distZygoT :: ( Functor f, Comonad w) => (f b -> b) -> ( forall c. f (w c) -> w (f c)) -> f ( EnvT b w a) -> EnvT b w (f a)
- distAna :: Functor f => Identity (f a) -> f ( Identity a)
- distApo :: Recursive t => Either t ( Base t a) -> Base t ( Either t a)
- distGApo :: Functor f => (b -> f b) -> Either b (f a) -> f ( Either b a)
- distGApoT :: ( Functor f, Functor m) => (b -> f b) -> ( forall c. m (f c) -> f (m c)) -> ExceptT b m (f a) -> f ( ExceptT b m a)
- distFutu :: Functor f => Free f (f a) -> f ( Free f a)
- distGFutu :: ( Functor f, Functor h) => ( forall b. h (f b) -> f (h b)) -> FreeT f h (f a) -> f ( FreeT f h a)
- zygoHistoPrepro :: ( Corecursive t, Recursive t) => ( Base t b -> b) -> ( forall c. Base t c -> Base t c) -> ( Base t ( EnvT b ( Cofree ( Base t)) a) -> a) -> t -> a
Base functors
type family Base t :: * -> * Source #
Obtain the base functor for a recursive datatype.
The core idea of this library is that instead of writing recursive functions on a recursive datatype, we prefer to write 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
dataListF
a b =Nil
|Cons
a b type instanceBase
[a] =ListF
a
The relationship between those two types is that if we replace
b
with
, we obtain a type which is isomorphic to
ListF
a
[a]
.
Instances
type Base Natural Source # | |
Defined in Data.Functor.Foldable |
|
type Base [a] Source # | |
Defined in Data.Functor.Foldable |
|
type Base ( Maybe a) Source # |
Example boring stub for non-recursive data types |
type Base ( NonEmpty a) Source # | |
Defined in Data.Functor.Foldable |
|
type Base ( Tree a) Source # | |
Defined in Data.Functor.Foldable |
|
type Base ( Fix f) Source # | |
Defined in Data.Functor.Foldable |
|
type Base ( Mu f) Source # | |
Defined in Data.Functor.Foldable |
|
type Base ( Nu f) Source # | |
Defined in Data.Functor.Foldable |
|
type Base ( Either a b) Source # |
Example boring stub for non-recursive data types |
type Base ( Cofree f a) Source # |
Cofree comonads are Recursive/Corecursive |
Defined in Data.Functor.Foldable |
|
type Base ( F f a) Source # |
Church encoded free monads are Recursive/Corecursive, in the same way that
|
Defined in Data.Functor.Foldable |
|
type Base ( Free f a) Source # |
Free monads are Recursive/Corecursive |
Defined in Data.Functor.Foldable |
|
type Base ( FreeT f m a) Source # |
Free transformations of monads are Recursive/Corecursive |
Defined in Data.Functor.Foldable |
|
type Base ( CofreeT f w a) Source # |
Cofree tranformations of comonads are Recursive/Corecusive |
Defined in Data.Functor.Foldable |
Base functor of
[]
.
Instances
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
.
If that unrolled value is a
ListF
a [a]
Cons
, it contains another
[a]
which can be
unrolled as well, and so on.
Typically,
Recursive
types also have a
Corecursive
instance, in which
case
project
and
embed
are inverses.
Minimal complete definition
Nothing
Methods
project :: t -> Base t t Source #
Unroll a single recursion layer.
>>>
project [1,2,3]
Cons 1 [2,3]
Instances
Recursive Natural Source # | |
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 [a] Source # | |
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 # |
|
Recursive ( Maybe a) Source # | |
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 ( NonEmpty a) Source # | |
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 ( Tree a) Source # | |
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 # | |
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 # | |
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 # | |
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 ( Either a b) Source # | |
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 f => Recursive ( Cofree f a) Source # | |
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 ( F f a) Source # | |
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 # |
|
Functor f => Recursive ( Free f a) Source # | |
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 m, Functor f) => Recursive ( FreeT f m a) Source # | |
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 # |
|
( Functor w, Functor f) => Recursive ( CofreeT f w a) Source # | |
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 # |
class Functor ( Base t) => Corecursive t where Source #
A recursive datatype which can be rolled up one recursion layer at a time.
For example, a value of type
can be rolled up into a
ListF
a [a]
[a]
.
This
[a]
can then be used in a
Cons
to construct another
,
which can be rolled up as well, and so on.
ListF
a [a]
Typically,
Corecursive
types also have a
Recursive
instance, in which
case
embed
and
project
are inverses.
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]
Instances
Corecursive Natural Source # | |
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 [a] Source # | |
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 # |
|
Corecursive ( Maybe a) Source # | |
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 ( NonEmpty a) Source # | |
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 ( Tree a) Source # | |
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 # | |
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 # | |
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 # | |
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 ( Either a b) Source # | |
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 f => Corecursive ( Cofree f a) Source # | |
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 ( F f a) Source # | |
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 # |
|
Functor f => Corecursive ( Free f a) Source # |
It may be better to work with the instance for
|
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 m, Functor f) => Corecursive ( FreeT f m a) Source # | |
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 # |
|
( Functor w, Functor f) => Corecursive ( CofreeT f w a) Source # | |
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 # |
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.
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]
Arguments
:: Corecursive t | |
=> (a -> Base t a) |
a (Base t)-coalgebra |
-> a |
seed |
-> t |
resulting fixed point |
An alias for
unfold
.
Combining unfolds and folds
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b Source #
An optimized version of
fold f . unfold g
.
Useful when your recursion structure is shaped like a particular recursive datatype, but you're neither consuming nor producing that recursive datatype. For example, the recursion structure of quick sort is a binary tree, but its input and output is a list, not a binary tree.
>>>
data BinTreeF a b = Tip | Branch b a b deriving (Functor)
>>>
:{
>>>
let quicksort :: Ord a => [a] -> [a]
>>>
quicksort = refold merge split where
>>>
split [] = Tip
>>>
split (x:xs) = let (l, r) = partition (<x) xs in Branch l x r
>>>
>>>
merge Tip = []
>>>
merge (Branch l x r) = l ++ [x] ++ r
>>>
:}
>>>
quicksort [1,5,2,8,4,9,8]
[1,2,4,5,8,8,9]
Changing representation
refix :: ( Recursive s, Corecursive t, Base s ~ Base t) => s -> t Source #
Convert from one recursive representation to another.
>>>
refix ["foo", "bar"] :: Fix (ListF String)
Fix (Cons "foo" (Fix (Cons "bar" (Fix Nil))))
hoist :: ( Recursive s, Corecursive t) => ( forall a. Base s a -> Base t a) -> s -> t Source #
Convert from one recursive type to another.
>>>
showTree $ hoist (\(NonEmptyF h t) -> NodeF [h] (maybeToList t)) ( 'a' :| "bcd")
(a (b (c d)))
transverse :: ( Recursive s, Corecursive t, Functor f) => ( forall a. Base s (f a) -> f ( Base t a)) -> s -> f t Source #
An effectful version of
hoist
.
Properties:
transverse
sequenceA
=pure
Examples:
The weird type of first argument allows user to decide an order of sequencing:
>>>
transverse (\x -> print (void x) *> sequence x) "foo" :: IO String
Cons 'f' () Cons 'o' () Cons 'o' () Nil "foo"
>>>
transverse (\x -> sequence x <* print (void x)) "foo" :: IO String
Nil Cons 'o' () Cons 'o' () Cons 'f' () "foo"
cotransverse :: ( Recursive s, Corecursive t, Functor f) => ( forall a. f ( Base s a) -> Base t (f a)) -> f s -> t Source #
A coeffectful version of
hoist
.
Properties:
cotransverse
distAna
=runIdentity
Examples:
Stateful transformations:
>>>
:{
cotransverse (\(u, b) -> case b of Nil -> Nil Cons x a -> Cons (if u then toUpper x else x) (not u, a)) (True, "foobar") :: String :} "FoObAr"
We can implement a variant of
zipWith
>>>
data Pair a = Pair a a deriving Functor
>>>
:{
let zipWith' :: forall a b. (a -> a -> b) -> [a] -> [a] -> [b] zipWith' f xs ys = cotransverse g (Pair xs ys) where g :: Pair (ListF a c) -> ListF b (Pair c) g (Pair Nil _) = Nil g (Pair _ Nil) = Nil g (Pair (Cons x a) (Cons y b)) = Cons (f x y) (Pair a b) :}
>>>
zipWith' (*) [1,2,3] [4,5,6]
[4,10,18]
>>>
zipWith' (*) [1,2,3] [4,5,6,8]
[4,10,18]
>>>
zipWith' (*) [1,2,3,3] [4,5,6]
[4,10,18]
Advanced usage
Mendler-style recursion-schemes
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
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
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
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 #
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
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
gfutu :: ( Corecursive t, Functor m, Monad m) => ( forall b. m ( Base t b) -> Base t (m b)) -> (a -> Base t ( FreeT ( Base t) m a)) -> a -> t Source #
grefold :: ( Comonad w, Functor f, Monad m) => ( forall c. f (w c) -> w (f c)) -> ( forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b Source #
A generalized hylomorphism
ghylo :: ( Comonad w, Functor f, Monad m) => ( forall c. f (w c) -> w (f c)) -> ( forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b Source #
A generalized hylomorphism
gchrono :: ( Functor f, Functor w, Functor m, Comonad w, Monad m) => ( forall c. f (w c) -> w (f c)) -> ( forall c. m (f c) -> f (m c)) -> (f ( CofreeT f w b) -> b) -> (a -> f ( FreeT f m a)) -> a -> b Source #
gprepro :: ( Recursive t, Corecursive t, Comonad w) => ( forall b. Base t (w b) -> w ( Base t b)) -> ( forall c. Base t c -> Base t c) -> ( Base t (w a) -> a) -> t -> a Source #
gpostpro :: ( Corecursive t, Recursive t, Monad m) => ( forall b. m ( Base t b) -> Base t (m b)) -> ( forall c. Base t c -> Base t c) -> (a -> Base t (m a)) -> a -> t Source #
A generalized postpromorphism
distParaT :: ( Corecursive t, Comonad w) => ( forall b. Base t (w b) -> w ( Base t b)) -> Base t ( EnvT t w a) -> EnvT t w ( Base t a) Source #
distGHisto :: ( Functor f, Functor h) => ( forall b. f (h b) -> h (f b)) -> f ( CofreeT f h a) -> CofreeT f h (f a) Source #
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 #
distGApoT :: ( Functor f, Functor m) => (b -> f b) -> ( forall c. m (f c) -> f (m c)) -> ExceptT b m (f a) -> f ( ExceptT b m a) Source #
distGFutu :: ( Functor f, Functor h) => ( forall b. h (f b) -> f (h b)) -> FreeT f h (f a) -> f ( FreeT f h a) Source #
Zygohistomorphic prepromorphisms
zygoHistoPrepro :: ( Corecursive t, Recursive t) => ( Base t b -> b) -> ( forall c. Base t c -> Base t c) -> ( Base t ( EnvT b ( Cofree ( Base t)) a) -> a) -> t -> a Source #
Zygohistomorphic prepromorphisms:
A corrected and modernized version of http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms