Полином в Хаскеле

Question

В четверг у меня экзамен по функциональному программированию, и я почти уверен, что мне придется делать TAD с полиномами. Я добавляю полиномы на данный момент так:

type Pol = [(Int,Int)] 

suma :: Pol -> Pol -> Pol
suma [] ys = ys
suma xs [] = xs
suma ((c1,g1):xs) ((c2,g2):ys)
    | g1 == g2  = ((c1+c2,g1):(suma xs ys))
    | g1 > g2 = ((c1,g1):(suma xs ((c2,g2):ys)))
    | g1 < g2 = ((c2,g2):(suma ((c1,g1):xs) ys))

Это прекрасно работает, но учитель не любит. Она предпочитает делать это с:

data Pol = P [(Int,Int)] deriving Show

В начале я думал, что было бы легко изменить структуру, но это не так, как я получаю много проблем при компиляции. Кто-нибудь может мне помочь? Я пробовал этот способ, но он не работает:

data Pol = P [(Int,Int)] deriving Show

suma :: Pol -> Pol -> Pol
suma (P []) (P ys) = P ys
suma (P xs) (P []) = P xs
suma (P ((c1,g1):xs)) (P ((c2,g2):ys))
    | g1 == g2  = P ((c1+c2,g1):suma (P xs) (P ys))
    | g1 > g2   = P ((c1,g1):(suma (P xs) (P ((c2,g2):ys))))
    | g1 < g2   = P ((c2,g2):(suma (P ((c1,g1):xs)) (P ys)))

Я получаю эту ошибку:

ERROR file:.\Febrero 2011.hs:7 - Type error in application
*** Expression     : P (c1 + c2,g1) : suma (P xs) (P ys)
*** Term           : suma (P xs) (P ys)
*** Type           : Pol
*** Does not match : [a]

Большое спасибо!

Answer 1

Если что-то не работает, пожалуйста, объясните почему в вопросе. Если есть ошибки компилятора, пожалуйста, опубликуйте их.

В этом случае проблема заключается в ошибке типа в последних ветвях suma. Посмотрите на

suma (P ((c1,g1):xs)) (P ((c2,g2):ys))
    | g1 == g2  = P ((c1+c2,g1):suma (P xs) (P ys))

В P ((c1+c2,g1):suma (P xs) (P ys)) вы пытаетесь создать список типа [(Int,Int)] с

(c1+c2,g1):suma (P xs) (P ys)

Вы пытаетесь создать список с заголовком типа (Int,Int), но с хвостом типа Pol (тип результата suma). В других случаях есть похожие ошибки.

Answer 2

Заставьте suma работать с List так, чтобы:

suma :: [(Int,Int)] -> [(Int,Int)] -> [(Int,Int)]
suma [] ys = ys
suma xs [] = xs
suma ((c1,g1):xs) ((c2,g2):ys)
    | g1 == g2  = ((c1+c2,g1):(suma xs ys))
    | g1 > g2 = ((c1,g1):(suma xs ((c2,g2):ys)))
    | g1 < g2 = ((c2,g2):(suma ((c1,g1):xs) ys))

Тогда сумма для Pol может быть определена как:

sumPol :: Pol -> Pol -> Pol
sumPol (P a) (P b) = P (suma a b)

Если вы хотите быть более стильным или монадическим :), тогда вы можете сделать Pol монадой и использовать нотацию do, чтобы делать вещи

Answer 3

Прежде всего, давайте рассмотрим ваш оригинальный код

type Pol = [(Int,Int)] 

suma :: Pol -> Pol -> Pol
suma [] ys = ys
suma xs [] = xs
suma ((c1,g1):xs) ((c2,g2):ys)
    | g1 == g2  = ((c1+c2,g1):(suma xs ys))
    | g1 > g2 = ((c1,g1):(suma xs ((c2,g2):ys)))
    | g1 < g2 = ((c2,g2):(suma ((c1,g1):xs) ys))

Если вы делаете:

let p1 = [(5,0),(1,1),(7,2)]::Pol
let p2 = [(1,2),(3,1),(2,0)]::Pol

тогда вы получите:

suma p1 p2
[(1,2),(3,1),(7,0),(1,1),(7,2)]

Это не «неправильно», но это не то, что можно ожидать от суммирования двух полиномов: вы можете получить результат в его упрощенной форме:

[(7,0),(4,1),(8,2)]

Еще один комментарий: вы узнали о Haskell синтаксис записи ? Я думаю, что это может упростить вашу работу и прояснить ситуацию. Вот подсказка:

data Term = Term { coeff :: Int,
                   expnt :: Int
                 } deriving Show

data Pol = Pol { terms :: [Term] } deriving Show

При этом суммирование двух многочленов без упрощения результата так же просто, как ... объединение их терминов :) ... и все наглядно:

Main> let p1 = Pol [Term 5 0, Term 1 1, Term 7 2]
Main> p1
Pol {terms = [Term {coeff = 5, expnt = 0},Term {coeff = 1, expnt = 1},Term {coeff = 7, expnt = 2}]}
Main> let p2 = Pol [Term 1 2, Term 3 1, Term 2 0]
Main> p2
Pol {terms = [Term {coeff = 1, expnt = 2},Term {coeff = 3, expnt = 1},Term {coeff = 2, expnt = 0}]}
Main> let p3 = sumpol p1 p2
Main> p3
Pol {terms = [Term {coeff = 5, expnt = 0},Term {coeff = 1, expnt = 1},Term {coeff = 7, expnt = 2},Term {coeff = 1, expnt = 2},Term {coeff = 3, expnt = 1},Term {coeff = 2, expnt = 0}]}

Упрощение полинома немного сложнее, но хорошее упражнение.

Надеюсь, это поможет.