Dan Weston westondan at imageworks.com
Mon Sep 22 21:54:04 EDT 2008

``` > 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.
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________