Hacker News Reader

Comment by jlebar | Hacker News Reader

I am not a Haskell programmer, but is this correct?

    (Poly a) + (Poly b) = Poly $ addup a b   where
       addup [] b  = b
       addup a  [] = a
       addup (a:as) (b:bs) = (a+b):(addup as bs)

Imagine a simple example, adding `x+2` and `10`. In OP's representation, these would be represented as the lists [1, 2] and [10]. That is, the first element is the coefficient of the term of highest degree.

But doesn't this implementation add list elements left-to-right, so we'd end up with the result [11, 2] instead of [1, 12]?

View on HN

You're misreading OP's representation:

> The polynomial x^3 −3x +1 is represented as Poly [1, -3, 0, 1]

It starts with the 0th coefficient and goes up. So adding `x+2` and `10` would be zip-adding lists [2,1] and [10,0].

>> The polynomial x^3 −3x +1 is represented as Poly [1, -3, 0, 1]

> It starts with the 0th coefficient and goes up.

Is a list in Haskell canonically written in the opposite order of what I expect? I expect that the 0'th element of the list [a, b, c] is `a`. In Haskell, is it `c`? Assuming `a` is the 0th element, then the coefficient for the highest-degree term is the 0th element of the Poly. And since the degree of the two polynomials doesn't necessarily match, matching up the two highest-degree coefficients and adding them is obviously wrong.

Or am I going crazy here?

  module Main where

  newtype Poly a = Poly [a] deriving (Eq, Show)

  instance Num a => Num (Poly a) where
    Poly a + Poly b = Poly $ addup a b
      where
        addup [] b  = b
        addup a  [] = a
        addup (a:as) (b:bs) = (a+b):(addup as bs)

  main :: IO ()
  main = print (Poly [1, 2] + Poly [10])


  *Main> main
  Poly [11,2]

Yep, you are correct.

Yeah it’s the cons operator so it matches the first element (head) of the list and next elements (tail). It would need a reverse and reverse back to work correctly.

reverse (addup (reverse a) (reverse b))

Reply on news.ycombinator.com