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

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

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.

• Id recovers fold
• ((,) a) recovers zygo (and para)
• Strf recovers g_histo (and histo)

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)

generalized anamorphisms parameterized by a monad, dual to foldWith

• Id recovers unfold
• (Either a) recovers g_apo (and apo)

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

refold f g == fold f . unfold g