Как добавить сравнения сравнений (==) в newtype в Haskell

Question

Я пытаюсь определить новый тип, называемый «Poly» в Haskell, где type представляет собой список «Num», представляющий полиномиальное выражение. [1,2,3] соответствует 3x^2 + 2x + 1, поэтому [4,5,6,0,0 ... 0] - тот же полином, что и [4,5,6].

Я создал вспомогательную функцию, называемую «chop», чтобы удалить 0 из конца списка, но мне трудно сравнивать два списка. Любые идеи, почему мое использование «экземпляра» здесь не работает?

Он компилируется, но когда вы пытаетесь сравнить 2 экземпляра Poly, WinGHCi зависает.

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 

Answer 1

Проблема в том, что вы определили (==) как рекурсивный. Упрощая ваше определение немного, у вас есть:

m == n = chop m == chop n 

Это вычисляется следующим образом:

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)) 
-> { ... } 

Вместо диспетчерских тесты равенства обратно на тест равенства многочленов, вы должны направить к равенству для списков , Например, можно написать

m == n = let P m' = chop m; P n' = chop n in m' == n' 

вместо этого.