Daniel Hlynskyi | 16 Jun 2012 23:17
Picon

Simplify (normalize) symbolic polynom-like expression

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)] `.

_______________________________________________
(Continue reading)

Máté Kovács | 17 Jun 2012 00:36
Picon
Gravatar

Re: Simplify (normalize) symbolic polynom-like expression

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
>
(Continue reading)

Daniel Hlynskyi | 17 Jun 2012 07:32
Picon

Re: Simplify (normalize) symbolic polynom-like expression

Not for equality testing, only for prettyprinting. So I want some
simple way to apply all the rules with smallest number of expression
tree traverses

As for ipoly, it looks like CAS. I will use Maxima as CAS and I don't
want to do extra Maxima call for something, that can be easily
(expecting) done in Haskell.

2012/6/17 Máté Kovács <mkovaxx <at> gmail.com>:
> 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.
(Continue reading)

Chaddaï Fouché | 17 Jun 2012 09:36
Picon
Gravatar

Re: Simplify (normalize) symbolic polynom-like expression

On Sat, Jun 16, 2012 at 11:17 PM, Daniel Hlynskyi
<abcz2.uprola <at> gmail.com> wrote:
> Hello.
> 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)] `.

It's because you're doing it in the wrong direction : in a tree always
normalize leaves before you try to normalize branches.

normalize (Sum xs) = case sort . filter (/= I 0) . map normalize $ xs of
  [] -> I 0
  [a] -> a
  ys -> sumPrefix ys
    where
      sumPrefix (I n : I m : ys) = sumPrefix $ I (n+m) : ys
      sumPrefix ys = ys

See how I normalize the elements of xs before anything else.

(Continue reading)

Chaddaï Fouché | 17 Jun 2012 09:37
Picon
Gravatar

Re: Simplify (normalize) symbolic polynom-like expression

On Sun, Jun 17, 2012 at 9:36 AM, Chaddaï Fouché
<chaddai.fouche <at> gmail.com> wrote:
> normalize (Sum xs) = case sort . filter (/= I 0) . map normalize $ xs of
>  [] -> I 0
>  [a] -> a
>  ys -> sumPrefix ys
>    where
>      sumPrefix (I n : I m : ys) = sumPrefix $ I (n+m) : ys
>      sumPrefix ys = ys

Sorry I did this a bit too fast...

> normalize (Sum xs) = case sumPrefix . sort . filter (/= I 0) . map normalize $ xs of
>  [] -> I 0
>  [a] -> a
>  ys -> Sum ys

_______________________________________________
Beginners mailing list
Beginners <at> haskell.org
http://www.haskell.org/mailman/listinfo/beginners
Daniel Hlynskyi | 17 Jun 2012 10:30
Picon

Re: Simplify (normalize) symbolic polynom-like expression

Thanks, that worked!

> Note that this isn't quite the right way to represent a poly if you
want to get to a canonical representation.

Can you expand a bit more on this? It is not classic poly, but
combination of symbolic vars,sums,products and exponentiation
operations (in fact, auto-random-generated)

2012/6/17 Chaddaï Fouché <chaddai.fouche <at> gmail.com>:
> On Sun, Jun 17, 2012 at 9:36 AM, Chaddaï Fouché
> <chaddai.fouche <at> gmail.com> wrote:
>> normalize (Sum xs) = case sort . filter (/= I 0) . map normalize $ xs of
>>  [] -> I 0
>>  [a] -> a
>>  ys -> sumPrefix ys
>>    where
>>      sumPrefix (I n : I m : ys) = sumPrefix $ I (n+m) : ys
>>      sumPrefix ys = ys
>
> Sorry I did this a bit too fast...
>
>> normalize (Sum xs) = case sumPrefix . sort . filter (/= I 0) . map normalize $ xs of
>>  [] -> I 0
>>  [a] -> a
>>  ys -> Sum ys

_______________________________________________
Beginners mailing list
Beginners <at> haskell.org
(Continue reading)


Gmane