Reverse Zip a Collection

Question

I'm looking to do a "reverse zip" on a collection. Essentially meaning:

let a = [1, 2, 3, 4, 5, 6, 7]
let (left, right) = a.reverseZip()

print(left)  // [1, 3, 5, 7] 
print(right) // [2, 4, 6]

I have an implementation that seems to work (see my answer listed below), but I have two questions that I'm hoping we could discuss:

1. What's the correct name for this kind of operation? It's not exactly the opposite of zip (and I'm certain this pattern exists elsewhere in another functional language)
2. Is there a more optimal algorithm for this method?

Answer 1

extension Collection {

    func reverseZip() -> ([Element], [Element]) {

        var left  = [Element]()
        var right = [Element]()

        let capacity = Double(self.count) / 2.0
        left .reserveCapacity(Int(ceil(capacity)))
        right.reserveCapacity(self.count / 2)

        for element in self {

            if left.count > right.count {
                right.append(element)
            } else {
                left.append(element)
            }
        }
        return (left, right)
    }
}

UPDATE (03/10/18) Thank you all for your help. Seems like a lot of you latched onto Stride, which is definitely a good way to go. I resisted this approach for 2 reasons:

1. I'm keen to keep this function as an extension of Collection, rather than Array
2. Strictly speaking, the startIndex of a given Collection isn't necessary 0, and the progression of indexes isn't necessarily an increment of 1 each time.

Martin R's approach of using a custom iterator definitely seemed like the right approach, so I used that along with the WWDC 2018's implementation of "EveryOther" to create a standard sequential iterator that simply goes along two elements in each while loop block, till it hits the end.

extension Collection {

    func deinterleave() -> ([Element], [Element]) {
        let smallHalf = count / 2
        let bigHalf   = count - smallHalf

        var left  = [Element]()
        var right = [Element]()

        left .reserveCapacity(bigHalf)
        right.reserveCapacity(smallHalf)

        let start = self.startIndex
        let end   = self.endIndex

        var iter = start
        while iter != end {
            left.append(self[iter])
            iter = index(after: iter)

            if iter == end { break }
            right.append(self[iter])

            iter = index(after: iter)
        }
        return (left, right)
    }
}

let a = [1,2,3,4,5,6,7]
print(a.deinterleave()) // ([1, 3, 5, 7], [2, 4, 6])

Without a doubt, there is some scope to improve this further and use vacawama's LazyMapSequence implementation, but for now this does everything I need it to.

Answer 2

Based on vacawama's idea to return lazy collections instead of arrays, here is a possible generalization to arbitrary collections with arbitrary strides:

extension Collection {

    func makeStrideIterator(stride: Int) -> AnyIterator<Element> {
        precondition(stride > 0, "The stride must be positive")
        var it = makeIterator()
        var first = true
        return AnyIterator<Element> {
            if first {
                first = false
            } else {
                // Skip `stride - 1` elements:
                for _ in 1..<stride {
                    guard let _ = it.next() else { return nil }
                }
            }
            return it.next()
        }
    }
}

The method returns an AnyIterator (which is both an iterator and a sequence) of the collection elements at the positions

0, stride, 2*stride, ...

Unzipping an array (or any other collection) can then be done with

let a = [1, 2, 3, 4, 5]
let left = a.makeStrideIterator(stride: 2)
let right = a.dropFirst().makeStrideIterator(stride: 2)

for e in left { print(e) }
// 1, 3, 5
for e in right { print(e) }
// 2, 4

Here is an example for picking every third character from a string:

for c in "ABCDEFG".makeStrideIterator(stride: 3) {
    print(c)
}
// A D G

The special case of unzipping into two arrays can then be implemented as

extension Collection {
    func unzip() -> ([Element], [Element]) {
        return (Array(makeStrideIterator(stride: 2)),
                Array(dropFirst().makeStrideIterator(stride: 2)))
    }
}

Example:

print([1, 2, 3, 4, 5].unzip())
// ([1, 3, 5], [2, 4])

Answer 3

This is a seed of an idea. Instead of returning arrays, it would be more efficient to return sequences.

Here is an Array extension that returns two LazyMapSequence<StrideTo<Int>, Element>. The advantage is that is doesn't actually generate the sequences; they are provided on demand because they're lazy. This is much like the way reversed() works on an Array.

extension Array {

    func reverseZip() -> (LazyMapSequence<StrideTo<Int>, Element>, LazyMapSequence<StrideTo<Int>, Element>) {

        let left = stride(from: 0, to: self.count, by: 2).lazy.map { self[$0] }
        let right = stride(from: 1, to: self.count, by: 2).lazy.map { self[$0] }

        return (left, right)
    }
}

Example:

let a = [1, 2, 3, 4, 5, 6, 7]
let (left, right) = a.reverseZip()

// iterate left
for i in left {
    print(i)
}

1
3
5
7

// turn them into arrays to print them
print(Array(left))

[1, 3, 5, 7]

print(Array(right))

[2, 4, 6]

I'm sure this can be generalized to something more general than Array. That is left as an exercise to the reader.

---

If you want two arrays

If you really want the two arrays, then you'd just return the result of map (taking out lazy):

extension Array {

    func reverseZip() -> ([Element], [Element]) {

        let left = stride(from: 0, to: self.count, by: 2).map { self[$0] }
        let right = stride(from: 1, to: self.count, by: 2).map { self[$0] }

        return (left, right)
    }
}