Control.Recursion
 Portability non-portable (rank-2 polymorphism, fundeps) Stability experimental Maintainer zednenem@psualum.com
 Contents FoldingUnfoldingTransformingFunctor 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) -> Cons a b -> c
Folding
fold :: Fixpoint f t => (f a -> a) -> t -> a

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

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

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

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

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

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

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

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

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

generalized anamorphisms parameterized by a monad, dual to foldWith

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

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
Methods
 inF :: f t -> t formally, in[f]: f -> mu f outF :: t -> f t formally, in^-1[f]: mu f -> f
Instances
 Functor f => Fixpoint f (Fix f) Fixpoint Unit () Fixpoint Maybe Int Fixpoint Maybe Integer Fixpoint (ConsPair a) [a]
newtype Fix f
Creates a fixpoint for any functor.
Constructors
 In (f (Fix f))
Instances
 Functor f => Fixpoint f (Fix f)
data ConsPair a b
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) -> Cons a b -> c
Deconstructor for ConsPair
Produced by Haddock version 0.6