Come si sostituiscono cicli continuativi con un’alternativa di programmazione funzionale senza ottimizzazione chiamata di coda?

Sto sperimentando uno stile più funzionale nel mio JavaScript; quindi, ho sostituito per cicli con funzioni di utilità come la mappa e ridurre. Tuttavia, non ho trovato una sostituzione funzionale per i cicli while poiché l’ottimizzazione delle chiamate tail non è generalmente disponibile per JavaScript. (Da quello che ho capito, ES6 impedisce alle chiamate tail di far traboccare lo stack ma non ne ottimizza le prestazioni.)

Spiego ciò che ho provato di seguito, ma il TLDR è: Se non ho l’ottimizzazione della coda, qual è il modo funzionale di implementare i loop?

Quello che ho provato:

Creazione di una funzione di utilità “while”:

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

Poiché l’ottimizzazione della coda non è disponibile, potrei riscriverla come:

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

Tuttavia a questo punto mi sembra di aver reso il mio codice più complicato / confuso per chiunque lo usi, dal momento che devo trascinarmi dietro una funzione di utilità personalizzata. L’unico vantaggio pratico che vedo è che mi costringe a rendere il ciclo puro; ma sembra che sarebbe più semplice usare semplicemente un ciclo while regolare e assicurarsi di mantenere tutto puro.

Ho anche provato a capire un modo per creare una funzione generatore che simuli gli effetti di ricorsione / looping e quindi iterare su di esso utilizzando una funzione di utilità come find o reduce. Tuttavia, non ho ancora trovato un modo leggibile per farlo.

Infine, la sostituzione di loop con le funzioni di utilità rende più evidente ciò che sto cercando di realizzare (ad esempio, fare una cosa per ogni elemento, controllare se ogni elemento supera un test, ecc.). Tuttavia, mi sembra che un ciclo while esprima già ciò che sto cercando di realizzare (ad esempio, iterare fino a quando non troviamo un numero primo, iterare finché la risposta non è sufficientemente ottimizzata, ecc.).

Quindi, dopo tutto questo, la mia domanda complessiva è: se ho bisogno di un ciclo while, sto programmando in uno stile funzionale, e non ho accesso all’ottimizzazione delle chiamate tail, quindi qual è la strategia migliore.

Un esempio in JavaScript

Ecco un esempio utilizzando JavaScript. Attualmente, la maggior parte dei browser non supporta l’ottimizzazione delle chiamate tail e pertanto lo snippet seguente non funzionerà

 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 

Programmare nel senso del paradigma funzionale significa che siamo guidati dai tipi per esprimere i nostri algoritmi.

Per trasformare una funzione ricorsiva di coda in una versione sicura per lo stack dobbiamo considerare due casi:

  • caso base
  • caso ricorsivo

Dobbiamo fare una scelta e questo va bene con i sindacati taggati. Tuttavia, Javascript non ha questo tipo di dati, quindi dobbiamo crearne uno o ricorrere alle codifiche Object .

Oggetto codificato

 // 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(); 

Vedi anche spiegare quale (dai documenti Ramda)

Crea un elenco da un valore seme. Accetta una funzione iteratore, che restituisce false per interrompere l’iterazione o un array di lunghezza 2 contenente il valore da aggiungere all’elenco risultante e il seed da utilizzare nella successiva chiamata alla funzione iteratore.

 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));