I'm trying to define a newtype called "Poly" in Haskell, where the type is a list of a "Num"s that represents a polynomial expression. [1,2,3] corresponds to 3x^2 + 2x + 1, so therefore [4,5,6,0,0...0] is the same polynomial as [4,5,6].
I've created a helper function called "chop" to remove 0's from the end of the list, but I'm having trouble comparing two lists. Any ideas why my use of "instance" does not work here?
It compiles, but when you try to compare 2 instances of Poly, WinGHCi hangs.
newtype Poly a = P [a]
x :: Num a => Poly a
chop :: (Eq a, Num a) => Poly a -> Poly a
chop (P l) = if (last l) == 0 then chop (P $ init l) else P l
instance (Num a, Eq a) => Eq (Poly a) where
(==) m n = if (chop m) == (chop n) then True else False
The problem is that you have defined (==) to be recursive on itself. Simplifying your definition a little, you have:
m == n = chop m == chop n
This evaluates like so:
m == n
-> { definition of (==) }
chop m == chop n
-> { definition of (==) }
chop (chop m) == chop (chop n)
-> { definition of (==) }
chop (chop (chop m)) == chop (chop (chop n))
-> { ... }
Instead of dispatching your equality test back to the equality test for polynomials, you should dispatch to the equality for lists. For example, one might write
m == n = let P m' = chop m; P n' = chop n in m' == n'
instead.