Map

It iterates, applies, transforms, collects. It's your functional best friend, map.

25 January 2017 ∙ Standard Library ∙ written by Greg Heo

What is map?

Map is a function that converts a collection into another collection. It applies a transformation operation to each element in the input collection, and outputs a collection of the transformed elements.

In this slightly different close reading of some open-source Swift, we’ll first think about what map is, try building it ourselves, and then compare our implementation with the “official” one to see what was different and why.

Map examples

The canonical demonstration of map is usually something like uppercasing an array of strings:

["hello", "world"].map { $0.uppercased() }
// output: ["HELLO", "WORLD"]

Or perhaps squaring an array of numbers:

[1, 2, 3].map { $0 * $0 }
// output: [1, 4, 9]

Wikipedia calls map a “higher-order function” which means it’s a function that takes a function as a parameter. Remember, closures are functions too! (Or maybe functions are closures too?)

You could convert an array of Double to an array of Int using a closure:

[15.2, 2.5, 10.0].map { Int($0) }
// output: [15, 2, 10]

What you’re really doing is passing each Double into Int‘s initializer; why not refer directly to the init function?

[15.2, 2.5, 10.0].map(Int.init)
// same output: [15, 2, 10]

Also note that the types of the input and output elements don’t need to be the same, as we’ve converted an array of Double to an array of Int here.

Implementing map

You could imagine how to write your own map:

• take an array and return another array
• need a closure parameter to perform the transformation step
• use a trusty for loop and build up an output array

Here’s what this might look like:

extension Array {
  // T is the output type
  func myMap<T>(_ transform: (Element) -> T) -> [T] {
    var result: [T] = []

    for item in self {
      result.append(transform(item))
    }

    return result
  }
}

map in Swift is defined on the Collection protocol but I’ve defined it here as an extension of Array for simplicity.

Since this is extending Array, self refers to the input array instance and Element is the type of thing the array holds.

We need to add a generic type parameter T for the output type. That means the transformation closure takes an Element and returns a T.

Then it’s a simple matter of iterating over the input array self, producing a transformed element of type T, and appending it to the result array. If you want to be terse, you could swap out the for loop with a forEach:

forEach { result.append(transform($0)) }

You can give it a try in a playground, and see that it works!

["hello", "world"].myMap { $0.uppercased() }
// output: ["HELLO", "WORLD"]

Time to submit that job application to join the Swift core team? Let’s compare and see how we did. 🤔

Standard library map

As usual, all the code will be right here inline, but you can check out the current source in Collection.swift on GitHub.

public func map<T>(_ transform: (Iterator.Element) throws -> T) rethrows -> [T] {

Looks pretty good! There’s the same generic parameter T for the output type. Since this is an extension on Collection rather than directly on Array, you need to go down to the Iterator to find the type Element.

map also supports transform closures that throw errors, and simply rethrows them. That was missing in our naïve implementation.

Counts

let count: Int = numericCast(self.count)
if count == 0 {
  return []
}

Why numericCast to get the count? A collection’s count is of type IndexDistance, which has to be some kind of SignedInteger. The default is Int but you can override this in your own custom collections. To be safe, there’s a cast specifically to Int.

If the collection is empty, we can return early. Seems like a reasonable optimization that saves allocating a new mutable array and iterating over nothing.

The actual map

var result = ContiguousArray<T>()
result.reserveCapacity(count)

In our implementation, we set up an empty mutable array. Here, the standard library sets up a ContiguousArray directly.

There are three flavors of array: ContiguousArray, ArraySlice, and Array. The differences are beyond the scope of this article but a contiguous array is like the textbook canonical array: a block of contiguous memory that you can index into.

Mutable arrays get initialized with some amount of storage and automatically grow as needed. That’s useful when you don’t know up front how many elements to hold, but that’s not the case here. Growing the array has some performance cost, and we can be more efficient by specifying exactly how much space we need with reserveCapacity().

var i = self.startIndex

for _ in 0..<count {
  result.append(try transform(self[i]))
  formIndex(after: &i)
}

It’s a for loop after all! We’re avoiding the overhead of spinning up an iterator, and indexing directly into the collection.

Normally, you might expect to see something like for i in 0..<count but the construct is different here: the index i is set and incremented separately, and the for loop’s job is to run count number of times.

We’re used to standard arrays that begin at index 0 and increment upwards. But again, map operates on generic collections. Who’s to say we can’t define a collection with negative indices? Or a collection that begins at index 10? Or a collection where only even indices are valid, and odd ones are out of bounds and cause a runtime trap?

For standard arrays, the highest valid index is (count - 1) but we can’t count on that here. We usually think of size and index as linked, but they’re separate concepts for generic collections. To summarize:

• The index starts at startIndex and gets advanced with formIndex(after:).
• The for loop’s job is to execute the code count number of times.

Check and return

_expectEnd(of: self, is: i)
return Array(result)

Finally, we end with a precondition to ensure we’ve reached the end of the collection. Now that the for loop has ended, the current index i should be the same as the collection’s endIndex. The _expectEnd(of:is:) function performs that check — you can see the code for it in Arrays.swift.gyb.

The Closing Brace

How did we do overall? I think pretty well — the big complication left out of our simple implementation was dealing with the array’s count vs its index.

That’s an important reminder that everyday things like arrays are made up of smaller pieces: sequence, collection, subscripting behavior, etc. Those pieces need to be generic, and you get more specific as you get closer to a concrete type. Building things on the generic level means thinking outside the “how would I build this?” box, into the “how could this be built?” box.

How would you build your own map? 🗺

}