category-extras-0.2: Various modules and constructs inspired by category theory.Source codeContentsIndex
Control.Recursion
Portabilitynon-portable (rank-2 polymorphism, fundeps)
Stabilityexperimental
Maintainerdan.doel@gmail.com
Contents
Folding
Unfolding
Transforming
Dynamic Programming
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).

Several combinators herein ((g_)futu, (g_)chrono, refoldWith, ...) are due to substantial help by Edward Kmett.

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 (Cofree f a) -> a) -> t -> a
g_histo :: (Functor h, Fixpoint f t) => (forall b. f (h b) -> h (f b)) -> (f (Cofree 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
futu :: Fixpoint f t => (a -> f (Free f a)) -> a -> t
g_futu :: (Functor h, Fixpoint f t) => (forall b. h (f b) -> f (h b)) -> (a -> f (Free h a)) -> a -> t
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
refoldWith :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (g c)) -> (forall c. m (e c) -> f (m c)) -> (g (w b) -> b) -> (a -> e (m a)) -> a -> b
chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> b
g_chrono :: (Functor f, Functor m, Functor w) => (forall c. f (w c) -> w (f c)) -> (forall c. m (f c) -> f (m c)) -> (f (Cofree w b) -> b) -> (a -> f (Free m a)) -> a -> b
dyna :: Functor f => (f (Cofree f b) -> b) -> (a -> f a) -> a -> b
g_dyna :: (Functor f, Functor h, Monad m) => (forall c. f (h c) -> h (f c)) -> (forall c. m (e c) -> f (m c)) -> (f (Cofree h b) -> b) -> (a -> e (m a)) -> a -> b
codyna :: Functor f => (f b -> b) -> (a -> f (Free f a)) -> a -> b
g_codyna :: (Functor f, Functor h, Comonad w) => (forall c. f (w c) -> w (g c)) -> (forall c. h (f c) -> f (h c)) -> (g (w b) -> b) -> (a -> f (Free h 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 -> aSource

A generalized foldr, known formally as a catmorphism and written (| f |).

	fold f == refold f outF
	fold f == foldWith (Identity . fmap runIdentity) (f . fmap runIdentity)
para :: Fixpoint f t => (f (t, a) -> a) -> t -> aSource

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

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 (Cofree f a) -> a) -> t -> aSource

Implements course-of-value recursion. At each step, the function receives an F-branching stream (Cofree) 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 (Cofree 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 (Cofree h a) -> a) -> t -> aSource

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

	g_histo g == foldWith (anaCofree (fmap headCofree) (g . fmap tailCofree))
foldWith :: (Fixpoint f t, Comonad w) => (forall b. f (w b) -> w (f b)) -> (f (w a) -> a) -> t -> aSource

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

A generalized unfoldr, known formally as an anamorphism and written [( f )].

	unfold f == refold inF f
	unfold f == unfoldWith (fmap Identity . unIdentity) (fmap Identity . f)
apo :: Fixpoint f t => (a -> f (Either t a)) -> a -> tSource

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

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

Generalized anamorphisms parameterized by a monad, dual to foldWith

futu :: Fixpoint f t => (a -> f (Free f a)) -> a -> tSource

Futumorphism: course of argument coiteration

        futu == chrono (inF . fmap headCofree)
        futu == g_futu id

Example, translated from /Primitive (Co)Recursion and Course-of-Value (Co)Iteration, Categorically/ (http://citeseer.ist.psu.edu/uustalu99primitive.html):

 phi (x:y:zs) = Pair y . inFree . Pair x $ return zs
 exch = futu phi
 l = exch [1..] -- [2,1,4,3,6,5,8,7,10,9..]
g_futu :: (Functor h, Fixpoint f t) => (forall b. h (f b) -> f (h b)) -> (a -> f (Free h a)) -> a -> tSource

Generalized futumorphism

        g_futu m == g_chrono (const Unit) m (inF . fmap headCofree)
        g_futu m == unfoldWith (distribFree m)
Transforming
refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> bSource

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

	refold f g == fold f . unfold g
refoldWith :: (Comonad w, Functor f, Monad m) => (forall c. f (w c) -> w (g c)) -> (forall c. m (e c) -> f (m c)) -> (g (w b) -> b) -> (a -> e (m a)) -> a -> bSource

Generalized hylomorphisms parameterized by both a monad and a comonad. This one combinator subsumes most-if-not-all the other combinators in this library.

e and g are additional functors related to f by natural transformations that have been fused into the distributive laws.

chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> bSource
a chronomorphism, coined by Edward Kmett, subsumes both histo and futumorphisms.
g_chrono :: (Functor f, Functor m, Functor w) => (forall c. f (w c) -> w (f c)) -> (forall c. m (f c) -> f (m c)) -> (f (Cofree w b) -> b) -> (a -> f (Free m a)) -> a -> bSource

Generalized chronomorphism. The recursion functor is separated from the Free and Cofree functors, and related by distributive laws.

        g_chrono w m == refoldWith (distribCofree w) (distribFree m)
Dynamic Programming
dyna :: Functor f => (f (Cofree f b) -> b) -> (a -> f a) -> a -> bSource

Dynamorphisms: a hylomorphism like combinator that captures dynamic programming.

        dyna f g == g_dyna id (fmap Identity . runIdentity) f (fmap Identity . g)
        dyna f g == chrono f (fmap return . g)

Example, translated from Recursion Schemes for Dynamic Programming (http://citeseer.ist.psu.edu/748315.html) section 4.2:

 data Poly a = Term | Single a | Double a a
 instance Functor Poly where
   fmap _ Term = Term
   fmap f (Single a) = Single (f a)
   fmap f (Double a b) = Double (f a) (f b)
 psi 0 = Term
 psi n
   | odd n  = Single (n-1)
   | even n = Double (n-1) (n `div` 2)
 phi Term = 1
 phi (Single n) = n
 phi (Double m n) = m + n
 bp1 = refold phi psi -- hylo version; ineffcient
 zeta 0 = Nil
 zeta n = Pair n (n-1)
 epsilon = headCofree
 theta = tailCofree
 pie x = let (Pair m y) = theta x in y
 pieN 0 x = x
 pieN n x = pieN (n-1) (pie x)
 sigma Nil = Term
 sigma (Pair n x)
   | odd n  = Single (epsilon x)
   | even n = Double (epsilon x) (epsilon (pieN (n`div`2 - 1) x))
 bp2 = dyna (phi . sigma) zeta -- dynamically programmed
g_dyna :: (Functor f, Functor h, Monad m) => (forall c. f (h c) -> h (f c)) -> (forall c. m (e c) -> f (m c)) -> (f (Cofree h b) -> b) -> (a -> e (m a)) -> a -> bSource

Generalized dynamorphism

        g_dyna w == refoldWith (distribCofree w)
codyna :: Functor f => (f b -> b) -> (a -> f (Free f a)) -> a -> bSource
The dual of dynamorphisms.
g_codyna :: (Functor f, Functor h, Comonad w) => (forall c. f (w c) -> w (g c)) -> (forall c. h (f c) -> f (h c)) -> (g (w b) -> b) -> (a -> f (Free h a)) -> a -> bSource
Generalized codynamorphisms.
Functor fixpoints
class Functor f => Fixpoint f t | t -> f whereSource
Methods
inF :: f t -> tSource
formally, in[f]: f -> mu f
outF :: t -> f tSource
formally, in^-1[f]: mu f -> f
show/hide Instances
newtype Fix f Source
Creates a fixpoint for any functor.
Constructors
In (f (Fix f))
show/hide Instances
Functor f => Fixpoint f (Fix f)
data ConsPair a b Source
Fixpoint of lists
Constructors
Nil
Pair a b
show/hide 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 -> cSource
Deconstructor for ConsPair
Produced by Haddock version 2.3.0