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

10

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.

user1358
quelle
7
Nach meiner Erfahrung ist rein funktionaler Code im Sinne der Nichtverwendung veränderlicher Variablen (was auch impliziert for, dass beispielsweise keine Schleifen verwendet werden) ein schlechtes Ziel in Python. Das vernünftige erneute Binden von Variablen und das Nicht-Mutieren von Objekten bietet Ihnen fast alle Vorteile und macht den Code unendlich lesbarer. Da Zahlenobjekte unveränderlich sind und nur zwei lokale Namen neu binden, erkennt Ihre "imperative" Lösung funktionale Programmiertugenden besser als jeder "streng reine" Python-Code.
2
Übrigens: Die Multiplikationsmethode ist die Horner-Methode und bei jedem Schritt effizienter als die Exponentiation, da für die Exponentiation dieselben Multiplikationen und noch einige mehr erforderlich sind.
1
Python ist im lambdaVergleich zu Sprachen mit einer leichteren anonymen Syntaxfunktion notorisch hässlich, wenn Sie mit der Verwendung beginnen . Ein Teil davon trägt wahrscheinlich zum "unreinen" Aussehen bei.
KChaloux
@KChaloux genau das wollte ich sagen. Die Unterstützung der funktionalen Programmierung ist in Python in vielerlei Hinsicht ein nachträglicher Gedanke und zeigt sich auch. Trotzdem denke ich nicht, dass selbst die erste Version so schrecklich unlesbar ist, dass man nicht herausfinden kann, was los ist.
Evicatos
Ich bin wirklich verwirrt von Ihrem Code, während der Problembereich eine mathematische Gleichung hat, die extrem klar ist. Warum verwenden Sie diese mathematische Gleichung nicht einfach wörtlich? Es lässt sich ziemlich leicht in eine Funktion in einer beliebigen Sprache verwandeln ... Sie sind sich nicht sicher, was Sie abbilden oder reduzieren oder iterieren möchten, wenn die Frage nach einer Funktion fragt, die eine einzelne Gleichung auswertet und diese Gleichung angibt - sie fragt nicht Iteration überhaupt ...
Jimmy Hoffa

Antworten:

13

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)] )
aelfric5578
quelle
17
Lassen Sie die eckigen Klammern fallen und geben Sie den Variablen sum(coeff * X**power for power, coeff in enumerate(poly))
aussagekräftigere
1
Es macht mich irgendwie traurig, dass die anderen Antworten so komplex sind. Nutzen Sie die Sprache zu Ihrem Vorteil!
Izkata
Verständnis ist wie eine For-Schleife, die in die funktionale Programmierung "eingeschmuggelt" wird
user1358
7
@ user1358 Nein, es ist syntaktischer Zucker für die Zusammensetzung von mapund filter. Man kann es sich auch als for-Schleife einer bestimmten Form vorstellen, aber Schleifen dieser Form entsprechen dem oben erwähnten Funktionskombinator.
7

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
Steven Evers
quelle
2
Und selbst wenn dies nicht der mapFall ist, sollte es ziemlich einfach sein, eine eigene zu schreiben , solange Sie verstehen, wie dies funktioniert.
KChaloux
4

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.

Jimmy Hoffa
quelle
4

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..]
paul
quelle
1
Es sind KEINE Hausaufgaben! Ganz zu schweigen davon, dass ich bereits 3 Lösungen gemacht habe.
user1358
In der Hälfte der Zeit in Python (einschließlich in diesem Fall) bedeutet "Tupel" "unveränderliche Liste" und ist daher von beliebiger Länge.
offensichtlich willkürliche Länge
user1358
1
Nicht wegen Python, sondern weil Polynom eine beliebige Länge impliziert und eine feste Größe keine große Übung wäre
user1358
1
@delnan Das ist interessant. Ich habe immer tupleeinen Satz von Werten mit fester Größe verstanden, von denen jeder möglicherweise unterschiedliche Typen hat und die nicht hinzugefügt oder daraus entfernt werden können. Ich habe nie wirklich verstanden, warum eine dynamische Sprache mit Listen, die heterogene Eingaben akzeptieren, diese benötigen würde.
KChaloux
3

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.
Karl Bielefeldt
quelle