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.