Hola usuario de nuestro sitio web, hallamos la solución a tu búsqueda, deslízate y la obtendrás aquí.
Solución:
Un ejemplo en JavaScript
A continuación, se muestra un ejemplo de uso de 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 exceededTrampolines
Podemos solucionar esta limitación cambiando la forma en que escribimos repetir, pero solo ligeramente. En lugar de devolver un valor directa o inmediatamente recurrente, devolveremos uno de nuestros dos tipos de trampolines, Bounce o Done. Entonces usaremos nuestro trampoline función 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) // 1000000Currying también ralentiza un poco las cosas, pero podemos remediarlo usando una función auxiliar para la recursividad. Esto también es bueno porque oculta los detalles de implementación del trampolín y no espera que la persona que llama rebote el valor de retorno. Esto funciona 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 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 muy interesados en el Bounce y Done envoltorios también.
Clojure crea una interfaz de trampolín especializada que utiliza un par de funciones, loop y recur – este par en tándem se presta a una expresión notablemente elegante de un programa
Oh, y también es muy rápido
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 msInicialmente, este estilo se sentirá extraño, pero con el tiempo encuentro que es el más consistente al producir programas duraderos. Los comentarios a continuación le ayudarán a acceder a la sintaxis rica en expresiones:
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
)
)
La mónada de continuación
Este es uno de mis temas favoritos, así que veremos cómo se ve con la mónada de continuación. Reutilizando loop y recur, implementamos una pila segura cont que puede secuenciar operaciones usando chain y ejecutar secuencias de operación usando runCont. Para repeat, esto no tiene sentido (y es lento), pero es genial ver la mecánica de cont en el trabajo en este simple ejemplo –
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 msY combinador
El combinador Y es mi combinador de espíritus; 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 proporcionada 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 de una manera segura, nuevamente, confiando en nuestro confiable trampolín.
Y demuestra la capacidad de extender la recursividad infinita sincrónica, fácil de usar, segura para la pila y 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)) // 10000Practicidad con while círculo
Pero seamos honestos: eso es mucha ceremonia cuando pasamos por alto una de las posibles soluciones más obvias: usar un for o while bucle, pero ocúltelo detrás de una interfaz funcional
Para todos los efectos, este repeat La función 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 loop/recur solución). Diablos, podría decirse que también es mucho más fácil de leer.
Por supuesto, esta función es quizás un ejemplo artificial: no todas las funciones recursivas se pueden convertir a una for o while bucle con tanta facilidad, pero en un escenario en el que sea posible, probablemente sea mejor hacerlo así. Guarde los trampolines y las continuaciones para levantar objetos pesados cuando un simple bucle no sea suficiente.
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) // 100000000setTimeout NO es una solución al problema de desbordamiento de pila
OK, entonces lo hace trabajar, pero sólo 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 usa setTimeout como mecanismo de recursividad seguro, no solo hace que sea imposible devolver un valor de su función sincrónicamente, será tan F 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 fomenta esta terrible estrategia
Lo que nuestro repeat se vería como usar setTimeout – observe que también se define en el estilo de paso de continuación, es decir, debemos llamar repeat con una devolución de llamadak) 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 tarda tanto en ejecutarse que dejé de intentar medirlo. No incluyo esto en los puntos de referencia a continuación porque es demasiado lento para siquiera ser considerado un enfoque viable.
Promesas
Las promesas tienen la capacidad de encadenar cálculos y son apilables. Sin embargo, lograr una pila segura repeat usar Promesas significa que tendremos que renunciar a nuestro valor de retorno sincrónico, de la misma manera que lo hicimos usando setTimeout. Proporciono esto como una “solución” porque lo hace resolver el problema, a diferencia de setTimeout, pero de una manera muy simple en comparación con el trampolín o la mónada de continuación. Sin embargo, como puede imaginar, el rendimiento es algo malo, pero no tan malo como el setTimeout ejemplo de arriba
Vale la pena señalar que en esta solución, el detalle de implementación de Promise está completamente oculto para la persona que llama. Se proporciona una única continuación como cuarto argumento y se llama cuando se completa el cálculo.
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
En serio, el while bucle es un lote más rápido, como casi 100 veces más rápido (al comparar lo mejor con lo peor, pero sin incluir 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
JavaScript de la Edad de Piedra
Las técnicas anteriores se demuestran utilizando sintaxis ES6 más nuevas, pero puede implementar un trampolín en la versión más temprana posible de JavaScript; solo requiere while y funciones de primera clase
A continuación, usamos javascript de la edad de piedra para demostrar que la recursividad infinita es posible y funciona sin necesariamente sacrificar un valor de retorno sincrónico – 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: 5999msRecursión infinita sin bloqueo usando JavaScript de la edad de piedra
Si, por alguna razón, desea una recursividad infinita sin bloqueo (asincrónica), podemos confiar en setTimeout aplazar un Un solo cuadro 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 sin bloqueo.
Esto demuestra que no hay nada especial en tener un requisito de no bloqueo. A while Las funciones de bucle y de primera clase siguen siendo el único requisito fundamental para lograr la recursividad segura para la pila sin sacrificar el rendimiento.
En un programa moderno, dadas las Promesas, sustituiríamos el setTimeout Llame para 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: 7762msUn mejor loop/recur patrón
Hay dos cosas que no me gustan de la loop/recur patrón descrito en la respuesta aceptada. Tenga en cuenta que en realidad me gusta la idea detrás del loop/recur patrón. Sin embargo, no me gusta la forma en que se ha implementado. Entonces, veamos primero la forma en que lo habría implementado.
// Recur :: a -> Result a b
const Recur = (...args) => ( recur: true, args );
// Return :: b -> Result a b
const Return = value => ( recur: false, value );
// loop :: (a -> Result a b) -> a -> b
const loop = func => (...args) =>
let result = func(...args);
while (result.recur) result = func(...result.args);
return result.value;
;
// repeat :: (Int, a -> a, a) -> a
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));
console.time("loop/recur/return");
console.log(repeat(1e6, x => x + 1, 0));
console.timeEnd("loop/recur/return");Compare esto con el loop/recur patrón descrito en la respuesta antes mencionada.
// recur :: a -> Recur a
const recur = (...args) => ( recur, args );
// loop :: (a? -> Recur a ∪ b) -> b
const loop = func =>
let result = func();
while (result && result.recur === recur) result = func(...result.args);
return result;
;
// repeat :: (Int, a -> a, a) -> a
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));
console.timeEnd("loop/recur");Si nota, la firma mecanografiada del segundo loop La función utiliza parámetros predeterminados (es decir a?) y uniones sin etiquetar (es decir Recur a ∪ b). Ambas características están en desacuerdo con el paradigma de programación funcional.
Problema con los parámetros predeterminados
los loop/recur patrón en la respuesta antes mencionada utiliza parámetros predeterminados para proporcionar los argumentos iniciales de la función. Creo que esto es un abuso de los parámetros predeterminados. Puede proporcionar argumentos iniciales con la misma facilidad usando mi versión de loop.
// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((n, x) => n === 0 ? Return(x) : Recur(n - 1, f(x)))(n, x);
// or more readable
const repeat = (n, f, x) =>
const repeatF = loop((n, x) => n === 0 ? Return(x) : Recur(n - 1, f(x)));
return repeatF(n, x);
;
Además, permite la conversión eta cuando se pasan todos los argumentos.
// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)))(n, f, x);
// can be η-converted to
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));
Usando la versión de loop con los parámetros predeterminados no permite la conversión eta. Además, te obliga a cambiar el nombre de los parámetros porque no puedes escribir (n = n, x = x) => ... en JavaScript.
Problema con las uniones sin etiquetar
Las uniones no etiquetadas son malas porque borran información importante, es decir, información de dónde provienen los datos. Por ejemplo, porque mi Result el tipo está etiquetado puedo distinguir Return(Recur(0)) de Recur(0).
Por otro lado, debido a que la variante del lado derecho de Recur a ∪ b no está etiquetado, si b está especializado en Recur a, es decir, si el tipo está especializado en Recur a ∪ Recur a, entonces es imposible determinar si el Recur a vino del lado izquierdo o del lado derecho.
Una crítica podría ser que b nunca se especializará en Recur a, y por lo tanto no importa que b no está etiquetado. He aquí un simple contraejemplo de esa crítica.
// recur :: a -> Recur a
const recur = (...args) => ( recur, args );
// loop :: (a? -> Recur a ∪ b) -> b
const loop = func =>
let result = func();
while (result && result.recur === recur) result = func(...result.args);
return result;
;
// repeat :: (Int, a -> a, a) -> a
const repeat = (n, f, x) => loop((m = n, r = x) => m === 0 ? r : recur(m - 1, f(r)));
// infinite loop
console.log(repeat(1, x => recur(1, x), "wow, such hack, much loop"));
// unreachable code
console.log("repeat wasn't hacked");Compare esto con mi versión de repeat que es a prueba de balas.
// Recur :: a -> Result a b
const Recur = (...args) => ( recur: true, args );
// Return :: b -> Result a b
const Return = value => ( recur: false, value );
// loop :: (a -> Result a b) -> a -> b
const loop = func => (...args) =>
let result = func(...args);
while (result.recur) result = func(...result.args);
return result.value;
;
// repeat :: (Int, a -> a, a) -> a
const repeat = loop((n, f, x) => n === 0 ? Return(x) : Recur(n - 1, f, f(x)));
// finite loop
console.log(repeat(1, x => Recur(1, x), "wow, such hack, much loop"));
// reachable code
console.log("repeat wasn't hacked");Por lo tanto, las uniones sin etiquetar no son seguras. Sin embargo, incluso si tuviéramos cuidado de evitar las trampas de las uniones sin etiquetar, seguiría prefiriendo las uniones etiquetadas porque las etiquetas brindan información útil al leer y depurar el programa. En mi humilde opinión, las etiquetas hacen que el programa sea más comprensible y más fácil de depurar.
Conclusión
Para citar el Zen de Python.
Explícito es mejor que implícito.
Los parámetros predeterminados y las uniones sin etiquetar son incorrectos porque están implícitos y pueden generar ambigüedades.
los Trampoline monada
Ahora, me gustaría cambiar de marcha y hablar de mónadas. La respuesta aceptada demuestra una mónada de continuación segura para la pila. Sin embargo, si solo necesita crear una función recursiva segura de pila monádica, no necesita toda la potencia de la mónada de continuación. Puedes usar el Trampoline monada.
los Trampoline mónada es un primo más poderoso de la Loop mónada, que es solo la loop función convertida en una mónada. Entonces, comencemos por comprender Loop monada. Entonces veremos el principal problema de la Loop mónada y cómo el Trampoline mónada se puede utilizar para solucionar ese problema.
// Recur :: a -> Result a b
const Recur = (...args) => ( recur: true, args );
// Return :: b -> Result a b
const Return = value => ( recur: false, value );
// Loop :: (a -> Result a b) -> a -> Loop b
const Loop = func => (...args) => ( func, args );
// runLoop :: Loop a -> a
const runLoop = ( func, args ) =>
let result = func(...args);
while (result.recur) result = func(...result.args);
return result.value;
;
// pure :: a -> Loop a
const pure = Loop(Return);
// bind :: (Loop a, a -> Loop b) -> Loop b
const bind = (loop, next) => Loop(( first, loop: func, args ) =>
const result = func(...args);
if (result.recur) return Recur( first, loop: func, args: result.args );
if (first) return Recur( first: false, loop: next(result.value) );
return result;
)( first: true, loop );
// ack :: (Int, Int) -> Loop Int
const ack = (m, n) =>
if (m === 0) return pure(n + 1);
if (n === 0) return ack(m - 1, 1);
return bind(ack(m, n - 1), n => ack(m - 1, n));
;
console.log(runLoop(ack(3, 4)));Tenga en cuenta que loop se ha dividido en un Loop y un runLoop función. La estructura de datos devuelta por Loop es una mónada, y el pure y bind Las funciones implementan su interfaz monádica. Usamos el pure y bind funciones para escribir una implementación sencilla de la función de Ackermann.
Desafortunadamente, el ack La función no es segura para la pila porque se llama a sí misma de forma recursiva hasta que alcanza un pure valor. En cambio, nos gustaría ack para devolver un Recur como estructura de datos para sus casos inductivos. Sin embargo, Recur los valores son de tipo Result en lugar de Loop. Este problema se resuelve con Trampoline monada.
// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ( bounce: true, func, args );
// Return :: a -> Trampoline a
const Return = value => ( bounce: false, value );
// trampoline :: Trampoline a -> a
const trampoline = result =>
while (result.bounce) result = result.func(...result.args);
return result.value;
;
// pure :: a -> Trampoline a
const pure = Return;
// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
Bounce(args => bind(first.func(...args), next))(first.args) :
next(first.value);
// ack :: (Int, Int) -> Trampoline Int
const ack = Bounce((m, n) =>
if (m === 0) return pure(n + 1);
if (n === 0) return ack(m - 1, 1);
return bind(ack(m, n - 1), n => ack(m - 1, n));
);
console.log(trampoline(ack(3, 4)));los Trampoline el tipo de datos es una combinación de Loop y Result. los Loop y Recur Los constructores de datos se han combinado en un solo Bounce constructor de datos. los runLoop La función ha sido simplificada y renombrada a trampoline. los pure y bind Las funciones también se han simplificado. De hecho, pure es solo Return. Finalmente, aplicamos Bounce a la implementación original de la ack función.
Otra ventaja de Trampoline es que se puede utilizar para definir funciones recursivas recursivas seguras para la pila. Por ejemplo, aquí hay una implementación de las funciones de secuencia femenina y masculina de Hofstadter.
// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ( bounce: true, func, args );
// Return :: a -> Trampoline a
const Return = value => ( bounce: false, value );
// trampoline :: Trampoline a -> a
const trampoline = result =>
while (result.bounce) result = result.func(...result.args);
return result.value;
;
// pure :: a -> Trampoline a
const pure = Return;
// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
Bounce(args => bind(first.func(...args), next))(first.args) :
next(first.value);
// female :: Int -> Trampoline Int
const female = Bounce(n => n === 0 ? pure(1) :
bind(female(n - 1), f =>
bind(male(f), m =>
pure(n - m))));
// male :: Int -> Trampoline Int
const male = Bounce(n => n === 0 ? pure(0) :
bind(male(n - 1), m =>
bind(female(m), f =>
pure(n - f))));
console.log(Array.from( length: 21 , (_, n) => trampoline(female(n))).join(" "));
console.log(Array.from( length: 21 , (_, n) => trampoline(male(n))).join(" "));El principal problema de escribir código monádico es el infierno de devolución de llamada. Sin embargo, esto se puede solucionar utilizando generadores.
// Bounce :: (a -> Trampoline b) -> a -> Trampoline b
const Bounce = func => (...args) => ( bounce: true, func, args );
// Return :: a -> Trampoline a
const Return = value => ( bounce: false, value );
// trampoline :: Trampoline a -> a
const trampoline = result =>
while (result.bounce) result = result.func(...result.args);
return result.value;
;
// pure :: a -> Trampoline a
const pure = Return;
// bind :: (Trampoline a, a -> Trampoline b) -> Trampoline b
const bind = (first, next) => first.bounce ?
Bounce(args => bind(first.func(...args), next))(first.args) :
next(first.value);
// bounce :: (a -> Generator (Trampoline b)) -> a -> Trampoline b
const bounce = func => Bounce((...args) =>
const gen = func(...args);
const next = data =>
const value, done = gen.next(data);
return done ? value : bind(value, next);
;
return next(undefined);
);
// female :: Int -> Trampoline Int
const female = bounce(function* (n)
return pure(n ? n - (yield male(yield female(n - 1))) : 1);
);
// male :: Int -> Trampoline Int
const male = bounce(function* (n)
return pure(n ? n - (yield female(yield male(n - 1))) : 0);
);
console.log(Array.from( length: 21 , (_, n) => trampoline(female(n))).join(" "));
console.log(Array.from( length: 21 , (_, n) => trampoline(male(n))).join(" "));Finalmente, las funciones recursivas entre sí también demuestran la ventaja de tener un trampoline función. Nos permite llamar a una función devolviendo un Trampoline valor sin ejecutarlo realmente. Esto nos permite construir más Trampoline valores y luego ejecute todo el cálculo cuando sea necesario.
Conclusión
Si desea escribir funciones seguras para la pila de forma indirecta o recursiva, o funciones seguras para la pila monádica, utilice la Trampoline monada. Si desea escribir funciones seguras de pila recursivas directamente no monádicas, utilice la loop/recur/return patrón.
La programación en el sentido del paradigma funcional significa que nos guiamos por tipos para expresar nuestros algoritmos.
Para transformar una función recursiva de cola en una versión segura para la pila, tenemos que considerar dos casos:
- caso base
- caso recursivo
Tenemos que tomar una decisión y esto va bien con los sindicatos etiquetados. Sin embargo, Javascript no tiene ese tipo de datos, por lo que tenemos que crear uno o recurrir a Object codificaciones.
Objeto codificado
// 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();Función codificada
Alternativamente, podemos crear una unión etiquetada real con una función de codificación. Ahora nuestro estilo está mucho más cerca de los lenguajes funcionales maduros:
// 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));