| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Description | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Provides implementations of Also provided is a type class for transforming a functor
to its fixpoint type and back ( Several combinators herein ((g_)futu, (g_)chrono, refoldWith, ...) are due to substantial help by Edward Kmett. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Synopsis | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Folding | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

A generalized fold f == | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

A variant of para == 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: Example: 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 zygo g == | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Implements course-of-value recursion. At each step, the function
receives an F-branching stream ( histo == 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).
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Generalizes g_histo g == | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Generalizes The behavior of | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Unfolding | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

A generalized unfold f == | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

apo == 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 g_apo g == | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Generalized anamorphisms parameterized by a monad, dual to | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Futumorphism: course of argument coiteration futu == 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..] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Generalized futumorphism g_futu m == | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Transforming | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

A generalized refold f g == | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Generalized hylomorphisms parameterized by both a monad and a comonad. This one combinator subsumes most-if-not-all the other combinators in this library. -
`w = Identity`yields`unfoldWith` -
`m = Identity`yields`foldWith` -
`Free m`and`Cofree w`yields`g_chrono`, and therefore`g_histo`and`g_futu`
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

a chronomorphism, coined by Edward Kmett, subsumes both histo and futumorphisms. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Generalized chronomorphism. The recursion functor is separated from the Free and Cofree functors, and related by distributive laws. g_chrono w m == | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Dynamic Programming | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Dynamorphisms: a hylomorphism like combinator that captures dynamic programming. dyna f g == Example, translated from 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Generalized dynamorphism g_dyna w == | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

The dual of dynamorphisms. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Generalized codynamorphisms. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Functor fixpoints | ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Deconstructor for ConsPair
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||

Produced by Haddock version 2.3.0 |