I recently read and answered Martin R's Recursive flattening of Swift sequences and continued to play around with the code until I arrived at something that was both pretty cool and possibly an abomination. So I figured I'd come back to CR with it and ask others' opinions.
If you want a full context, you should refer to Martin's question, but I'll reiterate the essential parts here:
The function seqentialFlatten(_:_,children:_), takes a sequence and a function that maps an element of that sequence into a sequence of the same type, and lazily returns an AnySequence with all elements that can be generated by repeatedly mapping elements into sequences. One use case of this is getting a list of all subviews of a view:
let someView : UIView = ...
let views = sequentialFlatten([someView], children: { $0.subviews as! [UIView] })
What I've done in this approach is used a more functional style to implement this function, using map and reduce. To achieve this, I've implemented the + operator for Generators, made a generic struct to make it possible to have local lazy variables and wrapped a whole bunch of stuff into AnyGenerators.
And therein lies the problem, I feel perhaps this bit of code has introduce too many new concepts for not much gain. I'll first post the full code and then go through some of my concerns.
func +<G: GeneratorType>(lhs: G, rhs: G) -> AnyGenerator<G.Element> {
var leftGen = lhs
var leftEmpty = false
var rightGen = rhs
var rightEmpty = false
return AnyGenerator {
if !leftEmpty, let elem = leftGen.next() {
return elem
}
leftEmpty = true
if !rightEmpty, let elem = rightGen.next() {
return elem
}
rightEmpty = true
return nil
}
}
struct Lazy<E> {
private let get: () -> E
lazy var val: E = self.get()
init(@autoclosure(escaping) _ getter: () -> E) {
get = getter
}
}
func sequentialFlatten<S : SequenceType>(seq : S, children : S.Generator.Element -> S) -> AnySequence<S.Generator.Element> {
return AnySequence {
() -> AnyGenerator<S.Generator.Element> in
seq.map {
let firstGen = AnyGenerator([$0].generate())
var secondGen = Lazy(sequentialFlatten(children($0), children: children).generate())
return firstGen + AnyGenerator {
secondGen.val.next()
}
}.reduce(AnyGenerator { nil }, combine: +)
}
}
let gen = sequentialFlatten([0], children: { n in n < 50 ? [2*n+1, 2*n+2] : []})
for e in gen {
print(e)
}
Right off the bat, the implementation of the + operator doesn't rub me right. It's overly verbose. At first I had it implemented as:
func +<G: GeneratorType>(lhs: G, rhs: G) -> AnyGenerator<G.Element> {
var leftGen = lhs
var rightGen = rhs
return AnyGenerator {
leftGen.next() ?? rightGen.next()
}
}
which is worlds nicer, but was a nightmare performance-wise. The problem was that, with complicated trees, all of the generators were gone trough, because the + operator relied on the two generators both returning nil to return nil itself. I'd love to see a version of this that is more elegant without losing too much in way of performance.
I'm worried there might be something like my Lazy struct already available and I'm reinventing the wheel.
I'm also worried about all the AnyGenerators I'm throwing around left and right, it seemed necessary, because I can't use my + operator on two different types of Generators. I have tried to rewrite the function and succeeded, but this caused Swift problems with type inference in the reduce as such:
func +<G1: GeneratorType, G2: GeneratorType where G1.Element == G2.Element>(lhs: G1, rhs: G2) -> AnyGenerator<G1.Element> {
var leftGen = lhs
var leftEmpty = false
var rightGen = rhs
var rightEmpty = false
return AnyGenerator {
if !leftEmpty, let elem = leftGen.next() {
return elem
}
leftEmpty = true
if !rightEmpty, let elem = rightGen.next() {
return elem
}
rightEmpty = true
return nil
}
}
Some general concerns:
- Is the performance okay? (speed and memory usage)
- Is the code Swifty enough?
