Was sind die funktionalen Entsprechungen von Imperativ-Break-Anweisungen und anderen Schleifenprüfungen?

Nehmen wir an, ich habe die folgende Logik. Wie schreibt man das in Functional Programming?

    public int doSomeCalc(int[] array)
    {
        int answer = 0;
        if(array!=null)
        {
            for(int e: array)
            {
                answer += e;
                if(answer == 10) break;
                if(answer == 150) answer += 100;
            }
        }
        return answer;
    }

Die Beispiele in den meisten Blogs, Artikeln ... Ich sehe nur den einfachen Fall einer einfachen mathematischen Funktion, die 'Summe' sagt. Aber ich habe eine ähnliche Logik wie oben in Java geschrieben und möchte diese in Clojure auf funktionalen Code migrieren. Wenn wir dies in FP nicht tun können, wird dies in den Werbeaktionen für FP nicht explizit angegeben.

Ich weiß, dass der obige Code absolut unerlässlich ist. Es wurde nicht mit dem Gedanken geschrieben, es in Zukunft auf FP zu migrieren.

Das nächste Äquivalent zum Durchlaufen eines Arrays in den meisten funktionalen Sprachen ist eine foldFunktion, dh eine Funktion, die eine benutzerdefinierte Funktion für jeden Wert des Arrays aufruft und einen akkumulierten Wert entlang der Kette weitergibt. In vielen funktionalen Sprachen wird foldes durch eine Reihe zusätzlicher Funktionen ergänzt, die zusätzliche Funktionen bieten, einschließlich der Option, bei bestimmten Bedingungen vorzeitig zu stoppen. In faulen Sprachen (z. B. Haskell) kann ein vorzeitiges Stoppen einfach dadurch erreicht werden, dass die Liste nicht weiter ausgewertet wird, wodurch niemals zusätzliche Werte generiert werden. Wenn ich Ihr Beispiel auf Haskell übersetze, würde ich es folgendermaßen schreiben:

doSomeCalc :: [Int] -> Int
doSomeCalc values = foldr1 combine values
  where combine v1 v2 | v1 == 10  = v1
                      | v1 == 150 = v1 + 100 + v2
                      | otherwise = v1 + v2

Wenn Sie die Syntax von Haskell nicht kennen, können Sie dies zeilenweise wie folgt aufteilen:

doSomeCalc :: [Int] -> Int

Definiert den Typ der Funktion, akzeptiert eine Liste von Ints und gibt einen einzelnen Int zurück.

doSomeCalc values = foldr1 combine values

Der Hauptteil der Funktion: Argument angegeben values, Rückgabe foldr1mit Argumenten aufgerufen combine(die wir unten definieren werden) und values. foldr1ist eine Variante des Fold-Primitivs, die mit dem auf den ersten Wert der Liste gesetzten Akkumulator beginnt (daher der 1im Funktionsnamen angegebene) und ihn dann mit der vom Benutzer angegebenen Funktion von links nach rechts kombiniert (was normalerweise als Rechtsfalte bezeichnet wird). daher das rim Funktionsnamen). Ist foldr1 f [1,2,3]also gleichbedeutend mit f 1 (f 2 3)(oder f(1,f(2,3))in konventioneller C-ähnlicher Syntax).

  where combine v1 v2 | v1 == 10  = v1

Definieren der combinelokalen Funktion: Sie erhält zwei Argumente v1und v2. Wenn v110 ist, kehrt es gerade zurück v1. In diesem Fall wird v2 nie ausgewertet , sodass die Schleife hier anhält.

                      | v1 == 150 = v1 + 100 + v2

Wenn alternativ v1 den Wert 150 hat, werden weitere 100 hinzugefügt und v2 hinzugefügt.

                      | otherwise = v1 + v2

Und wenn keine dieser Bedingungen zutrifft, addieren Sie einfach v1 zu v2.

Diese Lösung ist etwas spezifisch für Haskell, da die Tatsache, dass eine rechte Falte endet, wenn die Kombinationsfunktion ihr zweites Argument nicht auswertet, durch die verzögerte Auswertungsstrategie von Haskell verursacht wird. Ich kenne Clojure nicht, aber ich glaube, es wird streng ausgewertet, daher würde ich erwarten, dass es eine foldFunktion in seiner Standardbibliothek enthält, die eine spezielle Unterstützung für die vorzeitige Beendigung beinhaltet. Dies wird oft genannt foldWhile, foldUntiloder ähnliches.

Ein kurzer Blick auf die Dokumentation der Clojure-Bibliothek zeigt, dass sie sich in der Benennung von den meisten funktionalen Sprachen ein wenig unterscheidet und foldnicht das ist, wonach Sie suchen (es handelt sich um einen fortgeschritteneren Mechanismus zur Ermöglichung paralleler Berechnungen), reduceder jedoch direkter ist Äquivalent. Eine vorzeitige Beendigung liegt vor, wenn die reducedFunktion innerhalb Ihrer Kombinationsfunktion aufgerufen wird. Ich bin mir nicht 100% sicher, ob ich die Syntax verstehe, aber ich vermute, dass Sie nach so etwas suchen:

(reduce 
    (fn [v1 v2]
        (if (= v1 10) 
             (reduced v1)
             (+ v1 v2 (if (= v1 150) 100 0))))
    array)

NB: Beide Übersetzungen, Haskell und Clojure, sind für diesen speziellen Code nicht ganz richtig. Sie vermitteln jedoch den allgemeinen Kern der Sache - siehe Diskussion in den Kommentaren unten für spezifische Probleme mit diesen Beispielen.

Sie können es leicht in eine Rekursion umwandeln. Und es hat einen schönen schwanzoptimierten rekursiven Aufruf.

Pseudocode:

public int doSomeCalc(int[] array)
{
    return doSomeCalcInner(array, 0);
}

public int doSomeCalcInner(int[] array, int answer)
{
    if (array is empty) return answer;

    // not sure how to efficiently implement head/tails array split in clojure
    var head = array[0] // first element of array
    var tail = array[1..] // remainder of array

    answer += head;
    if (answer == 10) return answer;
    if (answer == 150) answer += 100;

    return doSomeCalcInner(tail, answer);
}

Die Antwort von Jules gefällt mir sehr gut , aber ich wollte zusätzlich auf etwas hinweisen, was die Leute an fauler funktionaler Programmierung oft vermissen, nämlich, dass nicht alles "in the loop" sein muss. Beispielsweise:

baseSums = scanl (+) 0

offsets = scanl (\offset sum -> if sum == 150 then offset + 100 else offset) 0

zipWithOffsets xs = zipWith (+) xs (offsets xs)

stopAt10 xs = if 10 `elem` xs then 10 else last xs

result = stopAt10 . zipWithOffsets . baseSums

result [1..]         -- 10
result [11..1000000] -- 500000499945

Sie können sehen, dass jeder Teil Ihrer Logik in einer separaten Funktion berechnet und dann zusammengesetzt werden kann. Dies ermöglicht kleinere Funktionen, die in der Regel leichter zu beheben sind. In Ihrem Spielzeugbeispiel erhöht dies möglicherweise die Komplexität, als sie entfernt, aber im Code der realen Welt sind die Funktionen zum Aufteilen oft viel einfacher als das Ganze.

Die meisten Listenverarbeitung Beispiele finden Sie Funktionen verwenden , wie sehen map, filter, sumetc. , die auf der Liste arbeiten als Ganzes. In Ihrem Fall haben Sie jedoch eine bedingte vorzeitige Beendigung - ein eher ungewöhnliches Muster, das von den üblichen Listenoperationen nicht unterstützt wird. Sie müssen also eine Abstraktionsebene ausklappen und eine Rekursion verwenden - was auch dem imperativen Beispiel näher kommt.

Dies ist eine ziemlich direkte (wahrscheinlich nicht idiomatische) Übersetzung in Clojure:

(defn doSomeCalc 
  ([lst] (doSomeCalc lst 0))
  ([lst sum]
    (if (empty? lst) sum
        (if (= sum 10) sum
            (let [sum (+ sum (first lst))]
                 [sum (if (= sum 150) (+ sum 100) sum)]
               (recur (rest lst) sum))))))) 

Edit: Jules weisen darauf hin , dass reducein Clojure tun vorzeitiges Ausscheiden unterstützen. Dies zu benutzen ist eleganter:

(defn doSomeCalc [lst]  
  (reduce (fn [sum val]
    (if (= sum 10) (reduced sum)
        (let [sum (+ sum val)]
             [sum (if (= sum 150) (+ sum 100) sum)]
           sum))
   lst)))

Auf jeden Fall können Sie in funktionalen Sprachen alles tun, wie Sie es in imperativen Sprachen können. Oft müssen Sie jedoch Ihre Denkweise etwas ändern, um eine elegante Lösung zu finden. Bei der imperativen Codierung denken Sie daran, eine Liste schrittweise zu verarbeiten, während Sie bei funktionalen Sprachen nach einer Operation suchen, die auf alle Elemente in der Liste angewendet werden kann.

Wie andere Antworten zeigen, hat Clojure reduceddafür gesorgt, dass Reduzierungen vorzeitig eingestellt werden:

(defn some-calc [coll]
  (reduce (fn [answer e]
            (let [answer (+ answer e)]
               (case answer
                 10  (reduced answer)
                 150 (+ answer 100)
                 answer)))
          0 coll))

Dies ist die beste Lösung für Ihre spezielle Situation. Sie können auch eine Menge Kilometer aus der Kombination bekommen reducedmit transduce, was Sie Wandler verwenden kann , um aus map, filteretc. Aber es ist weit von einer vollständigen Antwort auf Ihre allgemeine Frage ist.

Escape-Fortsetzungen sind eine verallgemeinerte Version von break- und return-Anweisungen. Sie sind in einigen Schemes ( call-with-escape-continuation), Common Lisp ( block+ return, catch+ throw) und sogar C ( setjmp+ longjmp) direkt implementiert . Allgemeinere begrenzte oder nicht begrenzte Fortsetzungen wie im Standardschema oder als Fortsetzungsmonaden in Haskell und Scala können auch als Escape-Fortsetzungen verwendet werden.

In Racket könnten Sie beispielsweise Folgendes verwenden let/ec:

(define (some-calc ls)
  (let/ec break ; let break be an escape continuation
    (foldl (lambda (answer e)
             (let ([answer (+ answer e)])
               (case answer
                 [(10)  (break answer)] ; return answer immediately
                 [(150) (+ answer 100)]
                 [else  answer])))
           0 ls)))

Viele andere Sprachen haben auch Escape Continuation-ähnliche Konstrukte in Form von Ausnahmebehandlung. In Haskell könnte man auch eine der verschiedenen Fehlermonaden mit verwenden foldM. Da es sich in erster Linie um Fehlerbehandlungskonstrukte handelt, die Ausnahmen oder Fehlermonaden für frühe Rückgaben verwenden, ist dies in der Regel kulturell inakzeptabel und möglicherweise recht langsam.

Sie können auch von Funktionen höherer Ordnung zu Schlussanrufen wechseln.

Wenn Sie Schleifen verwenden, geben Sie die nächste Iteration automatisch ein, wenn Sie das Ende des Schleifenkörpers erreichen. Sie können die nächste Iteration frühzeitig mit eingeben continueoder die Schleife mit break(oder return) verlassen. Wenn Sie Tail-Aufrufe (oder das loopKonstrukt von Clojure, das die Tail-Rekursion nachahmt) verwenden, müssen Sie immer einen expliziten Aufruf ausführen, um die nächste Iteration einzugeben. Um die Schleife zu beenden, rufen Sie einfach nicht rekursiv auf, sondern geben den Wert direkt ein:

(defn some-calc [coll]
  (loop [answer 0, [e es :as coll] coll]
    (if (empty? coll)
      answer
      (let [answer (+ answer e)]
        (case answer
          10 answer
          150 (recur (+ answer 100) es)
          (recur answer es))))))

Der komplizierte Teil ist die Schleife. Beginnen wir damit. Eine Schleife wird normalerweise in einen funktionalen Stil umgewandelt, indem die Iteration mit einer einzelnen Funktion ausgedrückt wird. Eine Iteration ist eine Transformation der Schleifenvariablen.

Hier ist eine funktionale Implementierung einer allgemeinen Schleife:

loop : v -> (v -> v) -> (v -> Bool) -> v
loop init iter cond_to_cont = 
    if cond_to_cont init 
        then loop (iter init) iter cond
        else init

Es dauert (ein Anfangswert der Schleifenvariablen, die Funktion, die eine einzelne Iteration [in der Schleifenvariablen] ausdrückt) (eine Bedingung, um die Schleife fortzusetzen).

In Ihrem Beispiel wird eine Schleife in einem Array verwendet, die ebenfalls unterbrochen wird. Diese Fähigkeit in Ihrer imperativen Sprache ist in die Sprache selbst eingebettet. In der funktionalen Programmierung wird eine solche Fähigkeit normalerweise auf Bibliotheksebene implementiert. Hier ist eine mögliche Implementierung

module Array (foldlc) where

foldlc : v -> (v -> e -> v) -> (v -> Bool) -> Array e -> v
foldlc init iter cond_to_cont arr = 
    loop 
        (init, 0)
        (λ (val, next_pos) -> (iter val (at next_pos arr), next_pos + 1))
        (λ (val, next_pos) -> and (cond_to_cont val) (next_pos < size arr))

Drin :

Ich benutze ein ((val, next_pos)) Paar, das die außerhalb sichtbare Schleifenvariable und die Position im Array enthält, die diese Funktion verbirgt.

Die Iterationsfunktion ist etwas komplexer als in der allgemeinen Schleife. Mit dieser Version kann das aktuelle Element des Arrays verwendet werden. [Es ist in Curryform .]

Solche Funktionen werden üblicherweise "fold" genannt.

Ich setze ein "l" in den Namen, um anzuzeigen, dass die Akkumulation der Elemente des Arrays linksassoziativ erfolgt. die Gewohnheit imperativer Programmiersprachen nachzuahmen, ein Array vom niedrigen zum hohen Index zu durchlaufen.

Ich habe ein "c" in den Namen eingefügt, um anzuzeigen, dass diese Fold-Version eine Bedingung annimmt, die steuert, ob und wann die Schleife vorzeitig gestoppt werden soll.

Natürlich sind solche Hilfsprogrammfunktionen wahrscheinlich in der Basisbibliothek verfügbar, die mit der verwendeten funktionalen Programmiersprache geliefert wird. Ich habe sie hier zur Demonstration geschrieben.

Nachdem wir alle Tools haben, die im Imperativfall in der Sprache verfügbar sind, können wir uns an die Implementierung der spezifischen Funktionalität Ihres Beispiels wenden.

Die Variable in Ihrer Schleife ist ein Paar ('answer', ein Boolescher Wert, der codiert, ob fortgefahren werden soll).

iter : (Int, Bool) -> Int -> (Int, Bool)
iter (answer, cont) collection_element = 
  let new_answer = answer + collection_element
  in case new_answer of
    10 -> (new_answer, false)
    150 -> (new_answer + 100, true)
    _ -> (new_answer, true)

Beachten Sie, dass ich eine neue "Variable" "new_answer" verwendet habe. Dies liegt daran, dass ich in der funktionalen Programmierung den Wert einer bereits initialisierten "Variablen" nicht ändern kann. Ich mache mir keine Sorgen um die Leistung, der Compiler kann den Speicher von 'answer' für 'new_answer' über die Lebenszeitanalyse wiederverwenden, wenn er dies für effizienter hält.

Dies in unsere zuvor entwickelte Schleifenfunktion zu integrieren:

doSomeCalc :: Array Int -> Int
doSomeCalc arr = fst (Array.foldlc (0, true) iter snd arr)

"Array" ist hier der Name des Moduls, dessen Exportfunktion foldlc lautet.

"Faust", "Sekunde" stehen für Funktionen, die die erste, zweite Komponente ihres Paarparameters zurückgeben

fst : (x, y) -> x
snd : (x, y) -> y

In diesem Fall erhöht der "punktfreie" Stil die Lesbarkeit der Implementierung von doSomeCalc:

doSomeCalc = Array.foldlc (0, true) iter snd >>> fst

(>>>) ist Funktionszusammensetzung: (>>>) : (a -> b) -> (b -> c) -> (a -> c)

Es ist dasselbe wie oben, nur der Parameter "arr" wird auf beiden Seiten der Definitionsgleichung weggelassen.

Eine letzte Sache: Prüfung auf Groß- und Kleinschreibung (Array == Null). In besser gestalteten Programmiersprachen, aber auch in schlecht gestalteten Sprachen mit einigen grundlegenden Disziplinen verwendet man eher einen optionalen Typ , um Nichtexistenz auszudrücken. Das hat nicht viel mit funktionaler Programmierung zu tun, worum es letztendlich geht, also beschäftige ich mich nicht damit.

Schreiben Sie die Schleife zunächst leicht um, sodass jede Iteration der Schleife entweder vorzeitig beendet wird oder answergenau einmal mutiert :

    public int doSomeCalc(int[] array)
    {
        int answer = 0;
        if(array!=null)
        {
            for(int e: array)
            {
                if(answer + e == 10) return answer + e;
                else if(answer + e == 150) answer = answer + e + 100;
                else answer = answer + e;
            }
        }
        return answer;
    }

Es sollte klar sein, dass das Verhalten dieser Version genau dasselbe ist wie zuvor, aber jetzt ist es viel einfacher, sie in einen rekursiven Stil umzuwandeln. Hier ist eine direkte Übersetzung von Haskell:

doSomeCalc :: [Int] -> Int
doSomeCalc = recurse 0
  where recurse :: Int -> [Int] -> Int
        recurse answer [] = answer
        recurse answer (e:array)
          | answer + e == 10 = answer + e
          | answer + e == 150 = recurse (answer + e + 100) array
          | otherwise = recurse (answer + e) array

Jetzt ist es rein funktional, aber wir können es sowohl vom Standpunkt der Effizienz als auch der Lesbarkeit aus verbessern, indem wir eine Falte anstelle einer expliziten Rekursion verwenden:

import Control.Monad (foldM)

doSomeCalc :: [Int] -> Int
doSomeCalc = either id id . foldM go 0
  where go :: Int -> Int -> Either Int Int
        go answer e
          | answer + e == 10 = Left (answer + e)
          | answer + e == 150 = Right (answer + e + 100)
          | otherwise = Right (answer + e)

In diesem Zusammenhang wird Leftfrühzeitig mit seinem Wert beendet und Rightdie Rekursion mit seinem Wert fortgesetzt.

Dies könnte jetzt ein bisschen mehr vereinfacht werden:

import Control.Monad (foldM)

doSomeCalc :: [Int] -> Int
doSomeCalc = either id id . foldM go 0
  where go :: Int -> Int -> Either Int Int
        go answer e
          | answer' == 10 = Left 10
          | answer' == 150 = Right 250
          | otherwise = Right answer'
          where answer' = answer + e

Dies ist besser als der endgültige Haskell-Code, aber es ist jetzt etwas weniger klar, wie er auf das ursprüngliche Java zurückgeht.