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