Une solution purement fonctionnelle à ce problème peut-elle être aussi propre que l'impératif?

J'ai un exercice en Python comme suit:

• un polynôme est donné comme un tuple de coefficients tels que les puissances sont déterminées par les indices, par exemple: (9,7,5) signifie 9 + 7 * x + 5 * x ^ 2

• écrire une fonction pour calculer sa valeur pour x donné

Depuis que je suis dans la programmation fonctionnelle ces derniers temps, j'ai écrit

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 je juge illisible, alors j'ai écrit

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]

ce qui est au moins aussi illisible, alors j'ai écrit

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

ce qui pourrait être moins efficace (éditer: j'avais tort!) car il utilise de nombreuses multiplications au lieu d'exponentiation, en principe, je ne me soucie pas des mesures ici (éditer: comme c'est idiot de ma part! toujours pas aussi lisible (sans doute) que la solution itérative:

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

Existe-t-il une solution purement fonctionnelle aussi lisible que l'impératif et proche de son efficacité?

Certes, un changement de représentation aiderait, mais cela a été donné par l'exercice.

Peut être Haskell ou Lisp, pas seulement Python.

La méthode de Horner est probablement plus efficace en termes de calcul comme le souligne @delnan, mais j'appellerais cela assez lisible en Python pour la solution d'exponentiation:

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

De nombreux langages fonctionnels ont des implémentations mapi qui vous permettent d'avoir un index tissé à travers une carte. Combinez cela avec une somme et vous avez ce qui suit en F #:

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

Je ne comprends pas comment votre code est lié à la portée du problème que vous avez définie, je vais donc donner ma version de ce que fait votre code en ignorant la portée du problème (en fonction du code impératif que vous avez écrit).

Haskell assez lisible (cette approche peut être facilement traduite dans n'importe quel langage FP qui a une déstructuration de liste et qui sort pur et lisible):

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

Parfois, l'approche simple et naïve de haskell comme celle-ci est plus propre que l'approche plus concise des personnes moins habituées à la PF.

Une approche plus clairement impérative qui est encore complètement pure est la suivante:

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 à la deuxième approche est d'être dans la monade ST, il fonctionnera très bien.

Bien que pour être certain, l'implémentation réelle la plus probable d'un Haskeller serait le zipwith mentionné dans une autre réponse ci-dessus. zipWithest une approche très typique et je crois que Python peut imiter l'approche zippée de la combinaison de fonctions et d'un indexeur qui peut être mappé.

Si vous avez juste un tuple (fixe), pourquoi ne pas le faire (en Haskell):

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

Si à la place vous avez une liste de coefficients, vous pouvez utiliser:

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

ou avec une réduction telle que vous l'aviez:

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

Il existe un ensemble général d'étapes que vous pouvez utiliser pour améliorer la lisibilité des algorithmes fonctionnels:

• Mettez des noms sur vos résultats intermédiaires, au lieu d'essayer de tout entasser sur une seule ligne.
• Utilisez des fonctions nommées au lieu de lambdas, en particulier dans les langues à syntaxe lambda verbeuse. Il est beaucoup plus facile de lire quelque chose comme evaluateTermune longue expression lambda. Tout simplement parce que vous pouvez utiliser un lambda ne signifie pas nécessairement que vous devriez .
• Si l'une de vos fonctions désormais nommées ressemble à quelque chose qui reviendrait assez fréquemment, il est probable qu'elle se trouve déjà dans la bibliothèque standard. Regardez autour de vous. Mon python est un peu rouillé, mais il semble que vous ayez essentiellement réinventé enumerateou zipWith.
• Souvent, voir les fonctions et les résultats intermédiaires nommés permet de raisonner plus facilement sur ce qui se passe et de le simplifier, auquel cas il peut être judicieux de remettre un lambda ou de combiner certaines lignes ensemble.
• Si un impératif pour la boucle semble plus lisible, il est probable qu'une incompréhension fonctionnerait bien.