> 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
Why do you need mutual recursion? What's wrong with:
identity (Sum (Lit 0) a) = identity a
...
identity (Quotient a (Lit 1)) = identity a
identity a = a
Structural recursion ensures that this always terminates.
Dan
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.
------------------------------------------------------------------------
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
