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)] `.
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@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@haskell.org http://www.haskell.org/mailman/listinfo/beginners
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@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@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@haskell.org http://www.haskell.org/mailman/listinfo/beginners
On Sat, Jun 16, 2012 at 11:17 PM, Daniel Hlynskyi <abcz2.uprola@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. Note that this isn't quite the right way to represent a poly if you want to get to a canonical representation. -- Jedaï
On Sun, Jun 17, 2012 at 9:36 AM, Chaddaï Fouché <chaddai.fouche@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
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@gmail.com>:
On Sun, Jun 17, 2012 at 9:36 AM, Chaddaï Fouché <chaddai.fouche@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
participants (3)
-
Chaddaï Fouché -
Daniel Hlynskyi -
Máté Kovács