Can a pure-functional solution to this problem be as clean as the imperative?

Question

I have an exercise in Python as follows:

• a polynomial is given as a tuple of coefficients such that the powers are determined by the indexes, e.g.: (9,7,5) means 9 + 7*x + 5*x^2

• write a function to compute its value for given x

Since I am into functional programming lately, I wrote

def evaluate1(poly, x):
  coeff = 0
  power = 1
  return reduce(lambda accu,pair : accu + pair[coeff] * x**pair[power],
                map(lambda x,y:(x,y), poly, range(len(poly))),
                0)

which I deem unreadable, so I wrote

def evaluate2(poly, x):
  power = 0
  result = 1
  return reduce(lambda accu,coeff : (accu[power]+1, accu[result] + coeff * x**accu[power]),
                poly,
                (0,0)
               )[result]

which is at least as unreadable, so I wrote

def evaluate3(poly, x):
  return poly[0]+x*evaluate(poly[1:],x) if len(poly)>0 else 0

which might be less efficient (edit: I was wrong!) since it uses many multiplications instead of exponentiation, in principle, I do not care about measurements here (edit: How silly of me! Measuring would have pointed out my misconception!) and still not as readable (arguably) as the iterative solution:

def evaluate4(poly, x):
  result = 0
  for i in range(0,len(poly)):
      result += poly[i] * x**i
  return result

Is there a pure-functional solution as readable as the imperative and close to it in efficiency?

Admittedly, a representation change would help, but this was given by the exercise.

Can be Haskell or Lisp aswell, not just Python.

Answer 1

Horner's method is probably more computationally efficient as @delnan points out, but I would call this pretty readable in Python for the exponentiation solution:

def eval_poly(poly, x):
    return sum( [a * x**i for i,a in enumerate(poly)] )

Answer 2

Many functional languages have mapi implementations that allow to you have an index weaved through a map. Combine that with a sum and you have the following in F#:

let compute coefficients x = 
    coefficients 
        |> Seq.mapi (fun i c -> c * Math.Pow(x, (float)i))
        |> Seq.sum

Answer 3

If you just have a (fixed) tuple, why not do this (in Haskell):

evalPolyTuple (c, b, a) x = c + b*x + a*x^2

If instead you have a list of coefficients, you can use:

evalPolyList coefs x = sum $ zipWith (\c p -> c*x^p) coefs [0..]

or with a reduce as you had it:

evalPolyList' coefs x = foldl' (\sum (c, p) -> sum + c*x^p) 0 $ zip coefs [0..]

Answer 4

I don't understand how your code relates to the problem scope you defined, so I'll give my version of what your code does ignoring the problem scope (based on the imperative code you wrote).

Pretty readable haskell (this approach can be easily translated to any FP language that has list destructuring and come out pure and readable):

eval acc exp val [] = acc
eval acc exp val (x:xs) = eval (acc + execPoly) (exp+1) xs
  where execPoly = x * (val^exp)

Sometimes the naive simple approach in haskell like that is cleaner than the more concise approach to people less accustomed to FP.

A more clearly imperative approach that's still completely pure is:

steval val poly = runST $ do
  accAndExp <- newSTRef (0,1)
  forM_ poly $ \x -> do
    modifySTRef accAndExp (updateAccAndExp x)
  readSTRef accAndExp
  where updateAccAndExp x (acc, exp) = (acc + x*(val^exp), exp + 1)

bonus to the second approach is being in the ST monad it will perform very well.

Though to be certain, the most likely real implementation from a Haskeller would be the zipwith mentioned in another answer above. zipWith is a very typical approach and I believe Python can mimic the zipping approach of combining functions and an indexer which can be mapped.

Answer 5

There is a general set of steps you can use to improve readability of functional algorithms:

• Put names on your intermediate results, instead of trying to cram everything on one line.
• Use named functions instead of lambdas, especially in languages with verbose lambda syntax. It's much easier to read something like evaluateTerm than a long lambda expression. Just because you can use a lambda doesn't necessarily mean you should.
• If one of your now-named functions looks like something that would come up pretty frequently, chances are it's already in the standard library. Look around. My python is a little rusty, but it looks like you basically reinvented enumerate or zipWith.
• Often, seeing the functions and intermediate results named makes it easier to reason about what's going on and simplify it, at which point it might make sense to put a lambda back in or combine some lines back together.
• If an imperative for loop looks more readable, chances are a for-comprehension would work well.