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

[Chaddaï Fouché]

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.

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

-- 
Jedaï