Higher-order function of recursive functions?

Question

Is there some way to "wrap" a recursive function via a higher-order function, so that the recursive call is also wrapped? (e.g. to log the arguments to the function on each call.)

For example, suppose we have a function, sum(), that returns the sum of a list of numbers by adding the head to the sum of the tail:

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

Is there some way to write a higher-order function, logging(), that takes the sum() function as input, and returns a function that outputs the arguments to sum() on each recursive call?

The following does not work:

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

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

Actual output:

[1, 2, 3]
-> 6

Expected output:

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

Is this even possible if sum() is rewritten so that it can be used with Y Combinator-style "recursion"?

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

I know this is kind of a non-answer but what you want is much easier to do if you use objects and dynamically dispatched methods. Essentially, we store "rec" in a mutable cell instead of having to pass it around.

It would be kind of similar to sum = logging(sum) (instead of sum2 =) but is more idiomatic and doesn't hardcode the name for the mutable reference we dispatch on.

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 2

Let's start backwards. Say you want a function traceSum:

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

You could implement traceSum as follows:

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

From this implementation we can create a generalized trace function:

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

This is similar to the way the Y combinator is implemented in JavaScript:

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

Your traceSum function can now be implemented as:

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

Unfortunately if you can't modify the sum function then you can't trace it since you need some way to specify which function to callback dynamically. Consider:

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

You cannot trace the above function because inside the function sum will always refer to the function itself. There's no way to specify the value of sum dynamically.