Как добавить сравнение равенства (==) к новому типу в Haskell

Я пытаюсь определить новый тип под названием «Poly» в Haskell, где тип представляет собой список «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

typeclass haskell newtype
person dman    schedule 28.04.2015    source источник
comment
Небольшой комментарий к стилю: код if e then True else False эквивалентен просто e.   -  person chi    schedule 29.04.2015
comment
Кстати, chop имеет квадратичную сложность, это можно сделать за линейное время O(n).   -  person Franky    schedule 29.04.2015

Ответы (1)


arrow_upward
8
arrow_downward

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

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'

вместо.

person Daniel Wagner    schedule 28.04.2015
comment
ПОЛНОСТЬЮ РАБОТАЕТ. Однако необходимо было внести одно незначительное изменение (P вместо Poly) m == n = пусть P m' = отрезать m; P n' = разбить n на m' == n' - person dman; 29.04.2015