[Haskell-beginners] Simplify (normalize) symbolic polynom-like expression

[Máté Kovács]

Hi Daniel,

It depends on what you want to use the normalized / canonical form for.

If it's to reduce semantic equivalence testing to simple syntactic
equality, e.g.
(A == B) = (canonize(A) == canonize(B)),
then you could just use the fully expanded form, which isn't really
simplification. :)

I'm doing something similar here (for polynomial expressions over an
inner product space):
https://github.com/mkovacs/ipoly/blob/master/Poly.hs

Cheers,
Máté

On Sat, Jun 16, 2012 at 2:17 PM, Daniel Hlynskyi <abcz2.uprola at gmail.com> wrote:
> Hello.
>
> I am new to typefull programming, so I've got a question.
> I have a simple mathematical expression (addition, product and
> exponentiation only):
>
>> data Expr = I Int -- integer constant
>>           | V -- symbolic variable
>>           | Sum [Expr]
>>           | Prod [Expr]
>>           | Pow Expr Expr
>
> What I want is normalize\simplify this expression. Eg `Prod [Pow V (I
> 0), Pow V (I 1)] ` must be simplified to just `V`. What techniques
> should I use to write `normalize` function?
> Simplification rules are quite simple:
>
>> normalize (Sum [a]) = normalize a
>> normalize (Sum xs) | (I 0) `elem` xs = map nomalize . Sum $ filter (/= I 0) xs
>>                          | otherwise = map normalize xs
>> normalize (Prod xs) | (I 0) `elem` xs = I 0
>> normalize (Prod xs) | (I 1) `elem` xs = map nomalize . Prod $ filter (/= I 1) xs
>>                          | otherwise = map normalize xs
>> normalize (Pow a (I 0)) = I 1
>> normalize (Pow a (I 1)) = normalize a
>
> and so on. But rules like theese cannot simplify some expressions, for
> example, `Prod [Pow V (I 0), Pow V (I 1)] `.
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners