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
Jake), but your version is more direct about what's going on.
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
understanding of category theory; other recursion patterns for free;
ability to open up the Expr coproduct; higher-order aesthetics.
[1] http://comonad.com/reader/2008/catamorphism
[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
[4] http://wadler.blogspot.com/2008/02/data-types-la-carte.html
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
