Haskell : error Couldn't match expected type

Question

Someone can help me to figure out what I am doing wrong in this code. I try to write a code that add two Polynomial functions, but I always get this error message:

main.hs:6:45: error:
    * Couldn't match expected type `[a]' with actual type `Poly a'
    * In the second argument of `(:)', namely `polyadd (P xs) (P ys)'
      In the first argument of `P', namely
        `((x + y) : polyadd (P xs) (P ys))'
      In the expression: P ((x + y) : polyadd (P xs) (P ys))
    * Relevant bindings include
        ys :: [a] (bound at main.hs:6:26)
        y :: a (bound at main.hs:6:24)
        xs :: [a] (bound at main.hs:6:15)
        x :: a (bound at main.hs:6:13)
        polyadd :: Poly a -> Poly a -> Poly a (bound at main.hs:4:1)
  |
6 | polyadd (P (x:xs)) (P (y:ys))  = P ((x+y) : polyadd (P xs) (P ys))
  |                                             ^^^^^^^^^^^^^^^^^^^^^

here is my code

data Poly a = P [a] deriving (Show, Eq)

polyadd :: (Num a, Eq a) => Poly a -> Poly a -> Poly a
polyadd (P ([])) (P (ys))          = P ys
polyadd (P (xs)) (P [])          = P xs
polyadd (P (x:xs)) (P (y:ys))  = P ((x+y) : polyadd (P xs) (P ys))

Answer 1

As I understand, you are creating a new Poly object, by combining the elements of the lists that are inside 2 Poly objects. Adding elements at corresponding indices and appending any possible remains of the longer list (if any).

While your polyadd returns a P [a], you are trying to append (x+y) to it using cons : like it is a simple list.

This happens in this part of your code:

polyadd (P (x:xs)) (P (y:ys))  = P ((x+y) : polyadd (P xs) (P ys))

And this is how ghc expresses the problem in its own words:

    * Couldn't match expected type `[a]' with actual type `Poly a'
    * In the second argument of `(:)', namely `polyadd (P xs) (P ys)'

: has an a on the left and expects a [a] on the right, but finds a Poly a.

This is how I would implement it. Extract both lists, pass them to a helper function to merge them and create a Poly with the result.

data Poly a = P [a] deriving (Show, Eq)
polyadd2 :: (Num a, Eq a) => Poly a -> Poly a -> Poly a
polyadd2 (P xs) (P ys)    = P $ go xs ys where
  go []   ys   = ys
  go xs  []    = xs
  go (x:xs) (y:ys) = (x+y) : go xs ys

Two notes on the side:

1. Poly is a good case to be turned into newtype since it has only one constructor which has only one field.
2. You can implement the list merging part of the code using a variety of zip related functions.

Answer 2

In this expression:

(x+y) : polyadd (P xs) (P ys)

You are trying to create a list by attaching head (x+y) to tail polyadd (P xs) (P ys). That's what operator (:) means. That's what it does. Creates a list from a head and a tail.

The problem is, a list's tail is supposed to be a list, but polyadd (P xs) (P ys) is not a list, it's a Poly a, as defined in your type signature. So it doesn't fit operator (:), which expects its right operand to be a list. So the compiler tells you exactly that: Couldn't match expected type '[a]' with actual type 'Poly a'

From what my mind reading abilities tell me about your intent, what you actually wanted to do was prepend (x+y) to the list that is wrapped inside the Poly a. To do that, you have to deconstruct the Poly a first:

polyadd (P (x:xs)) (P (y:ys))  = 
  let (P zs) = polyadd (P xs) (P ys)
  in P ((x+y) : zs)

But of course it would be cleaner and more efficient not to unwrap and rewrap the Poly a values at every step, but instead construct the resulting list first, and only then wrap it. To do that, you'll need a separate function that does the list traversal, then call that function, and wrap its result in Poly:

polyadd :: (Num a, Eq a) => Poly a -> Poly a -> Poly a
ployadd (P as) (P bs) = P (inner as bs)
  where
    inner [] ys = ys
    inner xs [] = xs
    inner (x:xs) (y:ys) = (x+y) : inner xs ys