Tuple-wrangling

EDIT: updated for Swift 2.0

Attention conservation notice: this is a bit of a ramble with no real payoff.

@OldManKris posted some code on github earlier in the week, with a version of zip that could zip together 3 arrays instead of 2. He also implemented an unzip function, that took an array of tuples and unzipped it into a tuple of arrays, that is:

let tuples = [
    ( 1, "1", 1.0), 
    ( 2, "2", 2.0), 
    ( 3, "3", 3.0),
]

let arrays = unzip(tuples)

// arrays now contains:
// ([1,2,3],["1","2","3"],[1.0,2.0,3.0])

Given my recent posts, my mind immediately went to making unzip lazy. But before we get to that, let’s muck about with tuples some.

The Swift standard library has a class for zipping together two sequences into a sequence of tuples. It’s called Zip2, and it’s a lazy sequence that only zips on demand, returning a 2-tuple of the corresponding elements of that position in the two collections:

let r = 1...3
let a = [6, 7, 8]
let z = Zip2(a,r)
for (x, y) in z {
    // iterate over (1,6),
    // (2,7) and (3,8)
}

Why Zip2? Why not just Zip, a class that takes an arbitrary number of sequences and zips them together into an n-tuple? Its init could take a variadic argument for the sequences. Why isn’t it that easy?

Because types, that’s why. Specifically, the type of of Zip2.GeneratorType.Element. It’s a 2-tuple, containing the types of the elements of the two sequences. It’s generic, sure – the first and second element can be of any type. But it’s emphatically a 2-tuple: ZipGenerator2 defines typealias Element = (E0.Element, E1.Element). If you wanted to create another version that supported a 3-tuple, you’d have to create a whole new class Zip3 that defined Element to be of type (E0.Element, E1.Element, E2.Element). There’s no general way of representing an n-tuple.

Similarly, Kris’s code defines unzip3 for operating on 3-tuples. Is there any way of unzipping an arbitrary tuple? The name unzip3 is taken from Haskell, which follows the same convention (as well as unzip4, unzip5 etc.). That Haskell (and Scala, and F#) doesn’t just define a generalized zip/unzip suggests it’s probably hard to do.1 2

edit: Swift 1.2 introduced a zip function, that takes two sequences and returns a Zip2. This could be a step towards overloading to return Zip3, Zip4 etc. for more than two sequences. So you can now write:

let r = 1...3
let a = [6, 7, 8]
let z = zip(a,r)
for (x, y) in z {
    // iterate over (1,6),
    // (2,7) and (3,8)
}

Unless… we make the switch from compile-time to run-time type identification. Then we have more tools at our disposal – Any, a type which can stand in for any type, and Mirror, the class that allows you to reflect and inspect the contents of a type.

Using Any might put some people off. Possibly if you’re a C programmer, you might worry it’s like void* and you’re one mis-cast away from an explosion. But I think of Any much like optionals – safe to use with the support the language gives you (such as if let x = y as? Type, similar to if let x = y for optionals).

Just like optionals, before you use it, you should ask the question “is there any other way?”. Just as it’s a pain to have to check an optional when it didn’t need to be an optional, it’s a pain to have to cast an Any, but if there’s no neater way then it’s OK.

The Mirror protocol allows you to examine any type at runtime. You get an object’s mirror by calling reflect(obj), passing in your object. If the object implements the Reflectable protocol, then the mirror you get back will be that type’s specific implementation of Mirror. If it doesn’t, you’ll get back the default implementation. Playgrounds use mirrors to determine how to display the values of variables, and a custom mirror would enable a type to pretty-print in the playground, for example like Array does.

The fact that Mirror is used by playgrounds has led some to infer it’s not to be relied on for other purposes – that it’s just there for debug. I’m not so sure – that it’s there in the standard library, and objects can implement their own mirrors, suggests it’s more solidly part of the language proper, like IntegerLiteralConvertible or Collection. As much as anything is in this beta is, anyway.3

Mirror isn’t a collection, but it is “collection-like”, in that it has a count property and supports subscripting. This is a good point, by the way – you don’t have to be a collection to be subscriptable.

The default implementation counts and exposes an object’s member variables, with the subscript returning a pair with the name and value of each member. It also provides a disposition enum, which indicates what kind of object it is – a struct, an enum, an index container (such as an array).

Or… a tuple. That means we could use mirrors to inspect a tuple at runtime to determine how many elements it has. Here is a struct, TupleCollectionView, that uses mirrors to take a tuple and make it look like a collection:

struct TupleCollectionView<T>: CollectionType {
    private let _mirror: MirrorType
    init(_ tuple: T) {
        _mirror = reflect(tuple)
    }

    var startIndex: Int { return 0 }

    var endIndex: Int {
        guard case .Tuple = _mirror.disposition
          else { return 1 }

        return _mirror.count
    }

    subscript(idx: Int) -> Any {
        guard case .Tuple = _mirror.disposition
          else { return _mirror.value }

        return _mirror[idx].1.value
    }
}

let t = (7,8,9)
let c = TupleCollectionView(t)
c[0]  // returns 7
c[2]  // returns 9

But wait, you ask, what if I pass something other than a tuple in? Well, I answer (in a deeply philosophical tone), what really is a variable if not a tuple of one element? Every variable in Swift is a 1-tuple. In fact, every non-tuple variable has a .0 property that is the value of that variable.4 Open up a playground and try it. So if you pass in a non-tuple variable into TupleCollectionView, it’s legit for it to act like a collection of one. If you’re unconvinced, read that justification again in the voice of someone who sounds really confident.

By using this view, we can easily write a version of unzip that takes a collection of n-tuples and returns them unzipped, if not as an array of tuples, then at least as an array of arrays.5

func unzip<C: CollectionType>(tuples: C) -> [[Any]] {
    var unzipped: [[Any]] = []

    var g = tuples.generate()
    if let t = g.next() {
        // take the first element and set up
        // the return array
        let c = TupleCollectionView(t)
        for e in c {
            unzipped.append([e])
        }

        // slot the remaining tuples into it
        // (need GeneratorSequence because not all
        //  collection generators are sequences)
        for t in GeneratorSequence(g) {
            let c = TupleCollectionView(t)
            for (i,e) in c.enumerate() {
                unzipped[i].append(e)
            }
        }
    }
    return unzipped
}

let zipped = [(1,"one", 1.0),(2,"two", 2.0)]
let unzipped = unzip(zipped)
// unzipped is now [[1, 2], ["one", "two"], [1.0, 2.0]]

We return [[Any]] for two reasons. First, because it’s what the mirror returns for the tuple elements. But second, because it’s the only way to dynamically return an array of different types without using tuples.

But note we don’t have to take in an Any as an argument. The input type T can be fixed at compile time – we just don’t know what arity it is until inspecting it at run-time. But because every element in the array is of the same fixed type, we can safely construct the size of the array to return based on the first element.6

Is there any way to lock in the return type at compile time? Sorta. If you’re willing to be constrained only to tuples of all of the same type, you could specify the return type explicitly and then cast the Any to it:

// note, additional U placeholder
struct TupleCollectionView<T,U>: CollectionType {
// ...

    subscript(idx: Int) -> U {
        guard case .Tuple = _mirror.disposition
            else { return _mirror.value as! U }

        return _mirror[idx].1.value as! U
    }
}

let t = (1,2)
let c = TupleCollectionView<(Int,Int),Int>(t)


func unzip<C: CollectionType,U>(tuples: C) -> [[U]] {
    var unzipped: [[U]] = []

    var g = tuples.generate()
    if let t = g.next() {
        let c = TupleCollectionView<C.Generator.Element,U>(t)
        for e in c {
            unzipped.append([e])
        }

        for t in GeneratorSequence(g) {
            let c = TupleCollectionView<C.Generator.Element,U>(t)
            for (i,e) in c.enumerate() {
                unzipped[i].append(e)
            }
        }
    }
    return unzipped
}

let zipped = [(1,2), (3,4)]
let unzipped: [[Int]] = unzip(zipped)

There are a few downsides to this, aside from being constrained to homogenous tuples.

First, having to declare both the in and out types is unweildy, though a little less unweildy with unzip, which at least can infer everything but the return type.

Second, what if you do this?

// this won't compile
let ints = [(1,2), ("3","4")]

// but this will
let ints = [(1,2), (3,4)]
let strings: [[String]] = unzip(ints)

// and so will this
let mixed = [(1,"2"), (3,"4")]
let ints: [[Int]] = unzip(mixed)

In both the latter cases, you get a kaboom at runtime.

We could replace the as with as?, but that would require unzip to return an optional, as in let ints: [[Int?]] = unzip(mixed), which is as much inconvenience as returning an Any.

My hope is there’s a clever way of determining, at compile time, that every element of the tuple T is of type U. But if there is, it’s beyond me. If someone smarter at compile-time type-wrangling than me thinks of a solution, hit me up on twitter.7


  1. There is actually a solution in Haskell, involving Applicative Types. But there’s no way I’m lunging head-first into a description of that based on my iffy Haskell skills. 
  2. Erlang can do it! Erlang tuples can be composed at runtime. Erlang gets no love from the Swift crowd :-( 
  3. Unlike, say, __conversion() which feels like an implementation detail leaked out. Those underscores are basically a sign on the door saying “Beware of the Leopard”. EDIT: __conversion was disappeared in later versions of Swift. 
  4. Interestingly, if you pass a tuple into a function that takes a generic argument, .0 will refer to the entire tuple, not the first element of the tuple. Well, it’s interesting to me, anyway. 
  5. Once again I find myself wishing I’d written that generic collection head and tail function. 
  6. OK, not entirely safely. You can break this by passing in an [Any] that contains tuples of variable length. Using Any is not quite as crash-proof as I might have led you to believe. 
  7. This would be cool because you could then probably use the same technique to confirm every element of the tuple conformed to a protocol. If every tuple element was equatable, you could then write a n-tuple implementation of ==

6 thoughts on “Tuple-wrangling

  1. If Swift supported variadic generics a much more elegant solution to this would be possible. Hopefully they will add that feature in 2.0.

  2. Despite its baroqueness there are some really great things in the latest versions of C++. It seems like the Swift team is trying to retain as much as possible in a much more elegant form. I’m hopeful that it will eventually bring together the best of the functional world with the best of C++. It’s off to a good start.

  3. I’m sure you’re aware, but It is also possible to use overloading and brute force to simulate the variadic version up to an arbitrary n-tuple. This gives callers a more convenient name and allows a variadic implementation to be dropped in if that becomes possible in the future.

      • It’s an unfortunate trade off at the moment. I prefer to avoid doing things at runtime when possible so finite n that is relatively easy to extend is my preference.

        Public discussion of real-world scenarios where variadic generics will be useful should increase the chance of seeing them in 2.0.

        You’re blog is really great, by the way. I wish I had the time to write as much as you have been…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s