Haskell中的多项式因式分解

import Data.Ratio

-- 定义多项式类型
data Poly a = P [a] deriving (Eq, Show)

-- 多项式乘法
mulP :: Num a => Poly a -> Poly a -> Poly a
mulP (P xs) (P ys) = P (conv xs ys)
  where
    conv xs ys = [sum [x * y * (fromIntegral (i+j)) | (x,i) <- zip xs [0..], (y,j) <- zip ys [0..]]]

-- 多项式的根
roots :: (Fractional a, Eq a) => Poly a -> [a]
roots (P xs) = [x | x <- [-100..100], evalP (P xs) x == 0]
  where
    evalP (P xs) x = sum [a * x^i | (a,i) <- zip xs [0..], i /= 0] + head xs

-- 多项式因式分解
factorizeP :: (Fractional a, Eq a) => Poly a -> [Poly a]
factorizeP p = map (\r -> divP p (P [1, -r])) (roots p)

-- 多项式除法
divP :: Num a => Poly a -> Poly a -> Poly a
divP (P xs) (P ys) = P (xs ++ replicate (length ys - length xs - 1) 0)

-- 示例
p = P [1, -3, 3, -1]
factors = factorizeP p