javascript - uso - programacion funcional vs orientada a objetos

¿Cómo reemplazo los bucles while con una alternativa de programación funcional sin optimización de la cola de llamadas? (4)

Estoy experimentando con un estilo más funcional en mi JavaScript; Por lo tanto, he reemplazado los bucles con funciones de utilidad como mapear y reducir. Sin embargo, no he encontrado un reemplazo funcional para los bucles while ya que la optimización de las llamadas de cola generalmente no está disponible para JavaScript. (Según tengo entendido, ES6 evita que las llamadas de cola desborden la pila, pero no optimiza su rendimiento).

A continuación explico lo que he intentado, pero el TLDR es: si no tengo la optimización de la cola, ¿cuál es la forma funcional de implementar los bucles while?

Lo que he intentado:

Crear una función de utilidad "while":

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

Como la optimización de la cola no está disponible, podría reescribir esto como:

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

Sin embargo, en este punto parece que he hecho mi código más complicado / confuso para cualquier otra persona que lo use, ya que tengo que cargar con una función de utilidad personalizada. La única ventaja práctica que veo es que me obliga a hacer puro el ciclo; pero parece que sería más sencillo usar un ciclo while regular y asegurarme de mantener todo puro.

También traté de encontrar una manera de crear una función generadora que imite los efectos de la recursividad / bucle y luego iterar sobre ella usando una función de utilidad como buscar o reducir. Sin embargo, todavía no he descubierto una forma legible de hacerlo.

Finalmente, reemplazar bucles por funciones de utilidad hace que sea más evidente lo que estoy tratando de lograr (por ejemplo, hacer algo con cada elemento, verificar si cada elemento pasa una prueba, etc.). Sin embargo, me parece que un ciclo while ya expresa lo que estoy tratando de lograr (por ejemplo, iterar hasta encontrar un número primo, iterar hasta que la respuesta esté lo suficientemente optimizada, etc.).

Entonces, después de todo esto, mi pregunta general es: si necesito un bucle while, estoy programando en un estilo funcional y no tengo acceso a la optimización de llamadas de cola, entonces cuál es la mejor estrategia.

He estado pensando mucho en esta pregunta. Recientemente me encontré con la necesidad de un bucle while funcional.

Me parece que lo único que esta pregunta realmente quiere es una forma de incluir un ciclo while. Hay una manera de hacerlo usando un cierre.

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

Alternativamente, si lo que desea es algo que encadena una matriz, puede usar el método de reducción.

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

Nada de esto convierte nuestro bucle while en su núcleo en una función. Pero sí nos permite el uso de un bucle en línea. Y solo quería compartir esto con cualquiera que pueda ayudar.

La programación en el sentido del paradigma funcional significa que somos guiados 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 debemos crear uno o recurrir a las codificaciones de Object .

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 real etiquetada con una codificación de funció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));

Vea también unfold cuáles (de Ramda docs)

Crea una lista a partir de un valor semilla. Acepta una función iteradora, que devuelve falso para detener la iteración o una matriz de longitud 2 que contiene el valor para agregar a la lista resultante y la semilla que se utilizará en la próxima llamada a la función iteradora.

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>

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 repetir, pero solo ligeramente. En lugar de devolver un valor recurrente directo o inmediato, devolveremos uno de nuestros dos tipos de trampolín, Bounce o Done . Luego usaremos nuestra función de 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 console.log(result) // 1000000

Currying ralentiza un poco las cosas también, pero podemos remediar eso usando una función auxiliar para la recursión. 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 corre aproximadamente el doble de rápido que la repeat anterior

// 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-style loop / recur

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

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

Ah, 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 ms

Inicialmente, este estilo se sentirá extraño, pero con el tiempo creo que es el más consistente al producir programas duraderos. Los comentarios a continuación ayudan a facilitar 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 el loop y la recur , implementamos un control seguro para la pila que puede secuenciar operaciones usando chain y ejecutar secuencias de operaciones usando runCont . Para repeat , esto no tiene sentido (y es lento), pero es genial ver la mecánica de cont en funcionamiento 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 ms

Combinador Y

El combinador Y es mi combinador espiritual; esta respuesta sería incompleta sin darle un lugar entre las otras técnicas. Sin embargo, la mayoría de las implementaciones del combinador Y no son aptas 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 trampolín de confianza.

Y demuestra la capacidad de extender la recursión infinita síncrona, fácil de usar, segura para la pila, sin saturar 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 el ciclo while

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

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

Por supuesto, esta función es quizás un ejemplo artificial: no todas las funciones recursivas se pueden convertir en un bucle for o while tan fácilmente, pero en un escenario en el que es posible, probablemente sea mejor hacerlo de esta manera. Guarde los trampolines y las continuaciones para levantar objetos pesados cuando un simple bucle no funcione.

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

OK, 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 usa setTimeout como un mecanismo de recursión seguro, no solo hace que sea imposible devolver un valor de su función de forma síncrona, será tan lento que ni siquiera querrá usar su función

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

Cómo se vería nuestra 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 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 ser considerado un enfoque viable.

Promesas

Las promesas tienen la capacidad de encadenar cálculos y son apilables. Sin embargo, lograr una repeat segura para la pila usando Promises 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 de setTimeout , pero de una manera que es 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 ejemplo anterior de setTimeout

Vale la pena señalar en esta solución, los detalles de implementación de Promise están completamente ocultos para la persona que llama. Se proporciona una única continuación como un 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))

Puntos de referencia

En serio, el ciclo while es mucho más rápido, como casi 100 veces más rápido (cuando se compara 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 nuevas sintaxis de ES6, pero podría implementar un trampolín en la versión más temprana posible de JavaScript: solo requiere funciones while y de primera clase

A continuación, utilizamos JavaScript de la edad de piedra para demostrar que la recursión infinita es posible y eficaz sin sacrificar necesariamente un valor de retorno síncrono: 100,000,000 recursiones en menos de 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.

Recurrencia 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 solo cuadro al comienzo del cálculo. Este programa también usa JavaScript de la edad de piedra y calcula 100,000,000 de recursiones en menos de 8 segundos, pero esta vez de manera no bloqueante.

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

En un programa moderno, dado Promesas, sustituiríamos la llamada setTimeout por una sola Promesa.