Why Does an Optional in Fast Enumeration Cause an Infinite Loop

Why does an optional in fast enumeration cause an infinite loop?

This is an unexpected result, but it is happening because of the way Swift for in loops work under the hood.

for in takes a variable and a Sequence. Swift calls makeIterator() on the Sequence to get an IteratorProtocol which returns successive items when next() is called on the iterator. next() returns an Optional so that it can return nil when all of the items have been exhausted.

In a normal case, you receive the non-optional values and Swift continues giving them out until nil is received in which case the loop ends.

This is the equivalent of your code when you don't use an optional:

let array = ["what"]
var iter = array.makeIterator()
while let text = iter.next() {
    print("Hello World")
}

The optional binding (while let) fails when iter.next() returns nil and the loop ends.

In your case, you have said that you will explicitly receive nil values (by declaring your loop variable as an optional), so when next() is called on the iterator and it is out of values, it hands you a nil which you graciously receive and the loop continues. The iterator continues to hand out nil and you continue to take them, and you have an infinite loop.

This is the equivalent of your code when you use an optional:

let array = ["what"]
var iter = array.makeIterator()
while let text: String? = iter.next() {
    print("Hello World")
}

In this case, the optional binding always works because text can receive the nil.

This blog gives a nice detailed explanation of what is happening under the hood with Swift for in loops.

swift syntax fix for JSON display loop

Your code would work if you remove ? after case let row:

if let puz = v2["Puzzle1"] {
    if let piece1 = puz["Piece_1"] {
        for case let row in piece1 as! Array<Any> { //<- No `?` after `row`
            for r in row as! Array<Int> {
                print(r, terminator: ",")
            }
            print("")
        }
        print("piece1")
    }
    print("puz")
}
print("Finished")

Swift runtime goes into infinite loop when using case let row?, I do not know why.
You may send a bug report to swift.org .

---

But I would write it as follows:

if let puz = v2["Puzzle1"] as? [String: [[Int]]] {
    if let piece1 = puz["Piece_1"] {
        for row in piece1 {
            for r in row {
                print(r, terminator: ",")
            }
            print("")
        }
        print("piece1")
    }
    print("puz")
}
print("Finished")

Better avoid using risky forced casting (as!), and avoid Any when you know the right types.

Why does using `cblas_ccopy` cause intermittent memory errors?

Use cblas_scopy instead of cblas_ccopy. cblas_ccopy copies (single precision) complex numbers which are twice the size of the single precision numbers you actually are using, so you're overrunning the end of the buffer.

How can I iterate over all items in NSMapTable in Swift

In Swift, this is done using conditional assignment.

let enumerator = visibleCollectionReusableHeaderViews.objectEnumerator()

while let myValue: AnyObject = enumerator.nextObject() {
    println(myValue)
}

Note the non optional type for myValue. Otherwise this loop would be infinite as myValue continued to accept nil objects.

Skip first entry in for loop in python?

To skip the first element in Python you can simply write

for car in cars[1:]:
    # Do What Ever you want

or to skip the last elem

for car in cars[:-1]:
    # Do What Ever you want

You can use this concept for any sequence (not for any iterable though).

An efficient data structure to hold structure variable with sorting capability

You need a custom functor for comparing your tries. This should do the trick:

#include <algorithm>
#include <vector>
// try is a keyword. renamed
struct sorthelper : public std::binary_function<try_, try_, bool>
{
    inline bool operator()(const try_& left, const try_& right)
    {   return left.id < right.id;  }
};

...
std::vector<try_> v;
// fill vector 
std::sort(v.begin(), v.end(), sorthelper());
...

Please feel free to ask if you have any follow-up questions. Do you possess the Stroustrup book?

Edit: Suggestion of Matteo:

struct try_
{
    int id;
    string val;
    bool operator<(const try_& other) const
        {return id < other.id;}

}; // no s here plz.

...
std::vector<try_> v;
// fill vector 
std::sort(v.begin(), v.end());
...

Why are Java Streams once-off?

I have some recollections from the early design of the Streams API that might shed some light on the design rationale.

Back in 2012, we were adding lambdas to the language, and we wanted a collections-oriented or "bulk data" set of operations, programmed using lambdas, that would facilitate parallelism. The idea of lazily chaining operations together was well established by this point. We also didn't want the intermediate operations to store results.

The main issues we needed to decide were what the objects in the chain looked like in the API and how they hooked up to data sources. The sources were often collections, but we also wanted to support data coming from a file or the network, or data generated on-the-fly, e.g., from a random number generator.

There were many influences of existing work on the design. Among the more influential were Google's Guava library and the Scala collections library. (If anybody is surprised about the influence from Guava, note that Kevin Bourrillion, Guava lead developer, was on the JSR-335 Lambda expert group.) On Scala collections, we found this talk by Martin Odersky to be of particular interest: Future-Proofing Scala Collections: from Mutable to Persistent to Parallel. (Stanford EE380, 2011 June 1.)

Our prototype design at the time was based around Iterable. The familiar operations filter, map, and so forth were extension (default) methods on Iterable. Calling one added an operation to the chain and returned another Iterable. A terminal operation like count would call iterator() up the chain to the source, and the operations were implemented within each stage's Iterator.

Since these are Iterables, you can call the iterator() method more than once. What should happen then?

If the source is a collection, this mostly works fine. Collections are Iterable, and each call to iterator() produces a distinct Iterator instance that is independent of any other active instances, and each traverses the collection independently. Great.

Now what if the source is one-shot, like reading lines from a file? Maybe the first Iterator should get all the values but the second and subsequent ones should be empty. Maybe the values should be interleaved among the Iterators. Or maybe each Iterator should get all the same values. Then, what if you have two iterators and one gets farther ahead of the other? Somebody will have to buffer up the values in the second Iterator until they're read. Worse, what if you get one Iterator and read all the values, and only then get a second Iterator. Where do the values come from now? Is there a requirement for them all to be buffered up just in case somebody wants a second Iterator?

Clearly, allowing multiple Iterators over a one-shot source raises a lot of questions. We didn't have good answers for them. We wanted consistent, predictable behavior for what happens if you call iterator() twice. This pushed us toward disallowing multiple traversals, making the pipelines one-shot.

We also observed others bumping into these issues. In the JDK, most Iterables are collections or collection-like objects, which allow multiple traversal. It isn't specified anywhere, but there seemed to be an unwritten expectation that Iterables allow multiple traversal. A notable exception is the NIO DirectoryStream interface. Its specification includes this interesting warning:

While DirectoryStream extends Iterable, it is not a general-purpose Iterable as it supports only a single Iterator; invoking the iterator method to obtain a second or subsequent iterator throws IllegalStateException.

[bold in original]

This seemed unusual and unpleasant enough that we didn't want to create a whole bunch of new Iterables that might be once-only. This pushed us away from using Iterable.

About this time, an article by Bruce Eckel appeared that described a spot of trouble he'd had with Scala. He'd written this code:

// Scala
val lines = fromString(data).getLines
val registrants = lines.map(Registrant)
registrants.foreach(println)
registrants.foreach(println)

It's pretty straightforward. It parses lines of text into Registrant objects and prints them out twice. Except that it actually only prints them out once. It turns out that he thought that registrants was a collection, when in fact it's an iterator. The second call to foreach encounters an empty iterator, from which all values have been exhausted, so it prints nothing.

This kind of experience convinced us that it was very important to have clearly predictable results if multiple traversal is attempted. It also highlighted the importance of distinguishing between lazy pipeline-like structures from actual collections that store data. This in turn drove the separation of the lazy pipeline operations into the new Stream interface and keeping only eager, mutative operations directly on Collections. Brian Goetz has explained the rationale for that.

What about allowing multiple traversal for collection-based pipelines but disallowing it for non-collection-based pipelines? It's inconsistent, but it's sensible. If you're reading values from the network, of course you can't traverse them again. If you want to traverse them multiple times, you have to pull them into a collection explicitly.

But let's explore allowing multiple traversal from collections-based pipelines. Let's say you did this:

Iterable<?> it = source.filter(...).map(...).filter(...).map(...);
it.into(dest1);
it.into(dest2);

(The into operation is now spelled collect(toList()).)

If source is a collection, then the first into() call will create a chain of Iterators back to the source, execute the pipeline operations, and send the results into the destination. The second call to into() will create another chain of Iterators, and execute the pipeline operations again. This isn't obviously wrong but it does have the effect of performing all the filter and map operations a second time for each element. I think many programmers would have been surprised by this behavior.

As I mentioned above, we had been talking to the Guava developers. One of the cool things they have is an Idea Graveyard where they describe features that they decided not to implement along with the reasons. The idea of lazy collections sounds pretty cool, but here's what they have to say about it. Consider a List.filter() operation that returns a List:

The biggest concern here is that too many operations become expensive, linear-time propositions. If you want to filter a list and get a list back, and not just a Collection or an Iterable, you can use ImmutableList.copyOf(Iterables.filter(list, predicate)), which "states up front" what it's doing and how expensive it is.

To take a specific example, what's the cost of get(0) or size() on a List? For commonly used classes like ArrayList, they're O(1). But if you call one of these on a lazily-filtered list, it has to run the filter over the backing list, and all of a sudden these operations are O(n). Worse, it has to traverse the backing list on every operation.

This seemed to us to be too much laziness. It's one thing to set up some operations and defer actual execution until you so "Go". It's another to set things up in such a way that hides a potentially large amount of recomputation.

In proposing to disallow non-linear or "no-reuse" streams, Paul Sandoz described the potential consequences of allowing them as giving rise to "unexpected or confusing results." He also mentioned that parallel execution would make things even trickier. Finally, I'd add that a pipeline operation with side effects would lead to difficult and obscure bugs if the operation were unexpectedly executed multiple times, or at least a different number of times than the programmer expected. (But Java programmers don't write lambda expressions with side effects, do they? DO THEY??)

So that's the basic rationale for the Java 8 Streams API design that allows one-shot traversal and that requires a strictly linear (no branching) pipeline. It provides consistent behavior across multiple different stream sources, it clearly separates lazy from eager operations, and it provides a straightforward execution model.

---

With regard to IEnumerable, I am far from an expert on C# and .NET, so I would appreciate being corrected (gently) if I draw any incorrect conclusions. It does appear, however, that IEnumerable permits multiple traversal to behave differently with different sources; and it permits a branching structure of nested IEnumerable operations, which may result in some significant recomputation. While I appreciate that different systems make different tradeoffs, these are two characteristics that we sought to avoid in the design of the Java 8 Streams API.

The quicksort example given by the OP is interesting, puzzling, and I'm sorry to say, somewhat horrifying. Calling QuickSort takes an IEnumerable and returns an IEnumerable, so no sorting is actually done until the final IEnumerable is traversed. What the call seems to do, though, is build up a tree structure of IEnumerables that reflects the partitioning that quicksort would do, without actually doing it. (This is lazy computation, after all.) If the source has N elements, the tree will be N elements wide at its widest, and it will be lg(N) levels deep.

It seems to me -- and once again, I'm not a C# or .NET expert -- that this will cause certain innocuous-looking calls, such as pivot selection via ints.First(), to be more expensive than they look. At the first level, of course, it's O(1). But consider a partition deep in the tree, at the right-hand edge. To compute the first element of this partition, the entire source has to be traversed, an O(N) operation. But since the partitions above are lazy, they must be recomputed, requiring O(lg N) comparisons. So selecting the pivot would be an O(N lg N) operation, which is as expensive as an entire sort.

But we don't actually sort until we traverse the returned IEnumerable. In the standard quicksort algorithm, each level of partitioning doubles the number of partitions. Each partition is only half the size, so each level remains at O(N) complexity. The tree of partitions is O(lg N) high, so the total work is O(N lg N).

With the tree of lazy IEnumerables, at the bottom of the tree there are N partitions. Computing each partition requires a traversal of N elements, each of which requires lg(N) comparisons up the tree. To compute all the partitions at the bottom of the tree, then, requires O(N^2 lg N) comparisons.

(Is this right? I can hardly believe this. Somebody please check this for me.)

In any case, it is indeed cool that IEnumerable can be used this way to build up complicated structures of computation. But if it does increase the computational complexity as much as I think it does, it would seem that programming this way is something that should be avoided unless one is extremely careful.

---

Related Topics