Data.Functor.Foldable

Base functors for fixed points

type family Base t :: * -> *

Instances

type Base [a] = Prim [a]

type Base (Maybe a) = Const (Maybe a)

Example boring stub for non-recursive data types

type Base (Nu f) = f

type Base (Mu f) = f

type Base (Fix f) = f

type Base (Either a b) = Const (Either a b)

Example boring stub for non-recursive data types

Fixed points

newtype Fix f

Constructors

Fix (f (Fix f))

Instances

Eq (f (Fix f)) => Eq (Fix f)

Ord (f (Fix f)) => Ord (Fix f)

Read (f (Fix f)) => Read (Fix f)

Show (f (Fix f)) => Show (Fix f)

Functor f => Unfoldable (Fix f)

Functor f => Foldable (Fix f)

Typeable ((* -> *) -> *) Fix

type Base (Fix f) = f

newtype Mu f

Constructors

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

Instances

(Functor f, Eq (f (Fix f)), Eq (Fix f)) => Eq (Mu f)

(Functor f, Ord (f (Fix f)), Ord (Fix f)) => Ord (Mu f)

(Functor f, Read (f (Fix f)), Read (Fix f)) => Read (Mu f)

(Functor f, Show (f (Fix f)), Show (Fix f)) => Show (Mu f)

Functor f => Unfoldable (Mu f)

Functor f => Foldable (Mu f)

type Base (Mu f) = f

data Nu f where

Constructors

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

Instances

(Functor f, Eq (f (Fix f)), Eq (Fix f)) => Eq (Nu f)

(Functor f, Ord (f (Fix f)), Ord (Fix f)) => Ord (Nu f)

(Functor f, Read (f (Fix f)), Read (Fix f)) => Read (Nu f)

(Functor f, Show (f (Fix f)), Show (Fix f)) => Show (Nu f)

Functor f => Unfoldable (Nu f)

Functor f => Foldable (Nu f)

type Base (Nu f) = f

data family Prim t :: * -> *

Instances

Functor (Prim [a])

(Eq a, Eq b) => Eq (Prim [a] b)

(Ord a, Ord b) => Ord (Prim [a] b)

(Read a, Read b) => Read (Prim [a] b)

(Show a, Show b) => Show (Prim [a] b)

data Prim [a]

• = Cons a b
• | Nil

Folding

class Functor (Base t) => Foldable t where

Minimal complete definition

project

Methods

project :: t -> Base t t

cata

Arguments

:: (Base t a -> a)

a (Base t)-algebra

-> t

fixed point

-> a

result

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

gpara :: (Unfoldable t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> (Base t (EnvT t w a) -> a) -> t -> a

prepro :: Unfoldable t => (forall b. Base t b -> Base t b) -> (Base t a -> a) -> t -> a

Fokkinga's prepromorphism

gprepro :: (Unfoldable 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

Instances

Foldable [a]

Foldable (Maybe a)

Functor f => Foldable (Nu f)

Functor f => Foldable (Mu f)

Functor f => Foldable (Fix f)

Foldable (Either a b)

Combinators

gapo :: Unfoldable t => (b -> Base t b) -> (a -> Base t (Either b a)) -> a -> t

gcata

Arguments

:: (Foldable t, Comonad w)

=> (forall b. Base t (w b) -> w (Base t b))

a distributive law

-> (Base t (w a) -> a)

a (Base t)-w-algebra

-> t

fixed point

-> a

A generalized catamorphism

zygo :: Foldable t => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a

gzygo :: (Foldable t, Comonad w) => (Base t b -> b) -> (forall c. Base t (w c) -> w (Base t c)) -> (Base t (EnvT b w a) -> a) -> t -> a

histo :: Foldable t => (Base t (Cofree (Base t) a) -> a) -> t -> a

Course-of-value iteration

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

futu :: Unfoldable t => (a -> Base t (Free (Base t) a)) -> a -> t

Distributive laws

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

distPara :: Unfoldable t => Base t (t, a) -> (t, Base t a)

distParaT :: (Unfoldable t, Comonad w) => (forall b. Base t (w b) -> w (Base t b)) -> Base t (EnvT t w a) -> EnvT t w (Base t a)

distZygo

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)

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 (Cofree h a) -> Cofree h (f a)

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

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

Unfolding

class Functor (Base t) => Unfoldable t where

Minimal complete definition

embed

Methods

embed :: Base t t -> t

ana

Arguments

:: (a -> Base t a)

a (Base t)-coalgebra

-> a

seed

-> t

resulting fixed point

apo :: Foldable t => (a -> Base t (Either t a)) -> a -> t

postpro :: Foldable t => (forall b. Base t b -> Base t b) -> (a -> Base t a) -> a -> t

Fokkinga's postpromorphism

gpostpro :: (Foldable 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

A generalized postpromorphism

Instances

Unfoldable [a]

Unfoldable (Maybe a)

Functor f => Unfoldable (Nu f)

Functor f => Unfoldable (Mu f)

Functor f => Unfoldable (Fix f)

Unfoldable (Either a b)

Combinators

gana

Arguments

:: (Unfoldable t, Monad m)

=> (forall b. m (Base t b) -> Base t (m b))

a distributive law

-> (a -> Base t (m a))

a (Base t)-m-coalgebra

-> a

seed

-> t

A generalized anamorphism

Distributive laws

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

distApo :: Foldable 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)

Refolding

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

ghylo :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (f c)) -> (forall d. m (f d) -> f (m d)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b

A generalized hylomorphism

Changing representation

refix :: (Foldable s, Unfoldable t, Base s ~ Base t) => s -> t

Common names

fold :: Foldable t => (Base t a -> a) -> t -> a

gfold

Arguments

:: (Foldable t, Comonad w)

=> (forall b. Base t (w b) -> w (Base t b))

a distributive law

-> (Base t (w a) -> a)

a (Base t)-w-algebra

-> t

fixed point

-> a

A generalized catamorphism

unfold :: Unfoldable t => (a -> Base t a) -> a -> t

gunfold

Arguments

:: (Unfoldable t, Monad m)

=> (forall b. m (Base t b) -> Base t (m b))

a distributive law

-> (a -> Base t (m a))

a (Base t)-m-coalgebra

-> a

seed

-> t

A generalized anamorphism

refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b

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

A generalized hylomorphism

Mendler-style

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

Mendler-style iteration

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

Mendler-style course-of-value iteration

Elgot (co)algebras

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

Elgot algebras

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

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

Zygohistomorphic prepromorphisms

zygoHistoPrepro :: (Unfoldable t, Foldable t) => (Base t b -> b) -> (forall c. Base t c -> Base t c) -> (Base t (EnvT b (Cofree (Base t)) a) -> a) -> t -> a

Zygohistomorphic prepromorphisms:

A corrected and modernized version of http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms