Werte in der Funktionsprogrammierung „merken“

20

Ich habe mich entschlossen, funktionale Programmierung zu erlernen. Bisher war es eine Explosion und ich habe das Licht sozusagen gesehen. Leider kenne ich keinen funktionalen Programmierer, von dem ich Fragen abprallen kann. Einführung in Stack Exchange.

Ich nehme an einem Web- / Softwareentwicklungskurs teil, aber mein Kursleiter ist nicht mit funktionaler Programmierung vertraut. Er ist in Ordnung, wenn ich es benutze, und er hat mich gebeten, ihm zu erklären, wie es funktioniert, damit er meinen Code besser lesen kann.

Ich entschied, dass der beste Weg, dies zu tun, darin besteht, eine einfache mathematische Funktion zu veranschaulichen, wie das Erhöhen eines Wertes zu einer Potenz. Theoretisch könnte ich das leicht mit einer vorgefertigten Funktion machen, aber das würde den Zweck eines Beispiels zunichte machen.

Wie auch immer, ich habe einige Schwierigkeiten herauszufinden, wie ich einen Wert halten kann. Da dies eine funktionale Programmierung ist, kann ich die Variable nicht ändern. Wenn ich das unbedingt codieren würde, würde es ungefähr so ​​aussehen:

(Das Folgende ist alles Pseudocode)

f(x,y) {
  int z = x;
  for(int i = 0, i < y; i++){
    x = x * z;
  }
  return x;
}

Bei der funktionalen Programmierung war ich mir nicht sicher. Das habe ich mir ausgedacht:

f(x,y,z){
  if z == 'null',
    f(x,y,x);
  else if y > 1,
    f(x*z,y-1,z);
  else
    return x;
}

Ist das richtig? zIn beiden Fällen muss ich einen Wert halten , aber ich war mir nicht sicher, wie ich das in der Funktionsprogrammierung machen sollte. Theoretisch hat es funktioniert, aber ich war mir nicht sicher, ob es „richtig“ war. Gibt es einen besseren Weg, dies zu tun?

Ucenna
quelle
32
Wenn Sie möchten, dass Ihr Beispiel ernst genommen wird, lassen Sie es eher ein praktisches als ein mathematisches Problem lösen. Es ist eine Art Klischee unter Entwicklern, dass "alles, wofür FP gut ist, mathematische Probleme löst", und wenn Ihr Beispiel eine weitere mathematische Funktion ist, verstärken Sie nur das Stereotyp, anstatt das, was Sie tun, nützlich erscheinen zu lassen.
Mason Wheeler
12
Ihr Versuch ist eigentlich ziemlich gut, wenn Sie reale Überlegungen berücksichtigen. Alle Ihre rekursiven Aufrufe sind Tail Calls , dh die Funktion führt nach dem Aufruf keine weiteren Aktionen aus. Dies bedeutet, dass ein Compiler oder Interpreter , der dies unterstützt, diese optimieren kann, sodass Ihre rekursive Funktion eine feste Menge an Stapelspeicher verwendet, anstatt eine Menge, die proportional zu ist y.
8bittree
1
Vielen Dank für die Unterstützung! Da ich noch sehr neu darin bin, ist mein Pseudocode nicht perfekt. @ MasonWheeler Ich denke, in diesem Fall ist mein Code nicht wirklich dazu gedacht, ernst genommen zu werden. Ich lerne immer noch und der Grund, warum ich FP liebe, ist, dass es Math-y ist. In meinem Beispiel geht es darum, meinem Lehrer zu erklären, warum ich FP verwende. Er versteht nicht wirklich, was es ist, also schien dies eine gute Möglichkeit zu sein, ihm die Vorteile zu zeigen.
Ucenna
5
In welcher Sprache möchten Sie den Code schreiben? Versuchen Sie nicht, einen Stil zu verwenden, der für die von Ihnen verwendete Sprache nicht geeignet ist.
Carsten S
2
Möglicherweise nützlich: en.wikipedia.org/wiki/Memoization
Ethan Bolker

Antworten:

37

Zunächst herzlichen Glückwunsch zum "Sehen des Lichts". Sie haben die Software-Welt zu einem besseren Ort gemacht, indem Sie Ihren Horizont erweitert haben.

Zweitens gibt es ehrlich gesagt keine Möglichkeit, dass ein Professor, der die funktionale Programmierung nicht versteht, irgendetwas Nützliches über Ihren Code aussagt, abgesehen von tritalen Kommentaren wie "Der Einzug sieht nicht gut aus". Dies ist in einem Webentwicklungskurs nicht so überraschend, da die meisten Webentwicklungen mit HTML / CSS / JavaScript durchgeführt werden. Abhängig davon, wie sehr Ihnen das Erlernen der Webentwicklung wirklich am Herzen liegt, möchten Sie sich möglicherweise anstrengen, um die Tools zu erlernen, die Ihr Professor lehrt (auch wenn es schmerzhaft sein mag - ich weiß aus Erfahrung).

Um die gestellte Frage zu beantworten: Wenn Ihr Imperativcode eine Schleife verwendet, ist der Funktionscode wahrscheinlich rekursiv.

(* raises x to the power of y *)
fun pow (x: real) (y: int) : real = 
    if y = 1 then x else x * (pow x (y-1))

Beachten Sie, dass dieser Algorithmus tatsächlich mehr oder weniger mit dem Imperativcode identisch ist. Tatsächlich könnte man die obige Schleife als syntaktischen Zucker für iterative rekursive Prozesse betrachten.

Als Randnotiz, es gibt keine Notwendigkeit für einen Wert von zentweder in Ihrem Imperativ- oder Funktionscode, in der Tat. Sie sollten Ihre Imperativfunktion folgendermaßen geschrieben haben:

def pow(x, y):
    var ret = 1
    for (i = 0; i < y; i++)
         ret = ret * x
    return ret

anstatt die Bedeutung der Variablen zu ändern x.

Gartenkopf
quelle
Dein Rekursiv powist nicht ganz richtig. So wie es ist, pow 3 3kehrt es zurück 81, anstatt 27. Es sollteelse x * pow x (y-1).
8bittree
3
Hoppla, es ist schwer, richtigen Code zu schreiben :) Behoben, und ich habe auch Typanmerkungen hinzugefügt. @Ucenna Es sollte SML sein, aber ich habe es eine Weile nicht mehr benutzt, daher könnte die Syntax leicht falsch sein. Es gibt zu viele verdammte Möglichkeiten, eine Funktion zu deklarieren. Ich kann mich nie an das richtige Schlüsselwort erinnern. Abgesehen von Syntaxänderungen ist der Code in JavaScript identisch.
Gardenhead
2
@jwg Javascript hat einige funktionale Aspekte: Funktionen können verschachtelte Funktionen definieren, Funktionen zurückgeben und Funktionen als Parameter akzeptieren; Es unterstützt Closures mit lexikalischem Gültigkeitsbereich (allerdings ohne dynamischen Gültigkeitsbereich). Es liegt an der Disziplin des Programmierers, keinen Status zu ändern und keine Daten zu mutieren.
Kasper van den Berg
1
@jwg Es gibt keine vereinbarte Definition von "funktionaler" Sprache (auch nicht für "imperativ", "objektorientiert" oder "deklarativ"). Ich versuche, diese Begriffe nach Möglichkeit nicht zu verwenden. Es gibt zu viele Sprachen unter der Sonne, um sie in vier ordentliche Gruppen einzuteilen.
Gardenhead
1
Popularität ist eine schreckliche Metrik, weshalb, wenn jemand erwähnt, dass Sprache oder Werkzeug X besser sein muss, weil es so weit verbreitet ist, ich weiß, dass es sinnlos wäre, dieses Argument fortzusetzen. Ich kenne die ML-Sprachfamilie besser als Haskell persönlich. Aber ich bin mir auch nicht sicher, ob es wahr ist. Ich schätze, die große Mehrheit der Entwickler hat Haskell noch nicht ausprobiert .
Gardenhead
33

Dies ist eigentlich nur ein Nachtrag zur Antwort von gardenhead, aber ich möchte darauf hinweisen, dass es einen Namen für das Muster gibt, das Sie sehen: Falzen.

Bei der funktionalen Programmierung ist eine Falte eine Möglichkeit, eine Reihe von Werten zu kombinieren, die sich einen Wert zwischen den einzelnen Operationen "merken". Erwägen Sie unbedingt das Hinzufügen einer Liste mit Zahlen:

def sum_all(xs):
  total = 0
  for x in xs:
    total = total + x
  return total

Wir nehmen eine Liste von Werten xsund einen Anfangszustand von 0(dargestellt durch totalin diesem Fall). Dann wird für jeden xin xskombinieren wir diesen Wert mit dem aktuellen Zustand nach einigen Kombinationsoperation (in diesem Fall zusätzlich), und das Ergebnis als die Verwendung neuer Zustand. Im Wesentlichen sum_all([1, 2, 3])ist äquivalent zu (3 + (2 + (1 + 0))). Dieses Muster kann in eine Funktion höherer Ordnung extrahiert werden , eine Funktion, die Funktionen als Argumente akzeptiert:

def fold(items, initial_state, combiner_func):
  state = initial_state
  for item in items:
    state = combiner_func(item, state)
  return state

def sum_all(xs):
  return fold(xs, 0, lambda x y: x + y)

Diese Implementierung von foldist immer noch unerlässlich, kann aber auch rekursiv erfolgen:

def fold_recursive(items, initial_state, combiner_func):
  if not is_empty(items):
    state = combiner_func(initial_state, first_item(items))
    return fold_recursive(rest_items(items), state, combiner_func)
  else:
    return initial_state

In Form einer Falte ausgedrückt lautet Ihre Funktion einfach:

def exponent(base, power):
  return fold(repeat(base, power), 1, lambda x y: x * y))

... wobei repeat(x, n)eine Liste von nKopien von zurückgegeben wird x.

Viele Sprachen, insbesondere solche, die auf funktionale Programmierung ausgerichtet sind, bieten eine Faltung in ihrer Standardbibliothek an. Sogar Javascript bietet es unter dem Namen reduce. Wenn Sie feststellen, dass Sie mithilfe der Rekursion einen Wert über eine Schleife hinweg "merken", möchten Sie im Allgemeinen wahrscheinlich eine Falte.

Jack
quelle
8
Lernen Sie auf jeden Fall zu erkennen, wann ein Problem durch eine Falte oder eine Karte gelöst werden kann. In FP können fast alle Loops als Fold oder Map ausgedrückt werden. Daher ist eine explizite Rekursion normalerweise nicht erforderlich.
Carcigenicate
1
In einigen Sprachen können Sie einfach schreibenfold(repeat(base, power), 1, *)
user253751
4
Rico Kahler: Hierbei scanwird im Wesentlichen foldnicht nur die Werteliste zu einem Wert zusammengefasst, sondern jeder Zwischenwert wird auf dem Weg zurückgespuckt, um eine Liste aller Zwischenzustände zu erstellen, die die Falte erstellt hat, anstatt nur die zu erstellen Endzustand. Es ist implementierbar in Bezug auf fold(jede Schleifenoperation ist).
Jack
4
@RicoKahler Und soweit ich das beurteilen kann, sind Verkleinerungen und Falten dasselbe. Haskell verwendet den Begriff "Falz", während Clojure "Reduzieren" bevorzugt. Ihr Verhalten scheint mir das gleiche zu sein.
Carcigenicate
2
@Ucenna: Es ist sowohl eine Variable als auch eine Funktion. In der funktionalen Programmierung sind Funktionen Werte wie Zahlen und Zeichenfolgen. Sie können sie in Variablen speichern, als Argumente an andere Funktionen übergeben, von Funktionen zurückgeben und im Allgemeinen wie andere Werte behandeln. Dies combiner_funcist ein Argument, sum_alldas eine anonyme Funktion übergibt (das ist das lambdaBit - es erstellt einen Funktionswert, ohne ihn zu benennen), die definiert, wie zwei Elemente miteinander kombiniert werden sollen.
Jack
8

Dies ist eine ergänzende Antwort zur Erläuterung von Karten und Falzen. Für die folgenden Beispiele verwende ich diese Liste. Denken Sie daran, dass diese Liste unveränderlich ist und sich daher niemals ändern wird:

var numbers = [1, 2, 3, 4, 5]

In meinen Beispielen verwende ich Zahlen, da sie zu leicht lesbarem Code führen. Denken Sie jedoch daran, dass Falten für alles verwendet werden können, wofür eine traditionelle imperative Schleife verwendet werden kann.

Eine Map nimmt eine Liste von etwas und eine Funktion und gibt eine Liste zurück, die mit der Funktion geändert wurde. Jedes Element wird an die Funktion übergeben und wird zu dem, was die Funktion zurückgibt.

Das einfachste Beispiel hierfür ist das Hinzufügen einer Nummer zu jeder Nummer in einer Liste. Ich werde Pseudocode verwenden, um es sprachunabhängig zu machen:

function add-two(n):
    return n + 2

var numbers2 =
    map(add-two, numbers) 

Wenn Sie drucken numbers2, sehen Sie, [3, 4, 5, 6, 7]welches die erste Liste ist, bei der jedem Element 2 hinzugefügt wurden. Beachten Sie, dass die zu verwendende Funktion add-twoangegeben wurde map.

Fold s sind ähnlich, außer dass die Funktion, die Sie ihnen geben müssen, 2 Argumente annehmen muss. Das erste Argument ist in der Regel der Akkumulator (in einer linken Falte, die am häufigsten sind). Der Akkumulator sind die Daten, die beim Schleifen übertragen werden. Das zweite Argument ist das aktuelle Element der Liste. genau wie oben für die mapFunktion.

function add-together(n1, n2):
    return n1 + n2

var sum =
    fold(add-together, 0, numbers)

Wenn Sie drucken sum, sehen Sie die Summe der Zahlen: 15.

Hier sind die Argumente folddafür:

  1. Dies ist die Funktion, die wir geben die Falte. Die Falte übergibt die Funktion dem aktuellen Akkumulator und dem aktuellen Element der Liste. Was auch immer die Funktion zurückgibt, wird der neue Akku, der beim nächsten Mal an die Funktion übergeben wird. Auf diese Weise "merken" Sie sich Werte, wenn Sie einen Loop im FP-Stil erstellen. Ich habe ihm eine Funktion gegeben, die 2 Zahlen annimmt und sie hinzufügt.

  2. Dies ist der anfängliche Akkumulator. Wie der Akku startet, bevor Elemente in der Liste verarbeitet werden. Wenn Sie Zahlen summieren, wie hoch ist die Gesamtsumme, bevor Sie Zahlen addieren? 0, die ich als zweites Argument übergeben habe.

  3. Schließlich übergeben wir wie bei der Karte auch die Liste der zu verarbeitenden Nummern.

Wenn Falten immer noch keinen Sinn ergeben, ziehen Sie dies in Betracht. Wenn du schreibst:

# Notice I passed the plus operator directly this time, 
#  instead of wrapping it in another function. 
fold(+, 0, numbers)

Sie setzen im Grunde die übergebene Funktion zwischen die einzelnen Elemente in der Liste und fügen den anfänglichen Akkumulator entweder links oder rechts hinzu (je nachdem, ob es sich um eine linke oder eine rechte Falte handelt).

[1, 2, 3, 4, 5]

Wird:

0 + 1 + 2 + 3 + 4 + 5
^ Note the initial accumulator being added onto the left (for a left fold).

Welches entspricht 15.

Verwenden Sie ein, mapwenn Sie eine Liste in eine andere Liste gleicher Länge umwandeln möchten.

Verwenden Sie a, foldwenn Sie eine Liste in einen einzelnen Wert umwandeln möchten, z. B. eine Liste von Zahlen summieren.

Wie @Jorg in den Kommentaren betonte, muss der "Einzelwert" nicht einfach wie eine Zahl sein. es kann sich um ein einzelnes Objekt handeln, einschließlich einer Liste oder eines Tupels! Die Art und Weise, wie ich tatsächlich Falten hatte, bestand darin, eine Karte in Form einer Falte zu definieren . Beachten Sie, wie der Akku eine Liste ist:

function map(f, list):
    fold(
        function(xs, x): # xs is the list that has been processed so far
            xs.add( f(x) ) # Add returns the list instead of mutating it
        , [] # Before any of the list has been processed, we have an empty list
        , list) 

Ehrlich gesagt, wenn Sie erst einmal verstanden haben, werden Sie feststellen, dass fast jede Schleife durch eine Falte oder eine Karte ersetzt werden kann.

Karzigenat
quelle
1
@Ucenna @Ucenna Es gibt ein paar Fehler in Ihrem Code (wie inie definiert zu werden), aber ich denke, Sie haben die richtige Idee. Ein Problem mit Ihrem Beispiel ist: der function ( x) wird jeweils nur ein Element der Liste übergeben, nicht die gesamte Liste. Beim ersten xAufruf wird Ihr anfänglicher Akku ( y) als erstes Argument und das erste Element als zweites Argument übergeben. Beim nächsten Start xwird der neue Akku auf der linken Seite (was auch immer xbeim ersten Mal zurückgegeben wurde) und das zweite Element der Liste als zweites Argument übergeben.
Carcigenicate
1
@Ucenna Nun, da Sie die Grundidee haben, schauen Sie sich Jacks Implementierung noch einmal an.
Carcigenicate
1
@Ucenna: Verschiedene langs haben unterschiedliche Präferenzen, ob die gegebene Funktion zum Falten den Akkumulator als erstes oder zweites Argument verwendet, leider. Einer der Gründe, warum es schön ist, eine kommutative Operation wie Addition zu verwenden, um Falten zu unterrichten.
Jack
3
Msgstr "Verwenden Sie a, foldwenn Sie eine Liste in einen einzelnen Wert umwandeln möchten (wie das Summieren einer Zahlenliste)." - Ich möchte nur darauf hinweisen, dass dieser "Einzelwert" beliebig komplex sein kann ... einschließlich einer Liste! Tatsächlich foldhandelt es sich um eine allgemeine Iterationsmethode, die alles kann, was Iteration kann. ZB mapkann trivial ausgedrückt werden als func map(f, l) = fold((xs, x) => append(xs, f(x)), [], l)Hier ist der "Einzelwert", der von berechnet foldwird, tatsächlich eine Liste.
Jörg W Mittag
2
… Evtl. mit einer Liste machen wollen, kann mit erledigt werden fold. Und es muss keine Liste sein, jede Sammlung, die als leer / nicht leer ausgedrückt werden kann, ist ausreichend. Was im Grunde bedeutet, dass jeder Iterator ausreicht. (Ich denke, das Wort "Katamorphismus" wäre zu viel für eine Einführung für Anfänger :-D)
Jörg W Mittag
1

Es ist schwer, gute Probleme zu finden, die mit der eingebauten Funktionalität nicht gelöst werden können. Und wenn es eingebaut ist, sollte es als Beispiel für einen guten Stil in der Sprache x dienen.

In haskell zum Beispiel haben Sie bereits die Funktion (^)im Prelude.

Oder wenn Sie es programmatischer machen wollen product (replicate y x)

Ich sage nur, dass es schwierig ist, die Stärken eines Stils / einer Sprache zu zeigen, wenn Sie nicht die darin enthaltenen Funktionen verwenden. Es könnte jedoch ein guter Schritt sein, um zu zeigen, wie es hinter den Kulissen funktioniert, aber ich denke, Sie sollten den besten Code in der von Ihnen verwendeten Sprache verwenden und dann der Person von dort helfen, zu verstehen, was bei Bedarf vor sich geht.

Viktor Mellgren
quelle
1
Um diese Antwort logisch mit den anderen zu verknüpfen, sollte beachtet werden, dass dies productnur eine Abkürzungsfunktion foldmit Multiplikation als Funktion und 1 als Ausgangsargument ist und dass dies replicateeine Funktion ist, die einen Iterator (oder eine Liste) erzeugt, wie ich bemerkte über den beiden sind in haskell) im wesentlichen nicht zu unterscheiden, was eine gegebene Anzahl identischer Ausgaben ergibt. Es sollte jetzt leicht verständlich sein, wie diese Implementierung das Gleiche wie die Antwort von @ Jack oben macht, indem nur vordefinierte Sonderfallversionen der gleichen Funktionen verwendet werden, um sie prägnanter zu gestalten.
Periata Breatta