My first accumulators

Question

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

• Flambino: In the future, it'd be nice if you could post this as two separate questions: One about the Scheme implementation, and one about the the JS (and link from one to the other, for those interested)
• Racheet: @Flambino Thanks, you're probably right. In some ways the question was about if I'd properly understood the differences in the algorithm caused by design constraints of the two languages. I thought that separating them out into different questions would have made it difficult to ask for that kind of feedback.
• Racheet: I could also do with some feedback confirming that the algorithm I'm implemented is actually foldr like I think (and not foldl), I'm not 100% on that. Either way, the code works, so it belongs on code review and not SO.
• Flambino: Yeah, I can understand that you'd like to contrast and compare the two implementations - unfortunately, I don't know enough scheme :-/ And you're right: This is actually a leftward fold, not foldr. I'll update my answer :)

Answer 1

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 :)

• Racheet: Thanks, that's really useful feedback. I hadn't thought about using array.slice, but now you mention it, it's blindingly obvious. I did think about putting the function argument at the end, but decided that since in the nodejs style that usually denotes a callback, and this isn't one, it was better to go with the the standard order to avoid "confusion by convention".
• Flambino: @Racheet It's true that in Node it's most often callbacks that go at the end, but that's because there are a lot of callbacks in Node :) Anyway, "callback" doesn't have to mean "function to call exactly once, when we're done", it can just mean "a function to call". In the case of a fold, it'll be called n times along the way. Also, I've updated my answer re: foldr vs foldl

Answer 2

Speaking for Scheme over here; looks pretty good. I have precisely three aesthetic quibbles, but you got the essence. Also, whether by accident or intention, you aren't doing the Scheme version destructively, so the comments Flambino had for your JS version don't apply here.

1. The base case in a list recursion is usually expressed as (null? foo) rather than (not (pair? foo))
2. You can use word-separators to keep names more readable (I'd have named this one fold-left myself).
3. Most implementations I've seen use the name memo where you have initial. I think it's mildly more appropriate, since by the time you've called your first recursion, it contains the previous result rather than the initial value.

• Flambino: Good point about initial vs memo. I was looking at that myself, but didn't change it (oddly, I used memo in an example, though, without even thinking about it)