#SequentialFlatten(), a recursive approach

SequentialFlatten(), a recursive approach

The four lines where you try to dequeue the first generator could be written in one line if Arrays had a popFirst function. (Which it should but weirdly doesn't.) So we can define that ourselves in an extension. (though this really is a matter of preference)

The four lines where you try to dequeue the first generator could be written in one line if Arrays had a popFirst function. (Which it should but weirdly doesn't.) So we can define that ourselves in an extension. (though this really is a matter of preference)

while var gen = generator {
    ...
}

That way, you don't have to force unwrap gen.

_{This doesn't work, since gen.next()only mutates the local variable gen}

I would opt to use while let instead of explicitly checking if gen is nil:

while let _ = gen {
    ...
}

gen = queue.popFirst()

_{This one might be going a bit far because we're extending Array just to get rid of 3 lines, but I really think it improves readability. In the end it's you're call.}

func sequentialFlatten<S : SequenceType>(seq : S, children : (S.Generator.Element) -> S) -> AnySequence<S.Generator.Element> {
    return AnySequence {
        () -> AnyGenerator<S.Generator.Element> in
        
        // Current generator, or `nil` if all sequences are exhausted:
        var gen: S.Generator? = seq.generate()
        // Queue of generators for sequences which still have to be enumerated:
        var queue: [S.Generator] = []
        
        return AnyGenerator {
            
            while let _ = gen {
                if let next = gen?.next() {
                    queue.append(children(next).generate())
                    return next
                }
                // Current generator is empty, try to deque next one:
                gen = queue.popFirst() // `nil` if queue is empty
            }
            return nil
        }
    }
}

I'd rename gen to generator so that in the while loop, you can do:

while let gen = generator {
    ...
}

That way, you don't have to force unwrap gen.

You need to declare generator and the elements of queueas AnyGenerators for this to work. That way they are ensured to be reference types and gen and generator refer to the same instance.

// Current generator, or `nil` if all sequences are exhausted:
var generator: AnyGenerator<S.Generator.Element>? = AnyGenerator(seq.generate())
// Queue of generators for sequences which still have to be enumerated:
var queue: [AnyGenerator<S.Generator.Element>] = []

generator = queue.popFirst()

_{This one might be going a bit far because we're extending Array just to get rid of 3 lines, but I really think it improves readability. In the end it's your call.}

func sequentialFlatten<S : SequenceType>(seq : S, children : (S.Generator.Element) -> S) -> AnySequence<S.Generator.Element> {
    return AnySequence {
        () -> AnyGenerator<S.Generator.Element> in
        
        // Current generator, or `nil` if all sequences are exhausted:
        var generator: AnyGenerator<S.Generator.Element>? = AnyGenerator(seq.generate())
        // Queue of generators for sequences which still have to be enumerated:
        var queue: [AnyGenerator<S.Generator.Element>] = []
        
        return AnyGenerator {
            
            while let gen = generator {
                if let next = gen.next() {
                    queue.append(AnyGenerator(children(next).generate()))
                    return next
                }
                // Current generator is empty, try to deque next one:
                generator = queue.popFirst() // `nil` if queue is empty
            }
            return nil
        }
    }
}