ejemplos - funciones lambda javascript
javascript: ¿función anónima recursiva? (18)
Digamos que tengo una función recursiva básica:
function recur(data) {
data = data+1;
var nothing = function() {
recur(data);
}
nothing();
}
¿Cómo podría hacer esto si tengo una función anónima como ...
(function(data){
data = data+1;
var nothing = function() {
//Something here that calls the function?
}
nothing();
})();
Me gustaría una forma de llamar a la función que llamó a esta función ... He visto guiones en algún lugar (no recuerdo dónde) que pueden indicar el nombre de una función llamada, pero no recuerdo ninguno de esa información ahora mismo.
¿Por qué no pasar la función a la función en sí?
var functionCaller = function(thisCaller, data) {
data = data + 1;
var nothing = function() {
thisCaller(thisCaller, data);
};
nothing();
};
functionCaller(functionCaller, data);
Como escribió bobince, simplemente nombra tu función.
¡Pero, supongo que también quieres pasar un valor inicial y detener tu función eventualmente!
var initialValue = ...
(function recurse(data){
data++;
var nothing = function() {
recurse(data);
}
if ( ... stop condition ... )
{ ... display result, etc. ... }
else
nothing();
}(initialValue));
ejemplo jsFiddle de trabajo (usa datos + = datos por diversión)
Con ES2015 podemos jugar un poco con la sintaxis y abusar de los parámetros predeterminados y los thunk. Las últimas son solo funciones sin ningún argumento:
const applyT = thunk => thunk();
const fib = n => applyT(
(f = (x, y, n) => n === 0 ? x : f(y, x + y, n - 1)) => f(0, 1, n)
);
console.log(fib(10)); // 55
// Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
Tenga en cuenta que f es un parámetro con la función anónima (x, y, n) => n === 0 ? x : f(y, x + y, n - 1) (x, y, n) => n === 0 ? x : f(y, x + y, n - 1) como su valor predeterminado. Cuando applyT se invoca, esta invocación debe tener lugar sin argumentos, de modo que se utiliza el valor predeterminado. El valor predeterminado es una función y, por lo tanto, f es una función nombrada, que puede llamarse recursivamente.
Cuando declaras una función anónima como esta:
(function () {
// Pass
}());
Se considera una expresión de función y tiene un nombre opcional (que puede usar para llamarlo desde sí mismo. Pero como es una expresión de función (y no una declaración) permanece anónima (pero tiene un nombre al que puede llamar). esta función puede llamarse a sí misma:
(function foo () {
foo();
}());
foo //-> undefined
En ciertas situaciones, debe confiar en funciones anónimas. Given es una función de map recursiva:
const map = f => acc => ([head, ...tail]) => head === undefined
? acc
: map (f) ([...acc, f(head)]) (tail);
const sqr = x => x * x;
const xs = [1,2,3,4,5];
console.log(map(sqr) ([0]) (xs)); // [0] modifies the structure of the array
Tenga en cuenta que el map no debe modificar la estructura de la matriz. Entonces, el acumulador acc no necesita estar expuesto. Podemos ajustar el map en otra función, por ejemplo:
const map = f => xs => {
let next = acc => ([head, ...tail]) => head === undefined
? acc
: map ([...acc, f(head)]) (tail);
return next([])(xs);
}
Pero esta solución es bastante detallada. Usemos el subcombinador U subestimado:
const U = f => f(f);
const map = f => U(h => acc => ([head, ...tail]) => head === undefined
? acc
: h(h)([...acc, f(head)])(tail))([]);
const sqr = x => x * x;
const xs = [1,2,3,4,5];
console.log(map(sqr) (xs));
Conciso, ¿no? U es muy simple pero tiene la desventaja de que la llamada recursiva se confunde un poco: sum(...) convierte en h(h)(...) - eso es todo.
Es posible que esto no funcione en todas partes, pero puede usar arguments.callee para referirse a la función actual.
Entonces, factorial podría hacerse así:
var fac = function(x) {
if (x == 1) return x;
else return x * arguments.callee(x-1);
}
Esta es una repetición de la respuesta de jforjs con diferentes nombres y una entrada ligeramente modificada.
// function takes two argument: first is recursive function and second is input
var sum = (function(capturedRecurser,n){
return capturedRecurser(capturedRecurser, n);
})(function(thisFunction,n){
if(n>1){
return n + thisFunction(thisFunction,n-1)
}else{
return n;
}
},5);
console.log(sum) //output : 15
No hubo necesidad de desenrollar la primera recursión. La función que se recibe a sí misma como referencia se remonta al primordial exudado de OOP.
Esta es una versión de la respuesta de @ zem con funciones de flecha.
Puedes usar el combinador U o Y El combinador Y es el más simple de usar.
U combinator, con esto tienes que seguir pasando la función: const U = f => f(f) U(selfFn => arg => selfFn(selfFn)(''to infinity and beyond''))
Combinador Y , con esto no tiene que seguir pasando la función: const Y = gen => U(f => gen((...args) => f(f)(...args))) Y(selfFn => arg => selfFn(''to infinity and beyond''))
La gente habló sobre el combinador Y en comentarios, pero nadie lo escribió como respuesta.
El combinador Y se puede definir en javascript de la siguiente manera: (gracias a steamer25 para el enlace)
var Y = function (gen) {
return (function(f) {
return f(f);
}(function(f) {
return gen(function() {
return f(f).apply(null, arguments);
});
}));
}
Y cuando quiera pasar su función anónima:
(Y(function(recur) {
return function(data) {
data = data+1;
var nothing = function() {
recur(data);
}
nothing();
}
})());
Lo más importante que debe tener en cuenta sobre esta solución es que no debe usarla.
Necesitaba (o más bien, quería) una función anónima de una sola línea para recorrer un objeto que formaba una cadena, y lo manejaba así:
var cmTitle = ''Root'' + (function cmCatRecurse(cmCat){return (cmCat == root) ? '''' : cmCatRecurse(cmCat.parent) + '' : '' + cmCat.getDisplayName();})(cmCurrentCat);
que produce una cadena como ''Root: foo: bar: baz: ...''
No estoy seguro de si la respuesta aún es necesaria, pero esto también se puede hacer utilizando delegados creados utilizando function.bind:
var x = ((function () {
return this.bind(this, arguments[0])();
}).bind(function (n) {
if (n != 1) {
return n * this.bind(this, (n - 1))();
}
else {
return 1;
}
}))(5);
console.log(x);
Esto no implica funciones nombradas o arguments.callee.
No haría esto como una función en línea. Está empujando contra los límites del buen gusto y realmente no te da nada.
Si realmente debes hacerlo, hay arguments.callee como en la respuesta de Fabrizio. Sin embargo, esto generalmente se considera desaconsejable y no se permite en el "modo estricto" de ECMAScript Fifth Edition. Aunque ECMA 3 y non-strict-mode no desaparecen, trabajar en modo estricto promete más optimizaciones de idioma posibles.
También se puede usar una función en línea nombrada:
(function foo(data){
data++;
var nothing = function() {
foo(data);
}
nothing();
})();
Sin embargo, las expresiones de función en línea nombradas también se evitan, ya que JScript de IE les hace algunas cosas malas. En el ejemplo anterior, foo contamina incorrectamente el ámbito primario en IE, y el padre foo es una instancia separada del foo visto dentro de foo .
¿Cuál es el propósito de poner esto en una función anónima en línea? Si solo quiere evitar contaminar el alcance principal, puede, por supuesto, ocultar su primer ejemplo dentro de otra función de auto-llamada-anónima (espacio de nombres). ¿Realmente necesita crear una copia nueva de nothing cada vez que se repite? Es posible que esté mejor con un espacio de nombres que contenga dos funciones simples recíprocas recíprocas.
Otra respuesta que no involucra función o argumentos nombrados.callee
var sum = (function(foo,n){
return n + foo(foo,n-1);
})(function(foo,n){
if(n>1){
return n + foo(foo,n-1)
}else{
return n;
}
},5); //function takes two argument one is function and another is 5
console.log(sum) //output : 15
Podrías hacer algo como:
(foo = function() { foo(); })()
o en tu caso:
(recur = function(data){
data = data+1;
var nothing = function() {
if (data > 100) return; // put recursion limit
recur(data);
}
nothing();
})(/* put data init value here */ 0);
Puede darle un nombre a la función, incluso cuando está creando la función como un valor y no como una declaración de "declaración de función". En otras palabras:
(function foo() { foo(); })();
es una función recursiva de soplar pila. Ahora, dicho esto, es probable que no desee hacer esto en general porque existen algunos problemas extraños con varias implementaciones de Javascript. ( Nota : es un comentario bastante antiguo; algunos / muchos / todos los problemas descritos en la publicación de Kangax en el blog pueden corregirse en navegadores más modernos).
Cuando dices un nombre como ese, el nombre no es visible fuera de la función (bueno, se supone que no es así, esa es una de las rarezas). Es como "letrec" en Lisp.
En cuanto a arguments.callee , eso no se permite en el modo "estricto" y, en general, se considera algo malo, porque dificulta algunas optimizaciones. También es mucho más lento de lo que cabría esperar.
editar - Si desea tener el efecto de una función "anónima" que puede llamarse a sí misma, puede hacer algo como esto (suponiendo que está pasando la función como una devolución de llamada o algo así):
asyncThingWithCallback(params, (function() {
function recursive() {
if (timeToStop())
return whatever();
recursive(moreWork);
}
return recursive;
})());
Lo que hace es definir una función con una declaración de declaración de función agradable, segura y no rota en IE, creando una función local cuyo nombre no contaminará el espacio de nombres global. La función de envoltura (verdaderamente anónima) simplemente devuelve esa función local.
Puede ser más simple usar un "objeto anónimo" en su lugar:
({
do: function() {
console.log("don''t run this ...");
this.do();
}
}).do();
Su espacio global está completamente libre de contaminación. Es bastante sencillo. Y puede aprovechar fácilmente el estado no global del objeto.
U combinador
El combinador U toma una función y la aplica a sí misma. Entonces, la función que le dé debería tener al menos un parámetro que se unirá a la función (ella misma)
En el ejemplo siguiente, no tenemos una condición de salida, por lo que solo realizaremos un ciclo indefinidamente hasta que ocurra un desbordamiento de la pila
const U = f => f (f)
U (f => (console.log ('' imminent!''), U (f)))
Podemos detener la recursión infinita usando una variedad de técnicas. Aquí, escribiré nuestra función anónima para devolver otra función anónima que está esperando una entrada; en este caso, algún número. Cuando se suministra un número, si es mayor que 0, continuaremos recurriendo; de lo contrario, devolveremos 0.
const log = x => (console.log (x), x)
const U = f => f (f)
// when our function is applied to itself, we get the inner function back
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
// returns: (x => x > 0 ? U (f) (log (x - 1)) : 0)
// where f is a reference to our outer function
// watch when we apply an argument to this function, eg 5
U (f => x => x > 0 ? U (f) (log (x - 1)) : 0) (5)
// 4 3 2 1 0
Lo que no es inmediatamente evidente aquí es que nuestra función, cuando se aplica por primera vez usando el combinador U , devuelve una función esperando la primera entrada. Si le dimos un nombre a esto, podemos construir efectivamente funciones recursivas usando lambdas (funciones anónimas)
const log = x => (console.log (x), x)
const U = f => f (f)
const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
countDown (5)
// 4 3 2 1 0
countDown (3)
// 2 1 0
Solo que esto no es recursividad directa , una función que se llama a sí misma usando su propio nombre. Nuestra definición de countDown no se refiere a sí misma dentro de su cuerpo y aún es posible la recursión
// direct recursion references itself by name
const loop = (params) => {
if (condition)
return someValue
else
// loop references itself to recur...
return loop (adjustedParams)
}
// U combinator does not need a named reference
// no reference to `countDown` inside countDown''s definition
const countDown = U (f => x => x > 0 ? U (f) (log (x - 1)) : 0)
Cómo eliminar la autorreferencia de una función existente con U combinator
Aquí le mostraré cómo tomar una función recursiva que utiliza una referencia a sí mismo y cambiarla a una función que utiliza el combinador U en lugar de la referencia propia.
const factorial = x =>
x === 0 ? 1 : x * factorial (x - 1)
console.log (factorial (5)) // 120
Ahora usando el combinador U para reemplazar la referencia interna a factorial
const U = f => f (f)
const factorial = U (f => x =>
x === 0 ? 1 : x * U (f) (x - 1))
console.log (factorial (5)) // 120
El patrón básico de reemplazo es esto. Tome nota mental, estaremos usando una estrategia similar en la siguiente sección
// self reference recursion
const foo = x => ... foo (nextX) ...
// remove self reference with U combinator
const foo = U (f => x => ... U (f) (nextX) ...)
Combinador Y
relacionados: los combinadores U e Y explicados usando una analogía espejo
En la sección anterior vimos cómo transformar la recursión de autorreferencia en una función recursiva que no se basa en una función nombrada que utiliza el combinador U. También hay un poco de molestia al tener que recordar que siempre se pasa la función a sí mismo como primer argumento. Bueno, el Y-combinator se basa en el U-combinator y elimina esa parte tediosa. Esto es bueno porque eliminar / reducir la complejidad es la razón principal por la que hacemos funciones
Primero, obtengamos nuestro propio Y-combinator
// standard definition
const Y = f => f (Y (f))
// prevent immediate infinite recursion in applicative order language (JS)
const Y = f => f (x => Y (f) (x))
// remove reference to self using U combinator
const Y = U (h => f => f (x => U (h) (f) (x)))
Ahora veremos cómo se compara su uso con el U-combinator. Aviso, para repetir, en lugar de U (f) podemos simplemente llamar a f ()
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
Y (f => (console.log ('' imminent!''), f ()))
Ahora demostraré el programa countDown usando Y - verá que los programas son casi idénticos pero el combinador Y mantiene las cosas un poco más limpias
const log = x => (console.log (x), x)
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const countDown = Y (f => x => x > 0 ? f (log (x - 1)) : 0)
countDown (5)
// 4 3 2 1 0
countDown (3)
// 2 1 0
Y ahora veremos factorial también
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const factorial = Y (f => x =>
x === 0 ? 1 : x * f (x - 1))
console.log (factorial (5)) // 120
Combinador U e Y con más de 1 parámetro
En los ejemplos anteriores, vimos cómo podemos recorrer y pasar un argumento para hacer un seguimiento del "estado" de nuestro cálculo. Pero, ¿qué pasa si necesitamos hacer un seguimiento del estado adicional?
Podríamos usar datos compuestos como una matriz o algo ...
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const fibonacci = Y (f => ([a, b, x]) =>
x === 0 ? a : f ([b, a + b, x - 1]))
// starting with 0 and 1, generate the 7th number in the sequence
console.log (fibonacci ([0, 1, 7]))
// 0 1 1 2 3 5 8 13
Pero esto es malo porque está exponiendo el estado interno (contadores b ). Sería bueno si pudiéramos simplemente llamar a fibonacci (7) para obtener la respuesta que queremos.
Usando lo que sabemos sobre las funciones curried (secuencias de funciones unarias (1-parámetro)), podemos lograr nuestro objetivo fácilmente sin tener que modificar nuestra definición de Y ni confiar en los datos compuestos o en las características avanzadas del lenguaje.
Mire la definición de fibonacci cerca abajo. Estamos aplicando inmediatamente 0 y 1 que están vinculados a b respectivamente. Ahora, fibonacci simplemente está esperando que se suministre el último argumento que estará vinculado a x . Cuando recursemos, debemos llamar a f (a) (b) (x) (no f (a,b,x) ) porque nuestra función está en forma de curry.
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const fibonacci = Y (f => a => b => x =>
x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
console.log (fibonacci (7))
// 0 1 1 2 3 5 8 13
Este tipo de patrón puede ser útil para definir todo tipo de funciones. A continuación veremos dos funciones más definidas usando el combinador Y ( range y reduce ) y una derivada de reduce , map .
const U = f => f (f)
const Y = U (h => f => f (x => U (h) (f) (x)))
const range = Y (f => acc => min => max =>
min > max ? acc : f ([...acc, min]) (min + 1) (max)) ([])
const reduce = Y (f => g => y => ([x,...xs]) =>
x === undefined ? y : f (g) (g (y) (x)) (xs))
const map = f =>
reduce (ys => x => [...ys, f (x)]) ([])
const add = x => y => x + y
const sq = x => x * x
console.log (range (-2) (2))
// [ -2, -1, 0, 1, 2 ]
console.log (reduce (add) (0) ([1,2,3,4]))
// 10
console.log (map (sq) ([1,2,3,4]))
// [ 1, 4, 9, 16 ]
TODO ES ANONIMO OMG
Debido a que estamos trabajando con funciones puras aquí, podemos sustituir cualquier función nombrada por su definición. Mira lo que sucede cuando tomamos fibonacci y reemplazamos las funciones nombradas con sus expresiones
/* const U = f => f (f)
*
* const Y = U (h => f => f (x => U (h) (f) (x)))
*
* const fibonacci = Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
*
*/
/*
* given fibonacci (7)
*
* replace fibonacci with its definition
* Y (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
*
* replace Y with its definition
* U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
//
* replace U with its definition
* (f => f (f)) U (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
*/
let result =
(f => f (f)) (h => f => f (x => U (h) (f) (x))) (f => a => b => x => x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1) (7)
console.log (result) // 13
Y ahí lo tienen: fibonacci (7) calculado recursivamente usando nada más que funciones anónimas
(function(data){
var recursive = arguments.callee;
data = data+1;
var nothing = function() {
recursive(data)
}
nothing();
})();