My first accumulators

Notes

I'm working my way through SICP, and as I got very confused by the section on folds, I decided to try to implement foldr in scheme and javascript to understand how it works differently with immutable and mutable variables.

I'm mostly looking for advice on whether or not what I've done makes sense idiomatically in each language, but any other feedback would be very much appreciated.

Scheme

;Foldr implemented so I can understand it
(define (foldright function initial collection)
        (if (not (pair? collection))
             initial
            (foldright function (function initial (car collection)) (cdr collection))))

;Test Case (should return 10)
(foldright (lambda (x y) (+ x y)) 0 (list 1 2 3 4))

Javascript

function foldr(func, initial, collection) {
    if (collection.length === 0) {
        return initial
    };
    initial = func(initial, collection[0]);
    collection.shift();
    return foldr(func, initial, collection);
};

//Test case (should return 10)   
var result = foldr(function (a, b) {
    return a + b;
}, 0, [1, 2, 3, 4]);

console.log(result);

I can only speak to the JS code - which looks pretty good, by the way... except:

You're modifying the array you're folding. In fact, you're truncating it completely due to your use of shift. So your function has destructive side-effects. After the fold, you have your answer, but you've lost the question, so to speak.

I.e.,

var question = [2, 3, 7];
var answer = foldr(function (a, b) { return a * b; }, 0, input);

console.log(answer);   // => 42
console.log(question); // => [] ... oops

Hence it'd be better to do something like this, using slice(1) to get a copy of the array starting from index 1:

function foldl(func, initial, collection) { // not foldr (see below)
    if (collection.length === 0) {
        return initial;
    }
    initial = func(initial, collection[0]);
    return foldl(func, initial, collection.slice(1));
}

By the way: You'll see I've removed the semicolon after the if block - it's not necessary (JS just ignores it, as it does the semicolon after the function body). But I've inserted a semicolon after return initial inside the block. That semicolon isn't strictly necessary either, since JS will see the close-brace following it, and insert its own semicolon. But better to do it properly yourself.

You could also write the condition as simply if (!collection.length), and it could be considered idiomatic. But I prefer your current - strict and explicit - condition myself.

Lastly, I'd prefer the Node.js style of placing function arguments at the end, like foldr(initial, collection, func) only because it avoids the dangling arguments after an inline function. On the other hand, JavaScript itself favors putting function arguments first, as in the built-in Array.prototype.reduce function... it's a tough call (no pun intended).

Update: I hadn't even noticed, until I read your comment above, but yes, your function is actually foldl, not foldr. You're reducing the array from first to last (i.e. from the left). So the first value passed to func is the first element in the array. A foldr function would pass the values in reverse order. A real foldr function could be:

function foldr(func, initial, collection) { // for real this time
    if( collection.length > 1) {
        initial = foldr(func, initial, collection.slice(1));
    }
    return func(initial, collection[0]);
}

You can check the behavior like this:

var func = function (memo, value) {
    memo.push(value);
    return memo;
};

foldl(func, [], [1, 2, 3, 4]); // => [1, 2, 3, 4]
foldr(func, [], [1, 2, 3, 4]); // => [4, 3, 2, 1] (reversed!)

Update 2: While I'm at it, here's a more memory efficient solution, that doesn't use slice and thus doesn't create n-1 arrays along the way. A similar technique can be used for foldl

function foldr(func, memo, collection) {
    var l = collection.length - 1;
    function fold(offset) {
        if( offset < l ) {
            memo = fold(offset + 1);
        }
        return func(memo, collection[offset]);
    }
    return fold(0);
}

Of course, neither this nor the functions above actually check whether the input array is empty (of if it's even an array)... not that that's terribly difficult to do, but I've complicated things enough already, I think :)

StackExchange Code Review Q#46729, answer score: 8