|
Control.Recursion | Portability | non-portable (rank-2 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.)
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)
|
|
|
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)
|
|
|
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).
|
|
|
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
|
|
|
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 |