Generics.MultiRec.Fold

The definition of generic fold, unfold, paramorphisms. In addition, some combinators that facilitate the construction of algebras.

There are several variants of fold in other modules that are probably easier to use:

• for folds with constant return type, look at Generics.MultiRec.FoldAlgK (or Generics.MultiRec.FoldK),
• for folds with convenient algebras, look at Generics.MultiRec.FoldAlg.

Generic fold and unfold

type Algebra' phi f r = forall ix. phi ix -> f r ix -> r ix

type Algebra phi r = Algebra' phi (PF phi) r

type AlgebraF' phi f g r = forall ix. phi ix -> f r ix -> g (r ix)

type AlgebraF phi g r = AlgebraF' phi (PF phi) g r

fold :: (Fam phi, HFunctor phi (PF phi)) => Algebra phi r -> phi ix -> ix -> r ix

foldM :: (Fam phi, HFunctor phi (PF phi), Monad m) => AlgebraF phi m r -> phi ix -> ix -> m (r ix)

type CoAlgebra' phi f r = forall ix. phi ix -> r ix -> f r ix

type CoAlgebra phi r = CoAlgebra' phi (PF phi) r

type CoAlgebraF' phi f g r = forall ix. phi ix -> r ix -> g (f r ix)

type CoAlgebraF phi g r = CoAlgebraF' phi (PF phi) g r

unfold :: (Fam phi, HFunctor phi (PF phi)) => CoAlgebra phi r -> phi ix -> r ix -> ix

unfoldM :: (Fam phi, HFunctor phi (PF phi), Monad m) => CoAlgebraF phi m r -> phi ix -> r ix -> m ix

type ParaAlgebra' phi f r = forall ix. phi ix -> f r ix -> ix -> r ix

type ParaAlgebra phi r = ParaAlgebra' phi (PF phi) r

type ParaAlgebraF' phi f g r = forall ix. phi ix -> f r ix -> ix -> g (r ix)

type ParaAlgebraF phi g r = ParaAlgebraF' phi (PF phi) g r

para :: (Fam phi, HFunctor phi (PF phi)) => ParaAlgebra phi r -> phi ix -> ix -> r ix

paraM :: (Fam phi, HFunctor phi (PF phi), Monad m) => ParaAlgebraF phi m r -> phi ix -> ix -> m (r ix)

Creating an algebra

type AlgPart f r ix = f r ix -> r ix

type (:->) f g r ix = f r ix -> g r ix infixr 9

(&) :: (AlgPart a :-> (AlgPart b :-> AlgPart (a :+: b))) r ix infixr 5

tag :: AlgPart a r ix -> AlgPart (a :>: ix) r ix'

con :: AlgPart a r ix -> AlgPart (C c a) r ix