Stefan Holdermans stefan at cs.uu.nl
Tue Jan 31 15:32:11 EST 2006

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

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