Consider a simple function that adds the first N natural numbers. (e.g. sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15
).
Here is a simple JavaScript implementation that uses recursion:
function recsum(x) {
if (x === 0) {
return 0;
} else {
return x + recsum(x - 1);
}
}
If you called recsum(5)
, this is what the JavaScript interpreter would evaluate:
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.
Here's a tail-recursive version of the same function:
function tailrecsum(x, running_total = 0) {
if (x === 0) {
return running_total;
} else {
return tailrecsum(x - 1, running_total + x);
}
}
Here's the sequence of events that would occur if you called tailrecsum(5)
, (which would effectively be tailrecsum(5, 0)
, because of the default second argument).
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
In the tail-recursive case, with each evaluation of the recursive call, the running_total
is updated.
Note: The original answer used examples from Python. These have been changed to JavaScript, since Python interpreters don't support tail call optimization. However, while tail call optimization is part of the ECMAScript 2015 spec, most JavaScript interpreters don't support it.
The yield
contextual keyword actually does quite a lot here.
The function returns an object that implements the IEnumerable<object>
interface. If a calling function starts foreach
ing over this object, the function is called again until it "yields". This is syntactic sugar introduced in C# 2.0. In earlier versions you had to create your own IEnumerable
and IEnumerator
objects to do stuff like this.
The easiest way understand code like this is to type-in an example, set some breakpoints and see what happens. Try stepping through this example:
public void Consumer()
{
foreach(int i in Integers())
{
Console.WriteLine(i.ToString());
}
}
public IEnumerable<int> Integers()
{
yield return 1;
yield return 2;
yield return 4;
yield return 8;
yield return 16;
yield return 16777216;
}
When you step through the example, you'll find the first call to Integers()
returns 1
. The second call returns 2
and the line yield return 1
is not executed again.
Here is a real-life example:
public IEnumerable<T> Read<T>(string sql, Func<IDataReader, T> make, params object[] parms)
{
using (var connection = CreateConnection())
{
using (var command = CreateCommand(CommandType.Text, sql, connection, parms))
{
command.CommandTimeout = dataBaseSettings.ReadCommandTimeout;
using (var reader = command.ExecuteReader())
{
while (reader.Read())
{
yield return make(reader);
}
}
}
}
}
Best Answer
I think the accepted answer is great, but it seems many people have failed to grasp some fundamental points.
First, Scala's
for
comprehensions are equivalent to Haskell'sdo
notation, and it is nothing more than a syntactic sugar for composition of multiple monadic operations. As this statement will most likely not help anyone who needs help, let's try again… :-)Scala's
for
comprehensions is syntactic sugar for composition of multiple operations with map,flatMap
andfilter
. Orforeach
. Scala actually translates afor
-expression into calls to those methods, so any class providing them, or a subset of them, can be used with for comprehensions.First, let's talk about the translations. There are very simple rules:
This
is translated into
This
is translated into
This
is translated on Scala 2.7 into
or, on Scala 2.8, into
with a fallback into the former if method
withFilter
is not available butfilter
is. Please see the section below for more information on this.This
is translated into
When you look at very simple
for
comprehensions, themap
/foreach
alternatives look, indeed, better. Once you start composing them, though, you can easily get lost in parenthesis and nesting levels. When that happens,for
comprehensions are usually much clearer.I'll show one simple example, and intentionally omit any explanation. You can decide which syntax was easier to understand.
or
withFilter
Scala 2.8 introduced a method called
withFilter
, whose main difference is that, instead of returning a new, filtered, collection, it filters on-demand. Thefilter
method has its behavior defined based on the strictness of the collection. To understand this better, let's take a look at some Scala 2.7 withList
(strict) andStream
(non-strict):The difference happens because
filter
is immediately applied withList
, returning a list of odds -- sincefound
isfalse
. Only thenforeach
is executed, but, by this time, changingfound
is meaningless, asfilter
has already executed.In the case of
Stream
, the condition is not immediatelly applied. Instead, as each element is requested byforeach
,filter
tests the condition, which enablesforeach
to influence it throughfound
. Just to make it clear, here is the equivalent for-comprehension code:This caused many problems, because people expected the
if
to be considered on-demand, instead of being applied to the whole collection beforehand.Scala 2.8 introduced
withFilter
, which is always non-strict, no matter the strictness of the collection. The following example showsList
with both methods on Scala 2.8:This produces the result most people expect, without changing how
filter
behaves. As a side note,Range
was changed from non-strict to strict between Scala 2.7 and Scala 2.8.