wren ng thornton wren at freegeek.org
Wed Sep 24 00:10:29 EDT 2008

```Jeremy Shaw wrote:
>> -- |Deep map of an expression.
>> eMap :: (Expr -> Expr) -> Expr -> Expr
>> eMap f (Sum a b) = f (Sum (eMap f a) (eMap f b))
>> eMap f (Difference a b) = f (Difference (eMap f a) (eMap f b))
>> eMap f (Product a b) = f (Product (eMap f a) (eMap f b))
>> eMap f (Quotient a b) = f (Quotient (eMap f a) (eMap f b))
>> eMap f (Var v) = f (Var v)
>> eMap f (Lit i) = f (Lit i)

Jake beat me to the punch, but this is exactly a catamorphism[1].
Generally ---as in, "with full generality"--- this is phrased in terms
of recursion over the least fixed point of a functor (as presented by

The short explanation is that |cata f| applies |f| over a recursive
datastructure once at each level from the bottom up. A fairly trivial
example of this is the |maybe| function for Maybe, an easy non-trivial
example is the |foldr| function over lists[2]. Your code is giving the
version for binary trees (with Var/Lit serving as []/Nothing to
terminate the recursion).

A few months ago vicky wrote some code to automatically generate
catamorphisms at a particular recursive type[3], though I can't say that
it'd be very helpful if you didn't already know what was going on. In
addition to Edward Kmett's work, Wouter Swierstra's _Data Types a la
Carte_[4] may be helpful to work through.

In the end you'll probably just want to stick with the above, unless you
really have something to gain by adding in the additional generality of
category-extras or DTalC. Things you may wish to gain: a better
ability to open up the Expr coproduct; higher-order aesthetics.

[2] Though the Prelude/Data.List version of that abstract function
reifies the two bodies of "f" as two separate arguments. Similarly for
|maybe|. In general there's a body of f for each branch of the
union/coproduct.

[3] http://hpaste.org/7682

--
Live well,
~wren
```