javascript - programacion - paradigmas funcionales

¿Función de orden superior de las funciones recursivas?

Question

¿Hay alguna forma de "envolver" una función recursiva a través de una función de orden superior, de modo que la llamada recursiva también esté envuelta? (por ejemplo, para registrar los argumentos de la función en cada llamada).

Por ejemplo, supongamos que tenemos una función, sum() , que devuelve la suma de una lista de números agregando la cabeza a la suma de la cola:

function sum(a) {
if (a.length === 0) {
return 0;
} else {
return a[0] + sum(a.slice(1));
}
}

¿Hay alguna forma de escribir una función de orden superior, logging() , que tome la función sum() como entrada, y devuelva una función que genere los argumentos para sum() en cada llamada recursiva?

Lo siguiente no funciona:

function logging(fn) {
return function(a) {
console.log(a);
return fn(a);
}
}
sum2 = logging(sum);
sum2([1, 2, 3]);

Salida real:

[1, 2, 3]
-> 6

Rendimiento esperado:

[1, 2, 3]
[2, 3]
[3]
[]
-> 6

¿Es esto posible incluso si se reescribe sum() para que se pueda utilizar con la "recursión" de estilo Combinator Y?

function sum_core(g) {
return function (a) {
if (a.length === 0) {
return 0;
} else {
return a[0] + g(a.slice(1));
}
};
}
sum = Y(sum_core);
sum([1, 2, 3]);
// -> 6

Answer 1

Asunto del alcance. Trate de hacer lo siguiente:

function logging(fn) {
var _fn = fn; // local cached copy
return function(a) {
console.log(a);
return _fn(a);
}
}

Answer 2

No es posible en JavaScript sin modificar la función. Si no quieres que el trabajo manual, tu mejor apuesta es algo así:

function logged(func){
return eval("("+func.toString().replace(/function(.*){(.*)/g,"function$1{console.log(arguments);$2")+")");
};

Entonces puedes usarlo como:

function sum(a) {
if (a.length === 0) {
return 0;
} else {
return a[0] + sum(a.slice(1));
}
}
console.log(logged(sum)([1,2,3,4]));

Qué salidas:

{ ''0'': [ 1, 2, 3, 4 ] }
{ ''0'': [ 2, 3, 4 ] }
{ ''0'': [ 3, 4 ] }
{ ''0'': [ 4 ] }
{ ''0'': [] }
10

logged sí mismo es muy lento porque recompila la función (con eval ), pero la función resultante es tan rápida como si la hubiera definido manualmente. Por lo tanto, use el logged solo una vez por función y está bien.

Answer 3

Sé que esto es una especie de no respuesta pero lo que quiere es mucho más fácil de hacer si usa objetos y métodos distribuidos dinámicamente. Esencialmente, almacenamos "rec" en una celda mutable en lugar de tener que pasarlo.

Sería similar a sum = logging(sum) (en lugar de sum2 = ) pero es más idiomático y no codifica el nombre de la referencia mutable que enviamos.

var obj = {
sum : function(a){
if (a.length === 0) {
return 0;
} else {
return a[0] + this.sum(a.slice(1)); // <-- dispatch on `this`
}
}
}
function add_logging(obj, funcname){
var oldf = obj[funcname];
obj[funcname] = function(/**/){
console.log(arguments);
return oldf.apply(this, arguments);
}
}
add_logging(obj, ''sum'');

Answer 4

Si insiste en usar funciones regulares sin usar "esto", la única manera que se me ocurre es aplicar el combinador de registro antes de atar el nudo con el combinador de recursión (Y). Básicamente, necesitamos usar el envío dinámico en el registrador, al igual que usamos el envío dinámico en la función suma.

// f: function with a recursion parameter
// rec: function without the recursion parameter
var sum = function(rec, a){
if (a.length === 0) {
return 0;
} else {
return a[0] + rec(a.slice(1));
}
};
var logging = function(msg, f){
return function(rec, x){
console.log(msg, x);
return f(rec, x);
}
}
var Y = function(f){
var rec = function(x){
return f(rec, x);
}
return rec;
}
//I can add a bunch of wrappers and only tie the knot with "Y" in the end:
console.log( Y(logging("a", logging("b", sum)))([1,2,3]) );

Salida

a [1, 2, 3]
b [1, 2, 3]
a [2, 3]
b [2, 3]
a [3]
b [3]
a []
b []
6

También podríamos extender Y y el registro para que sea variado, pero complicaría un poco el código.

Answer 5

Si no puedes cambiar la función de suma

function sum(a) {
if (a.length === 0) {
return 0;
} else {
return a[0] + sum(a.slice(1));
}
}

entonces es imposible Lo siento

editar

Feo pero funciona. No hagas eso ^^

function rest(a) {
console.log(a);
sum(a, rest);
}
function sum(a, rest) {
if (a.length === 0) {
return 0;
} else {
return a[0] + rest(a.slice(1));
}
}

Pero mira en http://www.nczonline.net/blog/2009/01/20/speed-up-your-javascript-part-2/

Busca el memoizer, lo leeré también.

Answer 6

Vamos a empezar hacia atrás. Digamos que quieres una función traceSum :

> traceSum([1, 2, 3]);
[1, 2, 3]
[2, 3]
[3]
[]
6

Podrías implementar traceSum siguiente manera:

function traceSum(a) {
console.log(a);
if (a.length === 0) return 0;
else return a[0] + traceSum(a.slice(1));
}

Desde esta implementación podemos crear una función de trace generalizada:

function trace(f) {
return function (a) {
console.log(a);
return f(trace(f), a);
};
}

Esto es similar a la forma en que se implementa el combinador Y en JavaScript:

function y(f) {
return function (a) {
return f(y(f), a);
};
}

Su función traceSum ahora se puede implementar como:

var traceSum = trace(function (traceSum, a) {
if (a.length === 0) return 0;
else return a[0] + traceSum(a.slice(1));
});

Desafortunadamente, si no puede modificar la función de sum , entonces no puede trace , ya que necesita alguna forma de especificar qué función se debe devolver dinámicamente . Considerar:

function sum(a) {
if (a.length === 0) return 0;
else return a[0] + sum(a.slice(1));
}

No puede trace la función anterior porque dentro de la función la sum siempre se referirá a la función en sí. No hay manera de especificar el valor de la sum dinámicamente.

Answer 7

function sum(a) {
if (a.length === 0) {
return 0;
} else {
return a[0] + sum(a.slice(1));
}
}
var dummySum = sum, sum = function(args) {
console.log(args);
return dummySum(args);
};
console.log(sum([1, 2, 3]));

Salida

[ 1, 2, 3 ]
[ 2, 3 ]
[ 3 ]
[]
6