¿Puede una solución funcional pura a este problema ser tan limpia como el imperativo?

Tengo un ejercicio en Python de la siguiente manera:

• un polinomio se da como una tupla de coeficientes de modo que las potencias están determinadas por los índices, por ejemplo: (9,7,5) significa 9 + 7 * x + 5 * x ^ 2

• escribir una función para calcular su valor para x dado

Como estoy en la programación funcional últimamente, escribí

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)

que considero ilegible, así que escribí

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]

que es al menos tan ilegible, así que escribí

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

que podría ser menos eficiente (editar: ¡me equivoqué!) ya que usa muchas multiplicaciones en lugar de exponenciación, en principio, no me importan las mediciones aquí (editar: ¡Qué tonto de mi parte! ¡La medición habría señalado mi error!) y todavía no es tan legible (posiblemente) como la solución iterativa:

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

¿Existe una solución puramente funcional tan legible como la imperativa y cercana a la eficiencia?

Es cierto que un cambio de representación ayudaría, pero esto fue dado por el ejercicio.

También puede ser Haskell o Lisp, no solo Python.

El método de Horner es probablemente más eficiente desde el punto de vista computacional como señala @delnan, pero yo llamaría a esto bastante legible en Python para la solución de exponenciación:

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

Muchos lenguajes funcionales tienen implementaciones de mapas que le permiten tener un índice entrelazado a través de un mapa. Combina eso con una suma y tienes lo siguiente en F #:

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

No entiendo cómo se relaciona su código con el alcance del problema que definió, así que le daré mi versión de lo que hace su código ignorando el alcance del problema (basado en el código imperativo que escribió).

Haskell bastante legible (este enfoque se puede traducir fácilmente a cualquier lenguaje FP que tenga una lista de desestructuración y salga puro y legible):

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

A veces, el enfoque simple e ingenuo en Haskell es más limpio que el enfoque más conciso para las personas menos acostumbradas a la PF.

Un enfoque más claramente imperativo que todavía es completamente puro es:

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)

La ventaja del segundo enfoque es que estar en la Mónada ST funcionará muy bien.

Aunque para estar seguros, la implementación real más probable de un Haskeller sería el código postal mencionado en otra respuesta anterior. zipWithEs un enfoque muy típico y creo que Python puede imitar el enfoque de compresión de combinar funciones y un indexador que se puede mapear.

Si solo tiene una tupla (fija), ¿por qué no hacer esto (en Haskell)?

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

Si, en cambio, tiene una lista de coeficientes, puede usar:

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

o con una reducción como la tenías:

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

Hay un conjunto general de pasos que puede usar para mejorar la legibilidad de los algoritmos funcionales:

• Ponga nombres en sus resultados intermedios, en lugar de tratar de agrupar todo en una línea.
• Utilice funciones con nombre en lugar de lambdas, especialmente en idiomas con sintaxis detallada de lambda. Es mucho más fácil leer algo como evaluateTermuna larga expresión lambda. El hecho de que pueda usar una lambda no significa necesariamente que deba hacerlo .
• Si una de sus funciones ahora nombradas parece algo que aparecería con bastante frecuencia, es probable que ya esté en la biblioteca estándar. Mira alrededor. Mi pitón está un poco oxidado, pero parece que básicamente reinventaste enumerateo zipWith.
• A menudo, ver las funciones y los resultados intermedios nombrados hace que sea más fácil razonar sobre lo que está sucediendo y simplificarlo, en cuyo punto podría tener sentido volver a colocar una lambda o combinar algunas líneas.
• Si un imperativo para el bucle parece más legible, es probable que una comprensión funcione bien.