Kann eine rein funktionale Lösung für dieses Problem so sauber sein wie der Imperativ?

Ich habe eine Übung in Python wie folgt:

• Ein Polynom wird als Tupel von Koeffizienten angegeben, so dass die Potenzen durch die Indizes bestimmt werden, z. B.: (9,7,5) bedeutet 9 + 7 * x + 5 * x ^ 2

• Schreiben Sie eine Funktion, um ihren Wert für ein gegebenes x zu berechnen

Da ich mich in letzter Zeit mit funktionaler Programmierung beschäftige, habe ich geschrieben

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)

was ich für unlesbar halte, schrieb ich

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]

Das ist mindestens genauso unlesbar, also schrieb ich

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

Das könnte weniger effizient sein (edit: Ich habe mich geirrt!), da es viele Multiplikationen anstelle von Potenzierung verwendet. Im Prinzip interessieren mich Messungen hier nicht (edit: Wie dumm von mir! Messen hätte auf mein Missverständnis hingewiesen!) und immer noch nicht so lesbar (wohl) wie die iterative Lösung:

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

Gibt es eine rein funktionale Lösung, die so lesbar wie der Imperativ ist und deren Effizienz nahe kommt?

Zugegeben, eine Änderung der Repräsentation würde helfen, aber dies wurde durch die Übung gegeben.

Kann auch Haskell oder Lisp sein, nicht nur Python.

Horners Methode ist wahrscheinlich rechnerisch effizienter, wie @delnan hervorhebt, aber ich würde dies in Python für die Exponentiationslösung als ziemlich lesbar bezeichnen:

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

Viele funktionale Sprachen verfügen über Mapi-Implementierungen, mit denen Sie einen Index durch eine Karte weben können. Kombiniere das mit einer Summe und du hast folgendes in F #:

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

Ich verstehe nicht, wie sich Ihr Code auf den von Ihnen definierten Problembereich bezieht, daher gebe ich meine Version dessen, was Ihr Code tut, und ignoriere den Problembereich (basierend auf dem von Ihnen geschriebenen imperativen Code).

Ziemlich lesbares Haskell (dieser Ansatz kann leicht in jede FP-Sprache übersetzt werden, die eine Listendestrukturierung aufweist und rein und lesbar ist):

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

Manchmal ist der naive einfache Ansatz in haskell so sauberer als der prägnantere Ansatz für Menschen, die weniger an FP gewöhnt sind.

Ein klarer zwingender Ansatz, der immer noch völlig rein ist, ist:

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)

Der Bonus für den zweiten Ansatz ist, dass er in der ST-Monade sehr gut abschneidet.

Obwohl dies sicher ist, wäre die wahrscheinlichste echte Implementierung eines Haskellers die in einer anderen Antwort oben erwähnte Zipwith. zipWithist ein sehr typischer Ansatz und ich glaube, Python kann den Zipping-Ansatz der Kombination von Funktionen und einem Indexer nachahmen, der zugeordnet werden kann.

Wenn Sie nur ein (festes) Tupel haben, warum nicht (in Haskell):

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

Wenn Sie stattdessen eine Liste von Koeffizienten haben, können Sie Folgendes verwenden:

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

oder mit einer Reduzierung, wie Sie es hatten:

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

Es gibt eine allgemeine Reihe von Schritten, mit denen Sie die Lesbarkeit von Funktionsalgorithmen verbessern können:

• Geben Sie Namen in Ihre Zwischenergebnisse ein, anstatt zu versuchen, alles in einer Zeile zu stopfen.
• Verwenden Sie benannte Funktionen anstelle von Lambdas, insbesondere in Sprachen mit ausführlicher Lambda-Syntax. Es ist viel einfacher, so etwas wie evaluateTermeinen langen Lambda-Ausdruck zu lesen . Gerade weil Sie können ein Lambda verwenden nicht unbedingt , dass Sie sollten .
• Wenn eine Ihrer jetzt genannten Funktionen wie etwas aussieht, das ziemlich häufig auftaucht, ist sie wahrscheinlich bereits in der Standardbibliothek enthalten. Umschauen. Meine Python ist ein wenig rostig, aber es sieht so aus, als hätten Sie im Grunde genommen neu erfunden enumerateoder zipWith.
• Wenn Sie die genannten Funktionen und Zwischenergebnisse sehen, können Sie häufig leichter überlegen, was vor sich geht, und es vereinfachen. An diesem Punkt kann es sinnvoll sein, ein Lambda wieder einzubauen oder einige Zeilen wieder zu kombinieren.
• Wenn ein Imperativ für eine Schleife besser lesbar aussieht, ist es wahrscheinlich, dass ein Verständnis gut funktioniert.