Hacker News Reader

Comment by jonalmeida | Hacker News Reader

I think there's an error in the first example.

  Poly [1, -3, 0, 1]

Should be:

  Poly [1, 0, -3, 1]

EDIT: My mistake.

View on HN

It's not - it starts with the unit coefficient (1), then x (-3), then x^2 (0), then x^3 (1). Some things become easier this way - including addition of polynomials of differing degree - and as an added bonus you can phantasize about representing power series as (lazy) infinite lists.

I thought so too at first but given the way addition is defined later on, it makes sense to keep the coefficients sorted by increasing power (the leftmost element in the list is its head, and the easiest to access when doing anything recursive)

Evaluation also becomes easy this way, using Horner's method: https://en.wikipedia.org/wiki/Horner%27s_method#Python_imple...

Something along the lines of this right?

  eval =
  v [] => 0
  v x:xs => x + v * eval v xs

You do have to love how clean definition by cases makes these sorts of things.

But this doesn't argue for the low-to-high order, because of reversed(). This code would be simpler and faster with the coefficients in the opposite order.

You're right, the process does start from the higher coefficients, and so does not really support the ordering presented.

You either need to use foldr to defer the multiply-and-add until the end of the list is processed, or reverse the list before processing it.

Reply on news.ycombinator.com