递归函数的高阶函数？

Question

是否有某种方式通过高阶函数“包装”递归函数，使递归调用也包装？ （例如，在每次调用时将参数记录到函数中）。

例如，假设我们有一个函数sum()，它通过将头添加到尾部的总和来返回数字列表的总和：

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

是否有某种方式来写一个高阶函数，logging()，即采取sum()功能作为输入，并返回参数输出到sum()每个递归调用的函数吗？

下不起作用：

function logging(fn) { 
    return function(a) { 
     console.log(a); 
     return fn(a); 
    } 
} 

sum2 = logging(sum); 
sum2([1, 2, 3]); 

实际输出：

[1, 2, 3] 
-> 6 

预期输出：

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

如果sum()被改写，以便它可以是这甚至可能用于Y Combinator风格的“递归”？

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

让我们开始向后。说你想要一个功能traceSum：

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

您可以实现traceSum如下：

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

从这个实现，我们可以创建一个通用trace功能：

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

这类似于Y组合器在JavaScript中实现的方式：

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

你traceSum功能现在可以为实现：

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

不幸的是，如果你不能修改sum功能，那么你不能trace，因为你需要一些方法来指定哪些功能回调动态地。试想一下：

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

你不能trace上述功能，因为里面的功能sum总是引用函数本身。无法动态指定sum的值。

Answer 2

范围问题。尽量做到以下几点：

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

Answer 3

如果你不能改变的总和功能

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

那么它是不可能的。对不起

编辑

丑，但工程。不要做^^

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

但着眼于http://www.nczonline.net/blog/2009/01/20/speed-up-your-javascript-part-2/

搜索memoizer，我会看看它。

Answer 4

我知道这是怎样的一个非答案，但你想要的东西是容易得多，如果你使用的对象和动态分派方法来做。本质上，我们将“rec”存储在一个可变单元格中，而不必传递它。

这将是一种类似于sum = logging(sum)（而不是sum2 =），但更地道和我们派遣的可变引用没有硬编码名称。

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 5

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

输出

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

Answer 6

不可能在JavaScript无需修改功能。如果你不希望体力劳动，最好的方法是类似的东西：

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

然后你可以使用它像：

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

，输出：

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

logged本身非常缓慢，因为它重新编译该函数（使用eval），但函数结果与手动定义函数一样快。所以，每个功能只能使用logged一次，你很好。

Answer 7

如果你坚持使用常规函数而不使用“this”，我能想到的唯一方法就是在用递归（Y）组合器绑定结之前应用日志组合器。 基本上，我们需要在记录器中使用动态分派，就像我们在求和函数本身中使用动态分派一样。

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

输出

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

我们也可以延伸Y和记录是可变参数，但它会使代码有点复杂。