result.shift 2 probably doesn't do what you think it does. You meant unshift.
shift removes the first element of an array (and doesn't take any arguments).unshift adds new items at the beginning of the array.
As a result, your final array isn't [2,3,5,...] but [5,...]
Also, I'll point out the bug in the code you have in your "equivalent Javascript code" link - it has >= in the result = (n for n in numbers when n >= 0) at the bottom instead of n > 0 (which is correct).
You probably guessed that since your code here has that fixed. n >= 0 doesn't filter the 0 elements from the array, n > 0 does.
And now for the functional ways. (Disclaimer: I don't think my functional rewrite of your code is any prettier - but it's more functional. Maybe someone can make it look more elegant?)
I'm no expert on functional programming, but from what I've learned, you generally try to use things like map, reduce, filter.
[].filter() takes predicate (test function returning boolean) that gets called with all the elements one by one and returns array with values that pass the test. You kind of already used it in the (n for n in numbers when n > 0) - it's the when part.
[].map() takes a "transforming" function that gets called with all the elements one by one and returns array with the transformed values. With CoffeeScript we can cheat again and use list comprehensions: (my_function(x) for x in xs).
[].reduce() is probably the least intuitive one - but we'll use it in your sieve :) You give it an initial value (accumulator) and a transforming function and it reduces the array left to right to a single value. The canonical example is summation: the_sum = [1,2,3].reduce(((acc, val) -> acc + val), 0) # the_sum is 6 now.
Now, when I hear "functional paradigm," I hear "loopless way" and "immutability." Functional programming is about more things, of course.
EDIT: oh man, I had limit = 100 in the code. Stupid mistake :) Fixed now.
sieve_sundaram = (limit) ->
start = 4
half = limit/2
numbers = (n for n in [3...limit+1] by 2)
steps = numbers[..] # copy of numbers
As you can see, numbers equals steps, at least at the first go. What we'll change will be the loops. Instead of thinking in terms of for ... do ..., we'll think more like result = (... for ...) - transforming the arrays with our map, filter, reduce functions or their CoffeeScript counterparts.
Now, we have to define the transforming function for the reduce(), because we want to do something like steps.reduce(callback,numbers). You see, with a little bit of imagination you had for step in steps do something in your code.
Now we'll do exactly that - our function for the reduce will get a step at every call, just like your loop did. So that's that.
Next problem we have is rewriting the "global" changes you make inside the loop. So we need to do something about the numbers[i-1] = 0 and start += 2 * (step + 1) lines. We'll make the changes propagate through the result values.
But how can we make two things propagate through one value? We'll use an array. Remember, numbers is an array and start is a number. Essentially we'll insert the start at the beginning (or the end, wouldn't matter) of the numbers array and at each call of our reduce callback extract it from there - and of course, after the reduce finishes.
callback = (start_and_nums,step) ->
start = start_and_nums[0]
nums = start_and_nums[1..]
So that's the extraction part. Pretty trivial with CoffeeScript.
Next part is little bit trickier. If you're familiar with recursion, you know the base case is usually written before the other parts of recursive function. We'll do something similar - check for your if start > half condition before we do anything else.
If it's true, it will simply mean that we don't need to do any of that sieving mumbo jumbo, that we're done and just need to wait till we get through all the elements, because we can't stop the reduce function midway.
if start > half
result = (n for n in nums when n > 0)
result.unshift start
return result
# We can't stop iterating inside the reduce() although we'd like to right now.
# Also, we slice the first element every time our function gets called,
# so we'll put it back here for now. We'll deal with it after reduce() finishes.
# Also, we mustn't forget about the 2!
Next portion of the code is reached only if we still have work to do (we didn't get to the return inside the if). It's outdented, but maybe that's hard to see with my comments between the lines.
Now, look at your for i... line. What you really want is i-1, because you use it in the next line (numbers[i-1]). So we'll use map. It should be pretty straightforward:
idxs = (idx-1 for idx in [start...half] by step)
OK, we have the is, now we have to deal with the sieving. If you look at your code and think about it in terms of transforming one array to another, you realize you either change an element to 0 if it was unlucky and its index was in the [start...half] by step, or don't change anything if the index wasn't there. Look how it translates to code:
new_nums = ((if i in idxs then 0 else num) for num,i in nums)
We dealt with the sieving, now we need to change the start variable. That's trivial:
new_start = start + 2 * (step + 1)
And we need to prepare these new values for the next "iteration" - and return them. You can see that instead of deciding whether to finish or loop again right after changing the start, we delegate that to the beginning of the callback.
If we had it here instead of at the beginning, we'd do unnecessary (and potentially harmful) changes to the numbers array, because we can't stop the reduce from getting through all the steps. That's a minor disadvantage of this approach - we do some unnecessary work. But we can limit it to just finding out if we actually need to do something or can just return immediately.
new_start_and_nums = new_nums[..]
new_start_and_nums.unshift new_start
return new_start_and_nums
That's the end of our callback function. Now remember, the function works with start_and_nums, but so far we have only the numbers. Let's fix that:
start_and_nums = numbers[..]
start_and_nums.unshift start
And let's finally run the reduce function!
result = (steps.reduce(callback,start_and_nums))
We don't really need the start value at the beginning.
result.shift()
But we need to put in the 2! The point of doing it here and not in the callback is again that we can't stop reduce from stopping. If we inserted it in there, it would get inserted multiple times.
result.unshift 2
Aaaand we're done.
return result
By the way, thanks for your question - I see the Sundaram's sieve for the first time. Seems very elegant :)
The final code: either copypaste the snippets above or use this gist :) But I sincerely hope you at least read through this and not just use the final thing, because of the time I put into writing the explanations... :D
