Werte in der Funktionsprogrammierung „merken“

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?

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.

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.

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.

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.