CODEWITHSUNDEEP
haskell
John Marley
John Marley

Reputation: 9

Creating Eq instances for polynomials

Representing polynomials in Haskell:

newtype Poly a = P [a]
x :: Num a => Poly a
x = P [1]

instance (Num a, Eq a) => Eq (Poly a) where

E.g. P[1,2,3] = 3x^2 + 2x + 1

I want to say that two polynomials are equal if the lists they have are equal (e.g. P[1,2,3] is equal to P[1,2,3]). They are also equal if the lists are the same except the last elements are 0's (e.g. P[1,2,3] is equal to P[1,2,3,0,0]).

However, I don't know the syntax for how to do this.

Upvotes: 0

Views: 306

Answers (2)

Random Dev
Random Dev

Reputation: 52290

implementing Eq

Just to extend on Jakes answer so you get a complete one:

I like the idea of just removing the leading zeros and with this you soon end up with:

newtype Poly a = P [a]

instance (Num a, Eq a) => Eq (Poly a) where
  P xs == P ys =
    removeLeadingZeros (reverse xs) == removeLeadingZeros (reverse ys)

removeLeadingZeros :: (Eq a, Num a) => [a] -> [a]
removeLeadingZeros (0 : xs) = removeLeadingZeros xs
removeLeadingZeros xs = xs

mind, that you don't really have to reverse again to just look for equality (as xs == ys <=> reverse xs == reverse ys)

here is a short test session in ghci:

λ> let p1 = P[1,2,3,0,0]
λ> let p2 = P[1,2,3]
λ> let p3 = P[1,2,3,0,4]

λ> p1 == p2
True

λ> p1 == p3
False

λ> p2 == p3
False

using smart constructors

Another possibility is to not publish the P constructor and get the polynoms into a normalized form at construction - this has the advantage that you can just use deriving Eq

module Poly
       ( Poly, fromList
       ) where

newtype Poly a = P [a]
                 deriving Eq

fromList :: (Num a, Eq a) => [a] -> Poly a
fromList = P . reverse . removeLeadingZeros . reverse

example

λ> let p1 = fromList [1,2,3,0,0]
λ> let p2 = fromList [1,2,3]

λ> p1 == p2
True

hiding it all

As you already seem to have implemented Num (Poly a) you can even remove the fromList from the exports - so users have to use arithmetic operators instead to construct polynoms.

You basically just have to export an x instead:

x :: (Eq a, Num a) => Poly a
x = fromList [0,1]

remarks

Depending on if P [] is ok for the zero polynom or if you rather have P [0] in this case instead you might want to rewrite removeLeadingZeros to

removeLeadingZeros :: (Eq a, Num a) => [a] -> [a]
removeLeadingZeros [0] = [0]
removeLeadingZeros (0 : xs) = removeLeadingZeros xs
removeLeadingZeros xs = xs

or something like it

Upvotes: 4

Sage Mitchell
Sage Mitchell

Reputation: 1583

removeLeadingZeros (0 : xs) = removeLeadingZeros xs removeLeadingZeros xs = xs

Reverse the list, remove leading zeros, and then reverse again.

(reverse . removeLeadingZeros . reverse) [3, 2, 1, 0, 0, 0]

Do the same operation to both polynomials and compare using ==.

(Untested for now, but I think this is right.)

Upvotes: 2

Related Questions