Higher-order function of recursive functions?

higher-order-functions, javascript, recursion, y-combinator

Solution

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.

Problem

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 ```

Original source