[Haskell-cafe] Is there already an abstraction for this?
Dan Weston
westondan at imageworks.com
Mon Sep 22 21:55:26 EDT 2008
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
>
>
More information about the Haskell-Cafe
mailing list