This (recent) paper describes a very interesting way to perform generic term rewriting: http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-020.pdf On Sep 23, 2008, at 3:46 AM, Jeremy Shaw wrote:
Hello,
I am trying to figure out if there is an existing abstraction I am missing here.
I have an expression data-type:
data Expr = Quotient Expr Expr | Product Expr Expr | Sum Expr Expr | Difference Expr Expr | Lit Double | Var Char deriving (Eq, Ord, Data, Typeable, Read, Show)
And I want to write a function that will take an expression and automatically apply the identity laws to simplify the expression.
The basic identity laws are:
a + 0 = a a * 1 = a
I can implement these with some 'sugar' as:
identity (Sum (Lit 0) a) = a identity (Sum a (Lit 0)) = a identity (Difference a (Lit 0)) = a identity (Product a (Lit 1)) = a identity (Product (Lit 1) a) = a identity (Quotient a (Lit 1)) = a identity a = a
This works fine when the identity only needs to be applied to the root of the expression tree:
*Main> ppExpr $ identity (expr "1 + 0") 1
But for more complicated trees it does not fully apply the identity laws:
*Main> ppExpr $ identity (expr "0 + (0 + 0) + (0 + 0)") ((0 + 0) + (0 + 0))
What we need to do is first apply the identity function to the children, and then apply them to the parent of the updated children. A first attempt would be to extend the identity function like this:
identity (Sum a b) = identity (Sum (identity a) (identity b))
However, that will not terminate because that same case will keep matching over and over. Another approach is to have two mutually recursive functions like:
identity' (Sum (Lit 0) a) = identityRec a identity' (Sum a (Lit 0)) = identityRec a identity' a = a
identityRec (Sum a b) = identity' (Sum (identity' a) (identity' b))
This prevents non-termination, but you have to be careful about calling identity' vs identityRec or you will either re-introduce non-termination, or you may not fully apply the identity laws.
Another option to create a helper function like:
-- |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)
Now we can easily apply the identity law recursively like:
deepIdentity :: Expr -> Expr deepIdentity = eMap identity
*Main> ppExpr (deepIdentity (expr "0 + (0 + 0) + (0 + 0)")) 0
Sweet!
But, having to write eMap out by hand like that somehow feels wrong -- as if I am missing some additional abstraction. In some respects eMap is like a Functor, but not quite. I expect there is a way to implement eMap using Data.Generics, which is perhaps better, but I still feel like that is missing something?
Anyway, I just thought I would ask in case someone recognized this pattern and could point me in the right direction. I have attached a working example program you can play with.
I would also be interested in alternative approaches besides the ones I outlined.
thanks! j.
...