Category extrasSource codeContentsIndex
Control.Recursion
Portability non-portable (rank-2 polymorphism, fundeps)
Stability experimental
Maintainer zednenem@psualum.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) -> 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