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

[Dan Weston]

 > 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe