Polynomial in Haskell

I have an exam on thursday about Functional programming and I’m pretty sure that I will have to do a TAD with Polynomials. I’m adding polynomials for the moment like this:

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))

It perfectly works but the teacher doesn’t like. She prefers to do it with:

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

At the beginning, I though it would be easy to change the structure but it’s not as I’m getting a lot of trouble in the compilation. Can anyone help me please? I tried this way but it doesn’t work:

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):(开发者_C百科suma (P xs) (P ((c2,g2):ys))))
    | g1 < g2   = P ((c2,g2):(suma (P ((c1,g1):xs)) (P ys)))

I get this error:

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]

Thank you so much!

---

If something doesn't work, please explain why in the question. If there are compiler errors, please post them.

In this case, the problem is a type error in the last branches of suma. Look at

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

In P ((c1+c2,g1):suma (P xs) (P ys)), you're trying to create a list of type [(Int,Int)] with

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

You're trying to construct a list with the head at type (Int,Int), but the tail at type Pol (the result type of suma). The other cases have similar errors.

---

Make suma to work on List such that:

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))

Then Sum for Pol can be defined as:

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

In case you want to be more stylish or monadic :) then you can make Pol a monad and use a do notation to do the stuff

---

First of all, let's consider your original code

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))

If you do:

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

then you get:

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

This is not "wrong", but it's not what one may expect out of summing two polynomials: you may want to get the result in its simplified form:

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

One more comment: have you learned about Haskell record syntax? I think it can simplify your work and make things cleared. Here's a hint:

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

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

With that, summing two polynomials without simplifying the result is as simple as ... concatenating their terms :) ... and everything is showable:

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}]}

Simplification of a polynomial is a little trickier, but a good exercise.

I hope this helps.