Higher-order function of recursive functions?
Asked Answered
D

7

19

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
Deem answered 5/1, 2014 at 13:10 Comment(0)
P
3

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.

Petigny answered 5/1, 2014 at 15:14 Comment(0)
F
6

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');
Freakish answered 5/1, 2014 at 14:4 Comment(0)
J
3
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]));

Output

[ 1, 2, 3 ]
[ 2, 3 ]
[ 3 ]
[]
6
Jueta answered 5/1, 2014 at 14:11 Comment(0)
F
3

If you insist on using regular functions without using "this", the only way I can think of is applying the logging combinator before you tie the knot with the recursion (Y) combinator. Basically, we need to use dynamic dispatching in the logger just like we used dynamic dispatching in the sum function itself.

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

Output

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

We could also extend Y and logging to be variadic but it would make the code a bit more complicated.

Freakish answered 5/1, 2014 at 14:51 Comment(2)
I think the last statement should be Y(logging("a", sum))([1,2,3]). Your last statement is redundant. Copy paste it in node.js and see for yourself.Petigny
@AaditMShah: I did that on purpose to show that you can add multiple wrappers to the sum function. And its not redundant, they print slightly different things :)Freakish
P
3

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.

Petigny answered 5/1, 2014 at 15:14 Comment(0)
R
1

If you cannot change the sum function

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

then it's impossible. Sorry

edit

Ugly but works. Don't do that ^^

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

But looks at http://www.nczonline.net/blog/2009/01/20/speed-up-your-javascript-part-2/

Search for memoizer, I'll read it too.

Remuneration answered 5/1, 2014 at 13:23 Comment(1)
Yeah, that hard-coded recursive call is a problem. Is there any way to slightly modify sum() to make this work? (Have updated the question slightly to make this clear.)Deem
P
1

It is not possible in JavaScript without modifying the function. If you don't want the manual work, your best bet is something like that:

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

Then you can use it like:

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

Which outputs:

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

logged itself is very slow because it recompiles the function (with eval), but the resulting function is as fast as if you defined it manually. So, use logged only once per function and you are fine.

Prat answered 5/1, 2014 at 14:32 Comment(7)
better use new Function instead of evalRevenue
@Revenue I didn't because the Regex substitution would become more complicated and this shouldn't be used many times anyway. But please, feel encouraged to edit it!Prat
@Revenue ... Why? Same effect. Same security concerns.Pliers
And it is not really faster. But security concerns? In that case? How?Prat
@Pliers see more in mdnRevenue
@Pliers there is nothing talking about using new Function instead. It is the same as eval.Prat
@viclib ummm ... That's my point. Was that supposed to be directed at Grundy?Pliers
A
-2

Scope issue. Try to do the following:

function logging(fn) {
    var _fn = fn; // local cached copy
    return function(a) {
        console.log(a);
        return _fn(a);
    }
}
Armlet answered 5/1, 2014 at 13:14 Comment(1)
That doesn't help. The recursive call to sum() will call the unwrapped version.Deem

© 2022 - 2024 — McMap. All rights reserved.