Control.Recursion
 Portability non-portable (rank-2 polymorphism, fundeps) Stability experimental Maintainer dan.doel@gmail.com
 Contents Folding Unfolding Transforming Functor fixpoints
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
fold :: Fixpoint f t => (f a -> a) -> t -> a
para :: Fixpoint f t => (f (t, a) -> a) -> t -> a
zygo :: Fixpoint f t => (f b -> b) -> (f (b, a) -> a) -> t -> a
histo :: Fixpoint f t => (f (Strf f a) -> a) -> t -> a
g_histo :: (Functor h, Fixpoint f t) => (forall b. f (h b) -> h (f b)) -> (f (Strf h a) -> a) -> t -> a
foldWith :: (Fixpoint f t, Comonad w) => (forall b. f (w b) -> w (f b)) -> (f (w a) -> a) -> t -> a
unfold :: Fixpoint f t => (a -> f a) -> a -> t
apo :: Fixpoint f t => (a -> f (Either t a)) -> a -> t
g_apo :: Fixpoint f t => (b -> f b) -> (a -> f (Either b a)) -> a -> t
unfoldWith :: (Fixpoint f t, Monad m) => (forall b. m (f b) -> f (m b)) -> (a -> f (m a)) -> a -> t
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
class Functor f => Fixpoint f t | t -> f where
 inF :: f t -> t outF :: t -> f t
newtype Fix f = In (f (Fix f))
data ConsPair a b
 = Nil | Pair a b
cons :: c -> (a -> b -> c) -> ConsPair a b -> c
Folding
 fold :: Fixpoint f t => (f a -> a) -> t -> a Source

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)
```
 para :: Fixpoint f t => (f (t, a) -> a) -> t -> a Source

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.)

Point-free 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
```

Point-free version:

``` dropWhile p = para \$ cons [] (\x xs -> if p x then snd xs else x : fst xs)
```
 zygo :: Fixpoint f t => (f b -> b) -> (f (b, a) -> a) -> t -> a Source

A generalization of para implementing "semi-mutual" 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)
```
 histo :: Fixpoint f t => (f (Strf f a) -> a) -> t -> a Source

Implements course-of-value recursion. At each step, the function receives an F-branching 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 one-element stream, and returns 1.
• For subsequent cases F(n), next is passed a the stream [F(n-1), F(n-2), ..., F(0)] and returns F(n-1)+F(n-2).
 g_histo :: (Functor h, Fixpoint f t) => (forall b. f (h b) -> h (f b)) -> (f (Strf h a) -> a) -> t -> a Source

Generalizes histo to cases where the recursion functor and the stream functor are distinct. Known as a g-histomorphism.

```	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 g-catamorphism 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
 unfold :: Fixpoint f t => (a -> f a) -> a -> t Source

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)
```
 apo :: Fixpoint f t => (a -> f (Either t a)) -> a -> t Source

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))
```
 g_apo :: Fixpoint f t => (b -> f b) -> (a -> f (Either b a)) -> a -> t Source

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
 refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b Source

A generalized map, known formally as a hylomorphism and written [| f, g |].

```	refold f g == fold f . unfold g
```
Functor fixpoints
 class Functor f => Fixpoint f t | t -> f where Source
Methods
 inF :: f t -> t Source
formally, in[f]: f -> mu f
 outF :: t -> f t Source
formally, in^-1[f]: mu f -> f Instances
 Fixpoint Maybe Int Fixpoint Maybe Int Fixpoint Maybe Integer Fixpoint Maybe Integer Fixpoint Unit () Fixpoint Unit () Functor f => Fixpoint f (Fix f) Fixpoint (ConsPair a) ([] a) Fixpoint (ConsPair a) ([] a)
 newtype Fix f Source
Creates a fixpoint for any functor.
Constructors
 In (f (Fix f)) Instances
 Functor f => Fixpoint f (Fix f)
 data ConsPair a b Source
Fixpoint of lists
Constructors
 Nil Pair a b Instances
 Functor (ConsPair a) Fixpoint (ConsPair a) ([] a) (Eq a, Eq b) => Eq (ConsPair a b) (Show a, Show b) => Show (ConsPair a b)
 cons :: c -> (a -> b -> c) -> ConsPair a b -> c Source
Deconstructor for ConsPair