14
\$\begingroup\$

As part of a programming challenge, we are tasked with creating a function with an undetermined number of successive calls. As an example, let's say the function returns simply the sum of the provided arguments, it should work as follows :

sum(4)() // 4
sum(4)(5)() // 9
sum(4)(5)(9)() // 18
sum(4)(5)(9)(1)() // 19
// etc...

The problem is simplified by the allowed empty function call at the end as an indication of end of calls.

I have worked on a solution that does the job but using global variables inside the function itself :

var sum = function (a) {
    if (!sum.init) {
        sum.total = 0;
        sum.init = true;
    }
    if (!arguments.length) {
        sum.init = false;
        return sum.total;
    }
    sum.total += a;
    return sum;
};

This solution works but uses state, global variables and function object trickery which is not ideal. My question here is whether there is a way to solve the problem in a purely recursive way.

As a side note, I do not believe the problem can be solved if that last empty call () is not provided, but if I'm wrong please let me know.

\$\endgroup\$
10
\$\begingroup\$

This solution works but uses state, global variables and function object trickery which is not ideal.

Good hunch. There's certainly some weird stuff going on with your current implementation.

My question here is whether there is a way to solve the problem in a purely recursive way.

Yep! You certainly can. It's a little tricky but we can make light work of it using a couple helper functions identity and sumk.

sumk uses a continuation to keep a stack of the pending add computations and unwinds the stack with 0 whenever the first () is called.

const identity = x => x

const sumk = (x,k) =>
  x === undefined ? k(0) : y => sumk(y, next => k(x + next))

const sum = x => sumk(x, identity)

console.log(sum())                // 0
console.log(sum(1)())             // 1
console.log(sum(1)(2)())          // 3
console.log(sum(1)(2)(3)())       // 6
console.log(sum(1)(2)(3)(4)())    // 10
console.log(sum(1)(2)(3)(4)(5)()) // 15

To make sense of this, remember sumk takes a continuation as an argument. When a Number is given, we recurse sumk with a newly created a continuation that is the sum of the given Number and whatever number comes next. When the Number input is finally undefined, we end the chain of additions with an empty Number (0). Finally the computation is complete and sent to the original continuation provided by sum, the identity function. Since identity just reflects its input, the computed sum will be the final return value.

I think a line-by-line evaluation really helps understand the process of a function. I'll walk you thru a the evaluation of the sum of 3 numbers. When I use the substitution model, notice I'm alpha renaming the parameter generated in lambda.

// instead of:
next => k(x + next)

// you'll see
A => k(x + A)
B => k(x + B)
C => k(x + C)

This renaming of the bound variable just helps you read the code better when the lambdas become nested.

OK, so here we go !

sum(1)(2)(3)()
= sumk(1, identity)(2)(3)()
= (y => sumk(y, A => identity(1 + A)))(2)(3)()
= sumk(2, A => identity(1 + A))(3)()
= (y => sumk(y, B => (A => identity(1 + A))(2 + B)))(3)()
= sumk(3, B => (A => identity(1 + A))(2 + B))()
= (y => sumk(y, C => (B => (A => identity(1 + A))(2 + B))(3 + C)))()
= sumk(undefined, C => (B => (A => identity(1 + A))(2 + B))(3 + C))
= (C => (B => (A => identity(1 + A))(2 + B))(3 + C))(0)
= (B => (A => identity(1 + A))(2 + B))(3 + 0)
= (B => (A => identity(1 + A))(2 + B))(3)
= (A => identity(1 + A))(2 + 3)
= (A => identity(1 + A))(5)
= identity(1 + 5)
= identity(6)
= 6

And finally, if you're not too keen on having sumk in the global scope, you can nest it as an auxiliary function inside sum itself

const identity = x => x

const sum = x => {
  const aux = (x,k) =>
    x === undefined ? k(0) : y => aux(y, next => k(x + next))
  return aux(x, identity)
}

sum(1)(2)(3)() // 6

This was a really fun question and I hope you learn a lot from the answer. If you need any other help, just ask ^_^


EDIT: I see another answer uses currying to achieve the same goal. I didn't originally think to solve the problem this way, so it's cool to see multiple approaches being used. To iterate on that implementation, I might do it something like this

// credit to alebianco for the currying idea
const sum = x => y =>
  y === undefined ? x : sum (x + y)

console.log(sum())                // OOPS!
console.log(sum(1)())             // 1
console.log(sum(1)(2)())          // 3
console.log(sum(1)(2)(3)())       // 6
console.log(sum(1)(2)(3)(4)())    // 10
console.log(sum(1)(2)(3)(4)(5)()) // 15

That ends up being quite elegant. But this currying solution actually has a problem with the following corner case

// should return 0, but always returns a function
console.log(sum())
// y => y === undefined ? x : sum (x + y)

Not really a big issue, but the sumk solution I provided above does not suffer from this.

\$\endgroup\$
  • \$\begingroup\$ The specifications provided by the OP do not require it to work for sum(). \$\endgroup\$ – mbomb007 Jan 30 '17 at 21:46
  • 1
    \$\begingroup\$ If I could vote twice, I would. Beautiful answer! \$\endgroup\$ – גלעד ברקן Jan 31 '17 at 2:06
  • 2
    \$\begingroup\$ @naomik the second solution is great and doesn't have to have a problem with the corner case if we update it as such : const sum = x => x === undefined ? 0 : y => y === undefined ? x : sum (x + y); \$\endgroup\$ – Ghassen Louhaichi Jan 31 '17 at 15:55
16
\$\begingroup\$

This solution uses a functional approach with currying, which i find more elegant since it doesn't have to rely on global variables

function sum(total) {
    return function () {
        if (arguments.length == 0) {
        	return total;
        } else {
        	return sum(total + arguments[0]);
        }
    }
}

console.log(sum(4)()) // 4
console.log(sum(4)(5)()) // 9
console.log(sum(4)(5)(9)()) // 18
console.log(sum(4)(5)(9)(1)()) // 19

The first call to ´sum´, returns the inner function. depending on the number of arguments passed to the inner function, it returns the value of sum's argument as it is or it calls again ´sum´ with the updated running total (thus returning again the inner function to be called again).

The limitation (of this implementation) is that you HAVE TO make a final call with no arguments to have to final value.

See this answer (Method 3: Infinite Level Currying) for an example of using .valueOf to get the result out at every call, even those with arguments.

\$\endgroup\$
  • \$\begingroup\$ This is exactly what I've been missing, a way to pass the information from call to the other without relying on global scope, thank you. \$\endgroup\$ – Ghassen Louhaichi Jan 30 '17 at 15:14
  • 3
    \$\begingroup\$ Note there is a corner case bug for sum() which should probably return 0. You'd have to add another if if you wanted to support this. I'm not sure if it's a problem for the OP tho. Great work otherwise ! \$\endgroup\$ – Thank you Jan 30 '17 at 17:40
  • \$\begingroup\$ es6 default parameters would solve the sum() case - function sum(total = 0) { ... \$\endgroup\$ – punkrockbuddyholly Jan 31 '17 at 10:26
  • \$\begingroup\$ Actually... that only works if you call sum()() \$\endgroup\$ – punkrockbuddyholly Jan 31 '17 at 10:28
  • \$\begingroup\$ why not just use ternary? return (arguments.length == 0) ? total : sum(total + arguments[0]); ... it's CR, after all. \$\endgroup\$ – vaxquis Jan 31 '17 at 12:31
8
\$\begingroup\$

Basically you could use an outer function sum for the initial call and a closure over the starting value a and an inner function fn, which is repeatingly returned and only exited if arguments.length is equal to zero.

If a value b is supplied, the variable a gets updated and the inner function fn gets returned.

function sum(a) {
    return function fn(b) {
        if (!arguments.length) {
            return a;
        }
        a += b;
        return fn;
    };
}

console.log(sum(1)());
console.log(sum(1)(2)());
console.log(sum(1)(2)(3)());

\$\endgroup\$
2
\$\begingroup\$
function add(n){
    var v=function(x){
        return add(n+x);
    }
    v.toString=v.valueof=function(){
        return n;
    }
    return v;
}

console.log(add(1));
console.log(add(1)(2));
console.log(add(1)(2)(3));
console.log(add(1)(2)(3)(5));

All of above answers need to call one extra time to have final result.This solution does not have limitation to make one extra call to evaluate final result. The solution works simply with concept if closures and other important thing which prevents to make extra call is use of valueOf and toString method who will provide primitive computed value resulted from n no. of computed calls.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.