递归函数的高阶函数？

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

- mjs

Answer 1

我知道这可能不是一个很明确的回答，但如果您使用对象和动态分派方法，想要实现的功能会更容易。基本上，我们将"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');

- hugomg

Answer 2

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

- thefourtheye

Answer 3

如果您坚持使用不带“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和logging扩展为可变参数，但这会使代码变得更加复杂。

- hugomg

---

我认为最后一个语句应该是 Y(logging("a", sum))([1,2,3])。你的最后一个语句是多余的。将其复制粘贴到 node.js 中，自己看看吧。 - Aadit M Shah

我是故意这样做的，以此来展示您可以向sum函数添加多个包装器。它们并不冗余，因为它们打印出略微不同的内容 :) - hugomg

Answer 4

让我们倒过来开始。假设您需要一个名为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);
    };
}

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

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函数，则无法跟踪它，因为您需要某种方式来动态指定要回调的函数。请考虑：

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

您无法跟踪上述函数，因为在函数内部，sum 总是指向函数本身。没有办法动态指定 sum 的值。

- Aadit M Shah

Answer 5

如果您无法更改sum函数

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，我也会阅读它。

- farvilain

---

是的，那个硬编码的递归调用是一个问题。有没有办法稍微修改 sum() 使之工作？（已经略微更新了问题以明确这一点。） - mjs

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即可。

- MaiaVictor

---

最好使用new Function而不是eval。 - Grundy

@Grundy ... 为什么？同样的效果。同样的安全问题。 - svidgen

而且它并不真的更快。但是安全问题呢？在那种情况下？怎么办？ - MaiaVictor

@svidgen 请在mdn中查看更多信息。 - Grundy

@svidgen，没有任何关于使用new Function的讨论。这与eval相同。 - MaiaVictor

Answer 7

作用域问题。尝试执行以下操作：

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

- Jacob

---

那没有帮助。对sum()的递归调用将调用未包装的版本。 - mjs