wake-up-neo.net

Wie ersetze ich while-Schleifen durch eine funktionale Programmierungsalternative ohne Rückrufoptimierung?

Ich experimentiere mit einem funktionaleren Stil in meinem JavaScript. daher habe ich für Schleifen mit Utility-Funktionen wie map und reduziere. Ich habe jedoch keinen funktionalen Ersatz für while-Schleifen gefunden, da die Optimierung von Aufrufaufrufen für JavaScript im Allgemeinen nicht verfügbar ist. (Soweit ich weiß, verhindert ES6, dass Tail Calls den Stack überlaufen lassen, aber ihre Leistung nicht optimiert.)

Ich erkläre, was ich unten ausprobiert habe, aber der TLDR lautet: Wenn ich keine Tail Call-Optimierung habe, wie kann ich while-Schleifen funktional implementieren?

Was ich versucht habe:

Erstellen einer Hilfsfunktion "while":

function while(func, test, data) {
  const newData = func(data);
  if(test(newData)) {
    return newData;
  } else {
    return while(func, test, newData);
  }
}

Da die Rückrufoptimierung nicht verfügbar ist, könnte ich dies folgendermaßen umschreiben:

function while(func, test, data) {
  let newData = *copy the data somehow*
  while(test(newData)) {
    newData = func(newData);
  }
  return newData;
}

An diesem Punkt fühlt es sich jedoch an, als habe ich meinen Code für alle anderen Benutzer komplizierter/verwirrender gemacht, da ich eine benutzerdefinierte Dienstprogrammfunktion verwenden muss. Der einzige praktische Vorteil, den ich sehe, ist, dass es mich zwingt, die Schleife rein zu machen. Es scheint jedoch einfacher zu sein, einfach eine normale while-Schleife zu verwenden und sicherzustellen, dass ich alles rein halte.

Ich habe auch versucht, eine Möglichkeit zu finden, eine Generatorfunktion zu erstellen, die die Auswirkungen von Rekursion/Schleifen nachahmt und dann mit einer Hilfsfunktion wie find oder verkleinert. Ich habe jedoch noch keine lesbare Möglichkeit dafür gefunden.

Durch das Ersetzen von Schleifen durch Utility-Funktionen wird schließlich klarer, was ich erreichen möchte (z. B. etwas für jedes Element tun, prüfen, ob jedes Element einen Test besteht, usw.). Es scheint mir jedoch, dass eine while-Schleife bereits ausdrückt, was ich erreichen möchte (z. B. iterieren, bis wir eine Primzahl finden, iterieren, bis die Antwort ausreichend optimiert ist usw.).

Nach all dem ist meine allgemeine Frage: Wenn ich eine while-Schleife brauche, programmiere ich in einem funktionalen Stil, und ich habe keinen Zugriff auf die Optimierung von Rückrufen, was ist die beste Strategie.

29

Ein Beispiel in JavaScript

Hier ist ein Beispiel mit JavaScript. Gegenwärtig unterstützen die meisten Browser keine Tail-Call-Optimierung, weshalb das folgende Snippet fehlschlägt

const repeat = n => f => x =>
  n === 0 ? x : repeat (n - 1) (f) (f(x))
  
console.log(repeat(1e3) (x => x + 1) (0)) // 1000
console.log(repeat(1e5) (x => x + 1) (0)) // Error: Uncaught RangeError: Maximum call stack size exceeded

Trampoline

Wir können diese Einschränkung umgehen, indem wir die Art und Weise ändern, in der wir Wiederholungen schreiben, jedoch nur geringfügig. Anstatt einen Wert direkt oder sofort wiederkehrend zurückzugeben, geben wir einen unserer beiden Trampolintypen zurück, Bounce oder Done. Dann werden wir unsere trampoline -Funktion verwenden, um die Schleife zu behandeln.

// trampoline
const Bounce = (f,x) => ({ isBounce: true, f, x })

const Done = x => ({ isBounce: false, x })

const trampoline = ({ isBounce, f, x }) => {
  while (isBounce)
    ({ isBounce, f, x } = f(x))
  return x
}

// our revised repeat function, now stack-safe
const repeat = n => f => x =>
  n === 0 ? Done(x) : Bounce(repeat (n - 1) (f), f(x))


// apply trampoline to the result of an ordinary call repeat
let result = trampoline(repeat(1e6) (x => x + 1) (0))

// no more stack overflow
console.log(result) // 1000000

Currying verlangsamt die Sache auch ein wenig, aber wir können das mit einer Hilfsfunktion für die Rekursion beheben. Das ist auch schön, weil es das Detail der Trampolin-Implementierung verbirgt und nicht erwartet, dass der Aufrufer den Rückgabewert abprallt. Dies läuft ungefähr doppelt so schnell wie das obige repeat

// aux helper hides trampoline implementation detail
// runs about 2x as fast
const repeat = n => f => x => {
  const aux = (n, x) =>
    n === 0 ? Done(x) : Bounce(x => aux (n - 1, x), f (x))
  return trampoline (aux (n, x))
}

Clojure-Stil loop/recur

Trampoline sind nett und alles, aber es ist ärgerlich, sich Sorgen machen zu müssen, trampoline für den Rückgabewert Ihrer Funktion aufzurufen. Wir sahen die Alternative darin, einen Hilfshelfer zu benutzen, aber komm schon, das nervt auch. Ich bin sicher, einige von Ihnen sind auch nicht besonders an den Wrappern Bounce und Done interessiert.

Clojure erstellt ein spezielles Trampolin-Interface, das die beiden Funktionen loop und recur verwendet - dieses Tandempaar eignet sich für einen bemerkenswert eleganten Ausdruck eines Programms

Oh und es ist auch sehr schnell

const recur = (...values) =>
  ({ recur, values })
  
const loop = run =>
{ let r = run ()
  while (r && r.recur === recur)
    r = run (...r.values)
  return r
}

const repeat = n => f => x =>
  loop
    ( (m = n, r = x) =>
        m === 0
          ? r
          : recur (m - 1, f (r))
    )
  
console.time ('loop/recur')
console.log (repeat (1e6) (x => x + 1) (0)) // 1000000
console.timeEnd ('loop/recur')              // 24 ms

Anfangs wird sich dieser Stil fremd anfühlen, aber im Laufe der Zeit finde ich, dass er bei der Produktion dauerhafter Programme am konsistentesten ist. Die folgenden Kommentare erleichtern Ihnen die Eingabe der ausdrucksreichen Syntax.

const repeat = n => f => x =>
  loop  // begin a loop with
    ( ( m = n   // local loop var m: counter, init with n
      , r = x   // local loop var r: result, init with x
      ) =>
        m === 0 // terminating condition
          ? r   // return result
          : recur    // otherwise recur with 
             ( m - 1 // next m value
             , f (r) // next r value
             )
    )

Die Fortsetzung Monade

Dies ist eines meiner Lieblingsthemen, also werden wir sehen, wie dies mit der Fortsetzung Monade aussieht. Wenn wir loop und recur wiederverwenden, implementieren wir einen stapelsicheren cont, der Operationen mit chain sequenzieren und Operationssequenzen mit runCont ausführen kann. Für repeat ist dies sinnlos (und langsam), aber es ist cool zu sehen, wie die Mechanik von cont in diesem einfachen Beispiel funktioniert -

const identity = x =>
  x

const recur = (...values) =>
  ({ recur, values })
  
const loop = run =>
{ let r = run ()
  while (r && r.recur === recur)
    r = run (...r.values)
  return r
}

// cont : 'a -> 'a cont
const cont = x =>
  k => recur (k, x)

// chain : ('a -> 'b cont) -> 'a cont -> 'b cont
const chain = f => mx =>
  k => recur (mx, x => recur (f (x), k))

// runCont : ('a -> 'b) -> a cont -> 'b
const runCont = f => mx =>
  loop ((r = mx, k = f) => r (k))

const repeat = n => f => x =>
{ const aux = n => x =>
    n === 0 // terminating condition
      ? cont (x) // base case, continue with x
      : chain             // otherise
          (aux (n - 1))   // sequence next operation on
          (cont (f (x)))  // continuation of f(x)

  return runCont  // run continuation
    (identity)    // identity; pass-thru
    (aux (n) (x)) // the continuation returned by aux
}

console.time ('cont monad')
console.log (repeat (1e6) (x => x + 1) (0)) // 1000000
console.timeEnd ('cont monad')              // 451 ms

Y Kombinator

Der Y-Kombinator ist mein Geist-Kombinator. Diese Antwort wäre unvollständig, ohne sie unter den anderen Techniken zu platzieren. Die meisten Implementierungen des Y-Kombinators sind jedoch nicht stapelsicher und laufen über, wenn die vom Benutzer bereitgestellte Funktion zu oft wiederholt wird. Da es bei dieser Antwort nur darum geht, das stapelsichere Verhalten beizubehalten, werden wir Y natürlich auf sichere Weise implementieren - wiederum unter Berufung auf unser zuverlässiges Trampolin.

Y demonstriert die Fähigkeit, einfach zu verwendende, stapelsichere, synchrone unendliche Rekursion zu erweitern, ohne Ihre Funktion zu beeinträchtigen.

const bounce = f => (...xs) =>
  ({ isBounce: true, f, xs })

const trampoline = t => {
  while (t && t.isBounce)
    t = t.f(...t.xs)
  return t
}

// stack-safe Y Combinator
const Y = f => {
  const safeY = f =>
    bounce((...xs) => f (safeY (f), ...xs))
  return (...xs) =>
    trampoline (safeY (f) (...xs))
}

// recur safely to your heart's content
const repeat = Y ((recur, n, f, x) =>
  n === 0
    ? x
    : recur (n - 1, f, f (x)))
  
console.log(repeat (1e5, x => x + 1, 0)) // 10000

Praktikabilität mit while loop

Aber seien wir ehrlich: Das ist eine Menge Zeremonie, wenn wir eine der offensichtlichsten möglichen Lösungen übersehen: Verwenden Sie eine for oder while -Schleife, aber verstecken Sie sie hinter einer funktionalen Schnittstelle

In jeder Hinsicht funktioniert diese repeat -Funktion genauso wie die oben angegebene - mit der Ausnahme, dass diese Funktion ein oder zwei Mal schneller ist (mit Ausnahme der loop/recur Lösung). Heck, es ist wohl auch viel einfacher zu lesen.

Zugegeben, diese Funktion ist vielleicht ein ausgedachtes Beispiel - nicht alle rekursiven Funktionen können so einfach in eine for oder while Schleife konvertiert werden, aber in einem solchen Szenario, in dem es möglich ist, ist es wahrscheinlich am besten, einfach mach es so. Bewahren Sie die Trampoline und Fortsetzungen für schweres Heben auf, wenn eine einfache Schleife nicht ausreicht.

const repeat = n => f => x => {
  let m = n
  while (true) {
    if (m === 0)
      return x
    else
      (m = m - 1, x = f (x))
  }
}

const gadzillionTimes = repeat(1e8)

const add1 = x => x + 1

const result = gadzillionTimes (add1) (0)

console.log(result) // 100000000

setTimeout ist KEINE Lösung für das Stapelüberlaufproblem

OK, also funktioniert , aber nur paradoxerweise. Wenn Ihr Dataset klein ist, brauchen Sie setTimeout nicht, da es keinen Stapelüberlauf gibt. Wenn Ihr Datensatz groß ist und Sie setTimeout als sicheren Rekursionsmechanismus verwenden, können Sie einen Wert nicht nur nicht synchron von Ihrer Funktion zurückgeben, sondern er ist auch so langsam, dass Sie ihn nicht einmal verwenden möchten Ihre Funktion

Einige Leute haben eine Interview-Q & A-Vorbereitungsseite gefunden, die diese schreckliche Strategie fördert

Wie unser repeat mit setTimeout aussehen würde - beachten Sie, dass es auch im Stil der Weitergabe definiert ist - dh wir müssen repeat mit einem Rückruf aufrufen (k) um den endgültigen Wert zu erhalten

// do NOT implement recursion using setTimeout
const repeat = n => f => x => k =>
  n === 0
    ? k (x)
    : setTimeout (x => repeat (n - 1) (f) (x) (k), 0, f (x))
    
// be patient, this one takes about 5 seconds, even for just 1000 recursions
repeat (1e3) (x => x + 1) (0) (console.log)

// comment the next line out for absolute madness
// 10,000 recursions will take ~1 MINUTE to complete
// paradoxically, direct recursion can compute this in a few milliseconds
// setTimeout is NOT a fix for the problem
// -----------------------------------------------------------------------------
// repeat (1e4) (x => x + 1) (0) (console.log)

Ich kann gar nicht genug betonen, wie schlimm das ist. Sogar 1e5 dauert so lange, dass ich es aufgegeben habe, es zu messen. Ich nehme dies nicht in die nachstehenden Benchmarks auf, weil es einfach zu langsam ist, um überhaupt als gangbarer Ansatz angesehen zu werden.


Versprechen

Versprechungen können Berechnungen verketten und sind stapelsicher. Um jedoch mit Promises ein stapelsicheres repeat zu erreichen, müssen wir unseren synchronen Rückgabewert aufgeben, genauso wie wir es mit setTimeout getan haben. Ich biete dies als "Lösung" an, weil es das Problem löst , im Gegensatz zu setTimeout, aber auf eine Art und Weise, die im Vergleich zum Trampolin oder zur Fortsetzung sehr einfach ist Monade. Wie Sie sich vielleicht vorstellen können, ist die Leistung etwas schlecht, aber bei weitem nicht so schlecht wie im obigen Beispiel setTimeout

Erwähnenswert bei dieser Lösung ist, dass die Details der Promise-Implementierung dem Aufrufer vollständig verborgen bleiben. Eine einzelne Fortsetzung wird als viertes Argument angegeben und aufgerufen, wenn die Berechnung abgeschlossen ist.

const repeat = n => f => x => k =>
  n === 0
    ? Promise.resolve(x).then(k)
    : Promise.resolve(f(x)).then(x => repeat (n - 1) (f) (x) (k))
    
// be patient ...
repeat (1e6) (x => x + 1) (0) (x => console.log('done', x))

Benchmarks

Im Ernst, die while -Schleife ist um ein Vielfaches schneller - etwa 100-mal schneller (im Vergleich vom Besten zum Schlechtesten - aber ohne asynchrone Antworten: setTimeout und Promise)

// sync
// -----------------------------------------------------------------------------
// repeat implemented with basic trampoline
console.time('A')
console.log(tramprepeat(1e6) (x => x + 1) (0))
console.timeEnd('A')
// 1000000
// A 114 ms

// repeat implemented with basic trampoline and aux helper
console.time('B')
console.log(auxrepeat(1e6) (x => x + 1) (0))
console.timeEnd('B')
// 1000000
// B 64 ms

// repeat implemented with cont monad
console.time('C')
console.log(contrepeat(1e6) (x => x + 1) (0))
console.timeEnd('C')
// 1000000
// C 33 ms

// repeat implemented with Y
console.time('Y')
console.log(yrepeat(1e6) (x => x + 1) (0))
console.timeEnd('Y')
// 1000000
// Y 544 ms

// repeat implemented with while loop
console.time('D')
console.log(whilerepeat(1e6) (x => x + 1) (0))
console.timeEnd('D')
// 1000000
// D 4 ms

// async
// -----------------------------------------------------------------------------

// repeat implemented with Promise
console.time('E')
promiserepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('E')
// 1000000
// E 2224 ms

// repeat implemented with setTimeout; FAILED
console.time('F')
timeoutrepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('F')
// ...
// too slow; didn't finish after 3 minutes

Steinzeit JavaScript

Die oben genannten Techniken werden mit neueren ES6-Syntaxen demonstriert. Sie können jedoch ein Trampolin in der frühestmöglichen Version von JavaScript implementieren. Es werden nur while und erstklassige Funktionen benötigt

Im Folgenden verwenden wir Steinzeit-Javascript, um zu demonstrieren, dass eine unendliche Rekursion möglich und performant ist, ohne dass unbedingt ein synchroner Rückgabewert geopfert werden muss - 100.000.000 Rekursionen in weniger als 6 Sekunden - dies ist ein dramatischer Unterschied zu setTimeout, der nur 1.000 Rekursionen in der gleichen Zeit.

function trampoline (t) {
  while (t && t.isBounce)
    t = t.f (t.x);
  return t.x;
}

function bounce (f, x) {
  return { isBounce: true, f: f, x: x };
}

function done (x) {
  return { isBounce: false, x: x };
}

function repeat (n, f, x) {
  function aux (n, x) {
    if (n === 0)
      return done (x);
    else 
      return bounce (function (x) { return aux (n - 1, x); }, f (x));
  }
  return trampoline (aux (n, x));
}

console.time('JS1 100K');
console.log (repeat (1e5, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100K');
// 100000
// JS1 100K: 15ms

console.time('JS1 100M');
console.log (repeat (1e8, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100M');
// 100000000
// JS1 100K: 5999ms

Nicht blockierende unendliche Rekursion mit steinzeitlichem JavaScript

Wenn Sie aus irgendeinem Grund eine nicht blockierende (asynchrone) unendliche Rekursion wünschen, können wir uns darauf verlassen, dass setTimeout eine Single aufschiebt Frame zu Beginn der Berechnung. Dieses Programm verwendet auch steinzeitliches Javascript und berechnet 100.000.000 Rekursionen in weniger als 8 Sekunden, diesmal jedoch auf nicht blockierende Weise.

Dies zeigt, dass es nichts Besonderes ist, eine nicht blockierende Anforderung zu haben. Eine while Schleife und erstklassige Funktionen sind nach wie vor die einzige Grundvoraussetzung, um eine stapelsichere Rekursion ohne Leistungseinbußen zu erreichen

In einem modernen Programm würden wir angesichts von Promises den setTimeout -Aufruf durch ein einziges Promise ersetzen.

function donek (k, x) {
  return { isBounce: false, k: k, x: x };
}

function bouncek (f, x) {
  return { isBounce: true, f: f, x: x };
}

function trampolinek (t) {
  // setTimeout is called ONCE at the start of the computation
  // NOT once per recursion
  return setTimeout(function () {
    while (t && t.isBounce) {
      t = t.f (t.x);
    }
    return t.k (t.x);
  }, 0);
}

// stack-safe infinite recursion, non-blocking, 100,000,000 recursions in under 8 seconds
// now repeatk expects a 4th-argument callback which is called with the asynchronously computed result
function repeatk (n, f, x, k) {
  function aux (n, x) {
    if (n === 0)
      return donek (k, x);
    else
      return bouncek (function (x) { return aux (n - 1, x); }, f (x));
  }
  return trampolinek (aux (n, x));
}

console.log('non-blocking line 1')
console.time('non-blocking JS1')
repeatk (1e8, function (x) { return x + 1; }, 0, function (result) {
  console.log('non-blocking line 3', result)
  console.timeEnd('non-blocking JS1')
})
console.log('non-blocking line 2')

// non-blocking line 1
// non-blocking line 2
// [ synchronous program stops here ]
// [ below this line, asynchronous program continues ]
// non-blocking line 3 100000000
// non-blocking JS1: 7762ms
68
user633183

Programmierung im Sinne des funktionalen Paradigmas bedeutet, dass wir uns von Typen leiten lassen, um unsere Algorithmen auszudrücken.

Um eine rekursive Tail-Funktion in eine stacksichere Version umzuwandeln, müssen wir zwei Fälle berücksichtigen:

  • basisfall
  • rekursiver Fall

Wir müssen eine Wahl treffen, und das passt gut zu den markierten Gewerkschaften. Javascript hat jedoch keinen solchen Datentyp, also müssen wir entweder einen erstellen oder auf Object-Kodierungen zurückgreifen.

Objekt kodiert

// simulate a tagged union with two Object types

const Loop = x =>
  ({value: x, done: false});
  
const Done = x =>
  ({value: x, done: true});

// trampoline

const tailRec = f => (...args) => {
  let step = Loop(args);

  do {
    step = f(Loop, Done, step.value);
  } while (!step.done);

  return step.value;
};

// stack-safe function

const repeat = n => f => x =>
  tailRec((Loop, Done, [m, y]) => m === 0
    ? Done(y)
    : Loop([m - 1, f(y)])) (n, x);

// run...

const inc = n =>
  n + 1;

console.time();
console.log(repeat(1e6) (inc) (0));
console.timeEnd();

Funktion kodiert

Alternativ können wir eine echte markierte Union mit einer Funktionskodierung erstellen. Nun ist unser Stil den reifen Funktionssprachen viel näher gekommen:

// type/data constructor

const Type = Tcons => (tag, Dcons) => {
  const t = new Tcons();
  t.run = cases => Dcons(cases);
  t.tag = tag;
  return t;
};

// tagged union specific for the case

const Step = Type(function Step() {});

const Done = x =>
  Step("Done", cases => cases.Done(x));
  
const Loop = args =>
  Step("Loop", cases => cases.Loop(args));

// trampoline

const tailRec = f => (...args) => {
  let step = Loop(args);

  do {
    step = f(step);
  } while (step.tag === "Loop");

  return step.run({Done: id});
};

// stack-safe function

const repeat = n => f => x => 
  tailRec(step => step.run({
    Loop: ([m, y]) => m === 0 ? Done(y) : Loop([m - 1, f(y)]),
    Done: y => Done(y)
  })) (n, x);

// run...

const inc = n => n + 1;
const id = x => x;

console.log(repeat(1e6) (inc) (0));

2
user6445533

Siehe auch aufklappen which (von Ramda docs)

Erzeugt eine Liste aus einem Startwert. Akzeptiert eine Iteratorfunktion, die gibt entweder false zurück, um die Iteration zu stoppen, oder ein Array der Länge 2 enthält den Wert, der der Ergebnisliste hinzugefügt werden soll, und den Startwert wird beim nächsten Aufruf der Iteratorfunktion verwendet.

var r = n => f => x => x > n ? false : [x, f(x)];
var repeatUntilGreaterThan = n => f => R.unfold(r(n)(f), 1);
console.log(repeatUntilGreaterThan(10)(x => x + 1));
<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.22.1/ramda.min.js"></script>

0
gpilotino

Ich habe viel über diese Frage nachgedacht. Vor kurzem bin ich auf die Notwendigkeit einer funktionellen While-Schleife gestoßen. 

Es scheint mir, dass das einzige, was diese Frage wirklich will, eine Möglichkeit ist, eine while-Schleife zu integrieren. Es gibt IS eine Möglichkeit, dies mit einem Verschluss zu tun.

"some string "+(a=>{
   while(comparison){
      // run code
   }
   return result;
})(somearray)+" some more"

Wenn Sie dagegen etwas von einem Array abkoppeln möchten, können Sie auch die reduzierte Methode verwenden. 

somearray.reduce((r,o,i,a)=>{
   while(comparison){
      // run code
   }
   a.splice(1); // This would ensure only one call.
   return result;
},[])+" some more"

Nichts davon verwandelt unsere while-Schleife im Kern in eine Funktion. Es erlaubt uns jedoch die Verwendung einer Inline-Schleife. Und ich wollte das einfach mit jedem teilen, dem dies helfen könnte.

0
bronkula