[Haskell-cafe] Is there already an abstraction for this?

[wren ng thornton]

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