¿Cómo puedo reemplazar los bucles while con una alternativa de programación funcional sin optimización de llamadas de cola?

Un ejemplo en JavaScript

Aquí hay un ejemplo usando JavaScript. Actualmente, la mayoría de los navegadores no admiten la optimización de llamadas de cola y, por lo tanto, el siguiente fragmento fallará

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

Trampolines

Podemos evitar esta limitación cambiando la forma en que escribimos repeat, pero solo ligeramente. En lugar de devolver un valor directamente o inmediatamente recurrente, devolveremos uno de nuestros dos tipos de trampolín, Bounce o Done. Luego usaremos nuestra función trampoline para manejar el bucle.

// 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 ralentiza un poco las cosas también, pero podemos remediarlo usando una función auxiliar para la recursión. Esto también es bueno porque oculta el detalle de implementación de trampolín y no espera que la persona que llama rebote el valor de retorno. Esto corre aproximadamente el doble de rápido que el anterior 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))
}

Estilo clojure loop/recur

Los trampolines son agradables y todo, pero es un poco molesto tener que preocuparse por llamar a trampoline en el valor de retorno de su función. Vimos que la alternativa era usar un ayudante auxiliar, pero vamos, eso también es un poco molesto. Estoy seguro de que algunos de ustedes no están demasiado interesados en los envoltorios Bounce y Done, también.

Clojure crea una interfaz de trampolín especializada que utiliza un par de funciones, loop y recur - este par tándem se presta a una expresión notablemente elegante de un programa

Oh y es muy rápido, también {[59]]}

const recur = (...args) =>
  ({ type: recur, args })
  
const loop = f =>
  {
    let acc = f ()
    while (acc && acc.type === recur)
      acc = f (...acc.args)
    return acc
  }

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

La mónada de continuación

Este es uno de mis temas favoritos, así que vamos a ver cómo se ve con la mónada de Continuación. También iremos un paso más allá y ocultaremos el detalle de implementación de trampolín dentro de de nuestra función repeat usando una función auxiliar (aux) para que la persona que llama no tenga que preocuparse por rebotar el valor devuelto cada vez

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

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

// Continuation monad; stack-safe implementation
const Cont = f => ({
  _runCont: f,
  chain: g =>
    Cont(k =>
      Bounce(f, x =>
        Bounce(g(x)._runCont, k)))
})

Cont.of = x => Cont(k => k(x))

const runCont = (m,k) =>
  trampoline(Bounce(m._runCont, k))

// repeat now leaks no implementation detail that a trampoline is used
const repeat = n => f => x => {
  const aux = (n,x) =>
    n === 0 ? Cont.of(x) : Cont.of(f(x)).chain(x => aux(n - 1, x))
  return runCont(aux(n,x), x => x)
}

// looks like any other function, still stack-safe
console.log(repeat(1e5) (x => x + 1) (0))

Y combinator

El combinador Y es mi combinador espiritual; esta respuesta estaría incompleta sin darle algún lugar entre las otras técnicas. Sin embargo, la mayoría de las implementaciones del combinador Y no son seguras para la pila y se desbordarán si la función suministrada por el usuario se repite demasiadas veces. Dado que esta respuesta se trata de preservar el comportamiento seguro de la pila, por supuesto implementaremos Y en un manera segura-de nuevo, confiando en nuestro trampolín de confianza.

Y demuestra la capacidad de extender la recursividad infinita síncrona, fácil de usar y segura para apilar sin sobrecargar su función.

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

Practicidad con while bucle

Pero seamos honestos: eso es mucha ceremonia cuando estamos pasando por alto una de las soluciones potenciales más obvias: use un bucle for o while, pero escóndalo detrás de un bucle funcional interfaz

A todos los efectos, esta función repeat funciona de manera idéntica a las proporcionadas anteriormente, excepto que esta es aproximadamente una o dos mil millones de veces más rápida (con excepción de la funciónloop/recur solución). Diablos, podría decirse que es mucho más fácil de leer también.

Concedido, esta función es quizás un ejemplo artificial - no todas las funciones recursivas se pueden convertir a un bucle for o while tan fácilmente, pero en un escenario donde es posible, es probablemente mejor simplemente hazlo así. Guarde los trampolines y las continuaciones para levantar objetos pesados cuando un simple bucle no lo haga.

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 no es una solución al problema de desbordamiento de pila

Bien, entonces funciona, pero solo paradójicamente. Si su conjunto de datos es pequeño, no necesita setTimeout porque no habrá desbordamiento de pila. Si su conjunto de datos es grande y utiliza setTimeout como un mecanismo de recursión seguro, no solo hace que sea imposible devuelva sincrónicamente un valor de su función, será tan lento que ni siquiera querrá usar su función

Algunas personas han encontrado un sitio de preparación de preguntas y respuestas para entrevistas que alienta esta terrible estrategia

Cómo se vería nuestro repeat usando setTimeout - observe que también se define en el estilo de paso de continuación-es decir, debemos llamar a repeat con una devolución de llamada (k) para obtener el valor final

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

No puedo enfatizar lo suficiente lo malo que es esto. Incluso 1e5 toma tanto tiempo correr que dejé de intentar medirlo. No estoy incluyendo esto en los puntos de referencia a continuación porque es demasiado lento incluso para ser considerado un enfoque viable.

Promesas

Las promesas tienen la capacidad de encadenar cálculos y son apilar seguro. Sin embargo, lograr una pila segura repeat usando Promesas significa que tendremos que renunciar a nuestro valor de retorno síncrono, de la misma manera que lo hicimos usando setTimeout. Estoy proporcionando esto como una "solución" porque resuelve el problema, a diferencia desetTimeout, pero de una manera que es muy simple en comparación con el trampolín o la mónada de continuación. Como se puede imaginar, sin embargo, el rendimiento es algo malo, pero ni de lejos tan malo como el ejemplo setTimeout anterior

Vale la pena señalar en esta solución, el detalle de la implementación de la promesa está completamente oculto para el llamante. Una única continuación se proporciona como un 4to argumento y se llama cuando el cálculo es completo.

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

Puntos de referencia

En serio, el bucle while es un lote más rápido, como casi 100 veces más rápido (cuando se compara lo mejor con lo peor, pero sin incluir las respuestas asíncronas: setTimeout y 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

Edad de Piedra JavaScript

Las técnicas anteriores se demuestran utilizando sintaxis ES6 más nuevas, pero podría implementar un trampolín en la versión más temprana posible de JavaScript – solo it requiere while y funciones de primera clase

A continuación, usamos javascript de la edad de piedra para demostrar que la recursión infinita es posible y performante sin necesariamente sacrificar un valor de retorno síncrono– 100,000,000 recursiones en bajo 6 segundos-esta es una diferencia dramática en comparación con setTimeout que solo puede 1,000 recursiones en la misma cantidad de tiempo.

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

Recursión infinita sin bloqueo usando JavaScript de la edad de piedra

Si , por alguna razón, desea una recursión infinita sin bloqueo (asíncrona), podemos confiar en setTimeout para diferir un marco único al inicio del cálculo. Este programa también utiliza javascript de la edad de piedra y calcula 100.000.000 de recursiones en menos de 8 segundos, pero esta vez de una manera no bloqueante.

Esto demuestra que no hay nada especial en tener un requisito de no bloqueo. Un bucle while y de primera clase las funciones siguen siendo el único requisito fundamental para lograr una recursividad segura para la pila sin sacrificar el rendimiento

En un programa moderno, dadas las Promesas, sustituiríamos el setTimeout llamado por una sola Promesa.

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