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

[Dan Weston]

Oops, never mind. This is just the shallow application you referred to. 
Too fast with that send button!

Dan Weston wrote:
> 
>  > 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
> 
>