result.shift 2 probably doesn't do what you think it does. You meant
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
>= 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
.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,
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
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
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)
# 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[..]
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[..]
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.
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.
Aaaand we're done.
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