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

10

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.

user1358
la source
7
D'après mon expérience, un code purement fonctionnel dans le sens de ne pas utiliser de variables mutables (ce qui implique également de ne pas utiliser de forboucles, par exemple) est un mauvais objectif à viser en Python. Re-lier judicieusement les variables et ne pas muter les objets vous donne presque tous les avantages et rend le code infiniment plus lisible. Étant donné que les objets numériques sont immuables et ne relient que deux noms locaux, votre solution "impérative" réalise mieux les vertus de programmation fonctionnelle que tout code Python "strictement pur".
2
BTW La méthode de multiplication est la méthode de Horner et elle est plus efficace que l'exponentiation à chaque étape, car l'exponentiation nécessite les mêmes multiplications et plus encore.
1
Python est un peu notoirement laid lorsque vous utilisez lambda, par rapport aux langages avec une fonction de syntaxe anonyme plus légère. Une partie de cela contribue probablement à l'apparence «impure».
KChaloux
@KChaloux, c'est exactement ce que j'allais dire. La prise en charge de la programmation fonctionnelle est en quelque sorte une réflexion après coup en Python à bien des égards et cela se voit. Même si je ne pense pas que même la première version soit si horriblement illisible que vous ne pouvez pas comprendre ce qui se passe.
Evicatos
Je suis vraiment confus par votre code, alors que la portée du problème a une équation mathématique qui est extrêmement claire, pourquoi ne pas simplement utiliser cette équation mathématique textuellement? C'est assez facilement transformé en une fonction dans n'importe quelle langue ... Je ne sais pas ce que vous voulez mapper ou réduire ou itérer quoi que ce soit lorsque la question demande une fonction qui évalue une seule équation et donne cette équation - elle ne demande pas itération du tout ...
Jimmy Hoffa

Réponses:

13

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)] )
aelfric5578
la source
17
Supprimez les crochets et donnez aux variables des noms plus descriptifs, et c'est encore mieux: sum(coeff * X**power for power, coeff in enumerate(poly))
Izkata
1
Cela m'attriste que les autres réponses affichées soient si complexes. Utilisez la langue à votre avantage!
Izkata
la compréhension est comme une boucle for "clandestinement" dans la programmation fonctionnelle
user1358
7
@ user1358 Non, c'est du sucre syntaxique pour la composition de mapet filter. On peut également le considérer comme une boucle for d'une forme particulière, mais les boucles de cette forme sont équivalentes au combinateur fonctionnel susmentionné.
7

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
Steven Evers
la source
2
Et même s'ils ne le font pas, tant que vous comprenez comment cela mapfonctionne, il devrait être assez simple d'écrire l'un des vôtres.
KChaloux
4

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

Jimmy Hoffa
la source
4

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..]
Paul
la source
1
Ce ne sont PAS des devoirs! Sans oublier que j'ai déjà fait 3 solutions.
user1358
La moitié du temps en Python (y compris dans ce cas), "tuple" signifie "liste immuable" et est donc de longueur arbitraire.
longueur évidemment arbitraire
user1358
1
pas à cause de python, mais parce que le polynôme implique une longueur arbitraire, et une taille fixe ne serait pas un gros exercice
user1358
1
@delnan C'est intéressant. J'ai toujours considéré tupleun ensemble de valeurs de taille fixe, chacun de types potentiellement différents, qui ne peuvent pas être ajoutés ou supprimés. Je n'ai jamais vraiment compris pourquoi un langage dynamique avec des listes, qui acceptent des entrées hétérogènes, en aurait besoin.
KChaloux
3

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.
Karl Bielefeldt
la source