在Haskell中将多项式转换为标准形式

Question

在Haskell中,我使用的是自定义数据类型Poly a = X | Coef a | Sum (Poly a) (Poly a) | Prod (Poly a) (Poly a) deriving (Show).

因此,多项式(3 + x)^ 2将表示为(Prod (Sum (Coef 3) X) (Sum (Coef 3) X)).

我很难将以这种方式输入的多项式转换为其标准形式的系数列表,我相信它将[9, 6, 1]为(3 + x)^ 2 = 9 + 6x + x ^ 2.

我相信一个可能的解决方案是在我的多项式数据类型上实现一些数学函数,这样我就可以简化输入,但是我没有成功.还有另外一种方法吗？

有人能指出我正确的方向吗？

Answer 1

不要简化您的Poly类型,直接简化为系数列表.也许可以反转系数列表(第一个元素^0,第二个元素^1,第三个元素^2等),我认为这样可以更容易.

data Poly a = X | Coef a | Sum (Poly a) (Poly a) | Prod (Poly a) (Poly a) deriving (Show)

toList :: Num a => Poly a -> [a]
toList X = [0, 1]
toList (Coef a) = [a]
toList (Sum a b) = let a' = toList a …
toList (Prod a b) = let a' = toList a …

我将离开实际的实现如何合并列表a'和b'for Sum和Prod分别作为练习.

如果需要,还可以创建一个toPoly :: [a] -> Poly a从列表转换为多项式的标准形式的函数.