[Haskell-cafe] point-free simplification algoritm.

[Stefan Holdermans]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Nino,

> I am also interested in knowing what zygomorphisms and  
> paramorphisms are? and how can u build a gcata?? (a cata for all  
> datatypes).

Regarding paramorphisms:

Consider the catamorphism on the type of Peano naturals,

   data Nat = Zero | Succ Nat

   cataNat     :: a -> (a -> a) -> Nat -> a
   cataNat e f =  cata
     where
       cata Zero     = e
       cata (Succ k) = f (cata k)

Have a look at the case for Succ. Note that cata only operates on the  
immediate child n; it leaves the Succ node itself untouched. This  
makes it quite hard to define structural-recursive functions that  
also need access to the complete node. For instance, a clumsy way to  
define the factorial on Peano naturals is

   fac' :: Nat -> Nat
   fac' =  snd . cataNat e f
     where
       e        = (Zero, Succ Zero)
       f (n, k) = (Succ n, Succ n `times` k)

Paramorphisms are like catamorphisms but provide access to the nodes  
themselves too:

   paraNat     :: a -> (Nat -> a -> a) -> Nat -> a
   paraNat e g =  para
     where
       para Zero       = e
       para n@(Succ k) = g n (para k)

The factorial can now be written as

   fac :: Nat -> Nat
   fac =  paraNat (Succ Zero) times

Another example is the paramorphism on lists:

   paraList     :: b -> (a -> [a] -> b -> b) -> [a] -> b
   paraList e g =  para
     where
       para []       = e
       para (x : xs) = g x xs (para xs)

Regarding generic catamorphisms: check out (datatype) generic  
programming or polytypic programming.

HTH,

   Stefan
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (Darwin)

iD8DBQFD38lLX0lh0JDNIpwRAthxAJ9iSndWFz/FHDiGPqAwMUXFIfbAAgCcCwnd
17Ahn/T8DNx4V8oRsFCFvCM=
=V7lp
-----END PGP SIGNATURE-----