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

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

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

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

Provides implementations of Also provided is a type class for transforming a functor
to its fixpoint type and back ( | ||||||||||||||||||||||||||||||||||||

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

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

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

fold :: Fixpoint f t => (f a -> a) -> t -> a | ||||||||||||||||||||||||||||||||||||

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

para :: Fixpoint f t => (f (t, a) -> a) -> t -> a | ||||||||||||||||||||||||||||||||||||

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

zygo :: Fixpoint f t => (f b -> b) -> (f (b, a) -> a) -> t -> a | ||||||||||||||||||||||||||||||||||||

A generalization of zygo g == | ||||||||||||||||||||||||||||||||||||

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 ( histo == 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 g_histo g == | ||||||||||||||||||||||||||||||||||||

foldWith :: (Fixpoint f t, Comonad w) => (forall b . f (w b) -> w (f b)) -> (f (w a) -> a) -> t -> a | ||||||||||||||||||||||||||||||||||||

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

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

unfold :: Fixpoint f t => (a -> f a) -> a -> t | ||||||||||||||||||||||||||||||||||||

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

apo :: Fixpoint f t => (a -> f (Either t a)) -> a -> t | ||||||||||||||||||||||||||||||||||||

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

g_apo :: Fixpoint f t => (b -> f b) -> (a -> f (Either b a)) -> a -> t | ||||||||||||||||||||||||||||||||||||

generalized apomorphisms, dual to g_apo g == | ||||||||||||||||||||||||||||||||||||

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

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

refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b | ||||||||||||||||||||||||||||||||||||

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

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

class Functor f => Fixpoint f t | t -> f where | ||||||||||||||||||||||||||||||||||||

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

newtype Fix f | ||||||||||||||||||||||||||||||||||||

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

data ConsPair a b | ||||||||||||||||||||||||||||||||||||

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

cons :: c -> (a -> b -> c) -> Cons a b -> c | ||||||||||||||||||||||||||||||||||||

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

Produced by Haddock version 0.6 |