
Control.Recursion  Portability  nonportable (rank2 polymorphism, fundeps)  Stability  experimental  Maintainer  dan.doel@gmail.com 





Description 
Provides implementations of catamorphisms (fold),
anamorphisms (unfold), and hylomorphisms (refold),
along with many generalizations implementing various
forms of iteration and coiteration.
Also provided is a type class for transforming a functor
to its fixpoint type and back (Fixpoint), along with
standard functors for natural numbers and lists (ConsPair),
and a fixpoint type for arbitrary functors (Fix).


Synopsis 




Folding



A generalized foldr, known formally as a catmorphism and written ( f ).
fold f == refold f outF
fold f == foldWith (Id . fmap unId) (f . fmap unId)



A variant of fold where the function f also receives the result of the
inner recursive calls. Formally known as a paramorphism and written < f >.
Dual to apo.
para == zygo inF
para f == refold f (fmap (id &&& id) . outF)
para f == f . fmap (id &&& para f) . outF
Example: Computing the factorials.
fact :: Integer > Integer
fact = para g
where
g Nothing = 1
g (Just (n,f)) = f * (n + 1)
 For the base case 0!, g is passed Nothing. (Note that inF Nothing == 0.)
 For subsequent cases (n+1)!, g is passed n and n!.
(Note that inF (Just n) == n + 1.)
Pointfree version: fact = para $ maybe 1 (uncurry (*) . first (+1)).
Example: dropWhile
dropWhile :: (a > Bool) > [a] > [a]
dropWhile p = para f
where
f Nil = []
f (Pair x xs) = if p x then snd xs else x : fst xs
Pointfree version:
dropWhile p = para $ cons [] (\x xs > if p x then snd xs else x : fst xs)



A generalization of para implementing "semimutual" recursion.
Known formally as a zygomorphism and written < f >^g, where g is an
auxiliary function. Dual to g_apo.
zygo g == foldWith (g . fmap fst &&& fmap snd)



Implements courseofvalue recursion. At each step, the function
receives an Fbranching stream (Strf) containing the previous
values. Formally known as a histomorphism and written { f }.
histo == g_histo id
Example: Computing Fibonacci numbers.
fibo :: Integer > Integer
fibo = histo next
where
next :: Maybe (Strf Maybe Integer) > Integer
next Nothing = 0
next (Just (Consf _ Nothing)) = 1
next (Just (Consf m (Just (Consf n _)))) = m + n
 For the base case F(0), next is passed Nothing and returns 0.
(Note that inF Nothing == 0)
 For F(1), next is passed a oneelement stream, and returns 1.
 For subsequent cases F(n), next is passed a the stream
[F(n1), F(n2), ..., F(0)] and returns F(n1)+F(n2).



Generalizes histo to cases where the recursion functor and the
stream functor are distinct. Known as a ghistomorphism.
g_histo g == foldWith (genStrf (fmap hdf) (g . fmap tlf))


foldWith :: (Fixpoint f t, Comonad w) => (forall b. f (w b) > w (f b)) > (f (w a) > a) > t > a  Source 

Generalizes fold, zygo, and g_histo. Formally known as a gcatamorphism
and written ( f )^(w,k), where w is a Comonad and k is a distributive law between
n and the functor f.
The behavior of foldWith is determined by the comonad w.


Unfolding



A generalized unfoldr, known formally as an anamorphism and written [( f )].
unfold f == refold inF f
unfold f == unfoldWith (fmap Id . unId) (fmap Id . f)



apomorphisms, dual to para
apo == g_apo outF
apo f == inF . fmap (id  apo f) . f
Example: Appending a list to another list
append :: [a] > [a] > [a]
append = curry (apo f)
where
f :: ([a],[a]) > ConsPair a (Either [a] ([a],[a]))
f ([], []) = Nil
f ([], y:ys) = Pair y (Left ys)
f (x:xs, ys) = Pair x (Right (xs,ys))



generalized apomorphisms, dual to zygo
g_apo g == unfoldWith (fmap Left . g  fmap Right)


unfoldWith :: (Fixpoint f t, Monad m) => (forall b. m (f b) > f (m b)) > (a > f (m a)) > a > t  Source 

generalized anamorphisms parameterized by a monad, dual to foldWith


Transforming



A generalized map, known formally as a hylomorphism and written [ f, g ].
refold f g == fold f . unfold g


Functor fixpoints



 Methods   formally, in[f]: f > mu f
   formally, in^1[f]: mu f > f

  Instances  



Creates a fixpoint for any functor.
 Constructors   Instances  



Fixpoint of lists
 Constructors   Instances  



Deconstructor for ConsPair


Produced by Haddock version 2.3.0 