Editing Catamorphisms (section)

== Generalized Catamorphisms ==
Most more advanced recursion schemes for folding structures, such as paramorphisms and zygomorphisms can be seen in a common framework as "generalized" catamorphisms[7]. A generalized catamorphism is defined in terms of an F-W-algebra and a distributive law for the comonad W over the functor F which preserves the structure of the comonad W.

<haskell>
  type Dist f w = forall a. f (w a) -> w (f a) 
  type FWAlgebra f w a = f (w a) -> a 
  g_cata :: (Functor f, Comonad w) => 
          Dist f w -> FWAlgebra f w a -> Mu f -> a 
  g_cata k g = extract . c where 
    c = liftW g . k . fmap (duplicate . c) . outF   
</haskell>
However, a generalized catamorphism can be shown to add no more expressive power to the concept of a catamorphism. That said the separation of a number of the "book keeping" concerns by isolating them in a reusable distributive law can ease the development of F-W-algebras.

We can transform an F-W-algebra into an F-algebra by including the comonad in the carrier for the algebra and then extracting after we perform this somewhat more stylized catamorphism:

<haskell>
  lowerAlgebra :: (Functor f, Comonad w) => 
                Dist f w -> FWAlgebra f w a -> Algebra f (w a) 
  lowerAlgebra k phi = liftW phi . k . fmap duplicate 
  g_cata :: (Functor f, Comonad w) => 
          Dist f w -> FWAlgebra f w a -> Mu f -> a 
  g_cata k phi = extract . cata (lowerGAlgebra k phi)   
</haskell>

and we can trivially transform an Algebra into an F-W-Algebra by mapping the counit of the comonad over F. Then using the trivial identity functor, we can represent every catamorphism as a generalized-catamorphism. 
<haskell>
  liftAlgebra :: (Functor f, Comonad w) => 
    Algebra f a -> FWAlgebra f w a

  liftAlgebra phi = phi . fmap extract


  cata :: Functor f => Algebra f a -> Mu f -> a
  cata f = g_cata (Identity . fmap runIdentity) (liftAlgebra f)
</haskell>
Between these two definitions we can see that a generalized catamorphism does not increase the scope of a catamorphism to encompass any more operations, it simply further stylizes the pattern of recursion.