[Haskell-cafe] point-free simplification algoritm.
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)
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-----
More information about the Haskell-Cafe
mailing list