CODEWITHSUNDEEP
haskellfunctional-programmingcomputer-sciencepolynomial-mathsimplification
Jack Buckley
Jack Buckley

Reputation: 171

Transform Polynomial to Standard Form in Haskell

In Haskell, I'm using a custom data type of Poly a = X | Coef a | Sum (Poly a) (Poly a) | Prod (Poly a) (Poly a) deriving (Show).

As such, the polynomial (3+x)^2 would be represented as (Prod (Sum (Coef 3) X) (Sum (Coef 3) X)).

I am having difficulty converting a polynomial entered this way into a list of coefficients of its standard form, which I believe would be [9, 6, 1] as (3+x)^2 = 9 + 6x + x^2.

I believe a possible solution would be to implement some math functions on my polynomial data types so that I could simplify an input, but I have been unsuccessful in doing this. Is there another way?

Can someone point me in the right direction?

Upvotes: 0

Views: 926

Answers (1)

Bergi
Bergi

Reputation: 665070

Don't simplify on your Poly type, simplify directly to the list of coefficients. Also maybe have the list of coefficients reversed (the first element for ^0, the second for ^1, the third for ^2 etc), I think that makes it easier.

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 …

I'll leave the actual implementation of how to merge the lists a' and b' for Sum and Prod respectively as an exercise.

If you want, you can also make a toPoly :: [a] -> Poly a function that converts from the list into the standard form of polynomials.

Upvotes: 6

Related Questions