Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
6  
In my experience, purely functional code in the sense of not using mutable variables (which also implies not using for loops, for example) is a bad goal to aim for in Python. Re-binding variables judiciously and not mutating objects gives you almost all of the benefits and makes the code infinitely more readable. Since number objects are immutable and it only rebinds two local names, your "imperative" solution better realizes functional programming virtues than any "strictly pure" Python code. –  delnan Dec 20 '13 at 17:36
1  
BTW The multiplication method is Horner's method and it's more efficient than exponentiation at each step, as the exponentiation requires the very same multiplications and then some more. –  delnan Dec 20 '13 at 17:45
1  
Python is kinda notoriously ugly when you get into using lambda, compared to languages with a lighter anonymous syntax function. Part of that probably contributes to the "unclean" appearance. –  KChaloux Dec 20 '13 at 18:00
    
@KChaloux that's exactly what I was going to say. Functional programming support is somewhat of an afterthought in Python in many respects and it kind of shows. Even so I don't think even the first version is so horribly unreadable that you can't figure out what's going on. –  Evicatos Dec 20 '13 at 18:05
    
I am really confused by your code, whereas the problem-scope has a mathematical equation which is extremely clear, why don't you just use that math equation verbatim? It's fairly easily turned into a function given any language... not sure what you want to map or reduce or iterate anything for when the question is asking for a function that evaluates a single equation and gives that equation - it doesn't ask for iteration at all... –  Jimmy Hoffa Dec 20 '13 at 18:38

5 Answers 5

up vote 10 down vote accepted

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)] )
share|improve this answer
13  
Drop the square brackets and give the variables more descriptive names, and it's even better: sum(coeff * X**power for power, coeff in enumerate(poly)) –  Izkata Dec 21 '13 at 1:26
1  
It kind of saddens me that the other posted answers are so complex. Use the language to your advantage! –  Izkata Dec 21 '13 at 1:27
    
comprehension is like a for-loop "smuggled" into functional programming –  user1358 Dec 21 '13 at 10:05
6  
@user1358 No, it's syntactic sugar for the composition of map and filter. One can also think of it as a for loop of a particular shape, but loops of that shape are equivalent to the aforementioned funcitonal combinator. –  delnan Dec 21 '13 at 16:38

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
share|improve this answer
2  
And even if they don't, as long as you understand how map works, it should be pretty simple to write one of your own. –  KChaloux Dec 20 '13 at 18:26

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.

share|improve this answer

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..]

I think maybe the language choice is helping the readability on this one :)

share|improve this answer
1  
It is NOT homework! Not to mention that I did 3 solutions already. –  user1358 Dec 20 '13 at 17:40
    
Half of the time in Python (including in this case), "tuple" means "immutable list" and is hence of arbitrary length. –  delnan Dec 20 '13 at 17:40
    
obviously arbitrary length –  user1358 Dec 20 '13 at 17:41
1  
not because of python, but because polynomial implies arbitrary length, and fixed size would not be a big of an exercise –  user1358 Dec 20 '13 at 17:46
1  
@delnan That's interesting. I've always taken tuple to mean a fixed-size set of values, each of potentially differing types, that cannot be added to or removed from. I never really understood why a dynamic language with lists, that accept heterogenous inputs, would need them. –  KChaloux Dec 20 '13 at 18:03

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.