Video #13: The Many Faces of Map

Episode: Video #13 Date: Apr 23, 2018 Access: Members Only 🔒 URL: https://www.pointfree.co/episodes/ep13-the-many-faces-of-map

Description

Why does the map function appear in every programming language supporting “functional” concepts? And why does Swift have two map functions? We will answer these questions and show that map has many universal properties, and is in some sense unique.

Video

Cloudflare Stream video ID: 2af1d020a4ceb733016559689367d7b0 Local file: video_13_the-many-faces-of-map.mp4 *(download with --video 13)*

References

Transcript

— 0:05

Today’s topic is a big one, and it’s only the beginning of a long, deep journey. We want to consider the seemingly humble map function in all of its glory. Many people point to the presence of map in a language as being a strong indicator of the language having “functional” tendencies. You’ll often hear “language ABC has support for functional concepts like map , filter , reduce , etc”, and the mention of map is always first! Why is that?! Swift must be doubly functional because it comes with two map s! One on arrays and one on optionals! We want to build intuition for why map seems to be so ubiquitous in “functional-leaning” languages, and in fact there are lots of other map s lurking in the shadows of our everyday Swift code that we have yet to explore. Swift’s maps

— 1:08

Let’s start by taking a tour of all the map s that Swift gives us. We have explored the map method on array a ton in this series. It’s used to transform all the elements of an array and get back a whole new array: [1, 2, 3] .map { $0 + 1 } [1, 2, 3] .map(incr)

— 1:31

We also defined a free map function because we saw that it composed a lil nicer. Let’s re-define it, but also provide an implementation from scratch just to show everyone how simple this function is: func map<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] { return { xs in var result = B xs.forEach { x in result.append(f(x)) } return result } }

— 2:36

And then we could do all types of fun stuff like: [1, 2, 3] |> map(incr) [1, 2, 3] |> map(incr) |> map(square)

— 3:00

An important law we observed while playing with these things is that map distributes over composition, and this has performance implications: [1, 2, 3] |> map(incr >>> square)

— 3:23

Now, there’s another map in the standard library that so far we have only briefly mentioned, and that is map on optional. It allows you to safely unwrap an optional, perform a transformation, and then rewrap the optional: Int?.some(2) .map(incr) Int?.none .map(incr) This means map allows you to deal with optionals in a very safe and expressive way without force unwrapping them in order to get at the value on the inside.

— 3:59

We also previously defined a free map on optionals because, again, it composed really nicely. Let’s do that again, but fully implement it this time to show how simple it is: func map<A, B>(_ f: @escaping (A) -> B) -> (A?) -> B? { return { switch $0 { case let .some(a): return .some(f(a)) case .none: return .none } } }

— 4:56

Which can be used like so: Int?.some(2) |> map(incr) Int?.some(2) |> map(incr) |> map(square) Int?.some(2) |> map(incr >>> square)

— 5:07

It also seems that map on optionals has the same property that it did on arrays in that it distributes over function composition. And because optionals are not a zero-cost abstraction this also has some, albeit tiny, performance implications since we aren’t creating multiple optionals.

— 5:37

There’s another property that map satisfies that we haven’t needed to use or discuss yet. To understand it, let’s look at something kinda strange: [1, 2, 3] .map { $0 } Int?.some(2) .map { $0 }

— 6:15

Here’s another property. If the transformation we supply to map doesn’t do anything, then it leaves the structure fixed. The seems like a very reasonable property for map to have. There’s a name for a function that does nothing but return its argument: the identity function. We can define it in full generality like so: func id<A>(_ a: A) -> A { return a } Seems like quite a useless function, but it means we can rewrite our earlier calls. [1, 2, 3] .map(id) Int?.some(2) .map(id)

— 6:41

How many times have you used the { $0 } closure in compactMap (or flatMap ) in order to remove the nil s? Well, now you can just use id ! [1, 2, nil, 3].compactMap(id) [1, 2, nil, 3].flatMap(id) There will be more uses in future episodes too.

— 7:11

What we’re seeing here is that when we map with id , we do not change the value that we’re mapping over: map preserves the identity function just like it preserved function composition: // map(id) == id

— 7:27

And this of course holds true for arrays and optionals. [1, 2, 3].map(id) == id([1, 2, 3]) // true Int?.some(2).map(id) == id(Int?.some(2)) // true

— 7:49

The identity function is also characterized by the fact that composing it with any other function leaves the other function fixed: // f >>> id == f // id >>> f == f Parametricity and theorems for free

— 7:59

OK, this fun and all, but so what? We do this type of stuff in our code all the time, and there is nothing deep and beautiful about it right? Well! I’m here to tell you that map is uniquely defined! There is literally no other way to define map on arrays or optionals other than how we have above. It’s a universal fact of nature! We truly have no choice but to define map as it is above. No matter how you try to philosophize it, there is no free will when it comes to defining map !

— 8:42

Can that possibly be true? But we can define all types of functions that have the same signature as map and yet do something completely different from map ! Let’s start with this stub: func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] { return { xs in } }

— 9:00

We could define this function to return just an empty array. func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] { return { xs in return [] } }

— 9:07

Heck, I could also double the array: func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] { return { xs in return xs + xs } } Cannot convert return expression of type ‘[A]’ to return type ‘[B]’

— 9:13

Oh wait, so the xs are in [A] and I need to get to [B] . I guess I should map this result then: func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] { return { xs in return (xs + xs).map(f) } }

— 9:21

We can keep going! func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] { return { xs in return [] return (xs + xs).map(f) return (xs + xs + xs).map(f) return xs.reversed().map(f) return Array(xs.prefix(1)).map(f) return Array(xs.prefix(2)).map(f) return Array(xs.suffix(1)).map(f) return Array(xs.suffix(2)).map(f) } } So how on earth is this unique?

— 10:19

Well, it’s unique with a caveat. While map is not unique amongst all such functions with this signature, but it is the unique one satisfying the property we observed before: map(id) == id . All of the lift s we defined do not have this property. They change the structure of the array by shuffling it, taking a subset, or repeating elements. Also, it’s no coincidence that we had to use map under the hood to transform the array after the shuffle. We could have also called map before shuffling: func lift<A, B>(_ f: @escaping (A) -> B) -> ([A]) -> [B] { return { xs in return [] return xs.map(f) + xs.map(f) return xs.map(f) + xs.map(f) + xs.map(f) return xs.map(f).reversed() return Array(xs.map(f).prefix(1)) return Array(xs.map(f).prefix(2)) return Array(xs.map(f).suffix(1)) return Array(xs.map(f).suffix(2)) } }

— 11:32

What we are seeing here is because this function signature is fully generic, and we know nothing about A ‘s and B ‘s other than we have an f that can transform A ‘s to B ‘s, the implementation of the function is very rigid. We can’t filter out, say, the even integers because we don’t know we are dealing with integers. We can’t all the values equal to some other value cause we don’t know we are dealing with Equatable things. We can’t take all the values greater than some value because we don’t know we are dealing with Comparable things.

— 12:00

There is not a lot of choice we have in implementing. We are forced into one of two situations: either transform the data with map(f) and then apply our shuffling, or apply our shuffling and transform with map(f) .

— 12:20

The formal statement of this is the following: // If f, g are functions // then lift(f) >>> map(g) == map(f) >>> lift(g)

— 12:38

This holds for any lift function. It’s kinda like map is universal enough that it can “intertwine” itself any other function that has the same signature. Let’s look at some concrete examples: let xs = [1, 2, 3, 4, 5] let f = incr let g = { (x: Int) in String(x) } let lhs = lift(f) >>> map(g) let rhs = map(f) >>> lift(g) lhs(xs) == rhs(xs) // true

— 13:25

The fact that it’s true makes sense because lift currently returns an empty array. lhs(xs) // [] rhs(xs) // [] But it continues to hold true for every lift we defined! We can use any array for the xs , any functions for the f and g (as long as they compose), and any lift implementation. This equality will be true.

— 14:06

So, given this universal property of map intertwining with all implementations of lift , what can we conclude. Well, what if lift also satisfied the lift(id) = id property, what would that say about the relation between lift and map ?

— 14:21

Let’s suppose that lift(id) is the same as id and see what happens. Given our previous formulation: // lift(f) >>> map(g) == map(f) >>> lift(g) We can swap f out for id ! // lift(id) >>> map(g) == map(id) >>> lift(g)

— 14:42

We can now swap both lift(id) and map(id) out for id . // id >>> map(g) == id >>> lift(g)

— 14:53

We also know that composing identity with a function is the same as the function itself, so we can remove those compositions. // map(g) == lift(g)

— 14:58

Lo and behold: map and lift are the same function! The moment we required lift(id) = id we all the sudden got that map and lift must be equal! This has now “proven” the universal property of map ! It is the unique function with its signature that preserves the identity.

— 15:17

The underlying idea that we are grasping at here is known as parametricity, and it’s only something you can see in languages that support parametric polymorphism, which Swift does with generics. It allows you to write code that works on many shapes by introducing type parameters. This is in contrast with other forms of polymorphism like subtype polymorphism, in which you write code that works on many shapes by creating subtypes of super types, such as in subclassing.

— 15:48

There is a really wonderful result that was proved in 1989, nearly 30 years ago, in a paper by Philip Wadler called “Theorems for Free” . It essentially says that given a suitably generic functions, like our map , there is a corresponding theorem that pops out for free, like our intertwiner property lift(f) >>> map(g) = map(f) >>> lift(g) . This works for any fully generic function! For example, consider this: func r<A>(_ xs: [A]) -> A? { fatalError() }

— 16:32

There is a theorem hiding here that shows how the map on array intertwines with the map on optionals! But we are going to leave the details of this to the exercises! Define your own map The standard library isn’t the only place we should be defining map ’s. You should be defining them on your own custom types too, as long as they uphold the laws. What kinds of types can we define map ?

— 17:23

One type we’ve encountered before is the Result type. enum Result<A, E> { case success(A) case failure(E) } What would its free map look like? func map<A, B, E>(_ f: @escaping (A) -> B) -> (Result<A, E>) -> Result<B, E> { return { result in switch result { case let .success(a): return .success(f(a)) case let .failure(e): return .failure(e) } } } Given a function (A) -> B , map will lift it up to a function (Result<A, E>) -> Result<B, E> , in which it transforms the successful case of the result. This allows you to safely unwrap a result to get at it’s value, apply a transformation, and then wrap it back up in a result.

— 17:54

What’s this look like in use? Result<Int, String>.success(42) |> map(incr) // .success(43) Result<Int, String>.failure("Error") |> map(incr) // .failure("Error") We see that it maps over the success side and leaves failure fixed.

— 18:25

Now, you may wonder: why are we only mapping the success side of a Result ? You are completely correct to wonder that, and the fact is there is not a particularly good reason. The map function is defined as only operating on a single type at a time, and so we must choose a side. The sides we have chosen are simply the conventions of the community. But we could have just as easily defined a map on the failure case and it would have been completely valid. The community probably settled on map on the success case because as programmers we are usually more focused on the “happy” path than the error path.

— 19:04

Now this does not contradict the uniqueness property of map , for what we have here is two different map s on two different generic parameters. The case of arrays and optionals we only had a single generic. So what we really have is one unique map implementation per generic parameter.

— 19:20

In a future episode we will explore a way of bridging both of these maps together into a single concept that will actually simplify our types quite a bit.

— 19:28

OK, now that we see it’s totally fine to define map on our own types, let’s get a bunch of examples to show just how common this function is. Take for example this: struct F1<A> { let value: A } I don’t even wanna give this a name, let’s just focus on the type abstractly. It’s a wrapper around a generic value, A . Let’s define what a map would look like on such a type: func map<A, B>(_ f: @escaping (A) -> B) -> (F1<A>) -> F1 { return { f1 in } } We know that’s the shape it should have, so can we implement it? func map<A, B>(_ f: @escaping (A) -> B) -> (F1<A>) -> F1 { return { f1 in F1(value: f(f1.value)) } }

— 20:26

So we see to map a value in this type means to simply unwrap the value, transform it with f , and wrap it up again. So, does map(id) == id hold true? Let’s consider the body. return { f1 in F1(value: f(f1.value)) }

— 20:45

And replace f with id return { f1 in F1(value: id(f1.value)) } Well, id leaves its value fixed. return { f1 in F1(value: f1.value) } And f1 and F1(value: f1.value) are equivalent. return { f1 in f1 } It’s the identity function! return { $0 }

— 21:11

It indeed seems that we’ve stumbled upon the one true map for F1 .

— 21:19

Let’s try another! Check out this type: struct F2<A, B> { let apply: (A) -> B } It’s just a wrapper around a function. I claim that a map -like function can be defined for the B generic parameter: func map<A, B, C>(_ f: @escaping (B) -> C) -> (F2<A, B>) -> F2<A, C> { return { f2 in return F2 { a in } } }

— 22:12

Well what can we do in here? We have something in A , we have something that transforms A ’s into B ’s, and we something that transforms B ’s into C ’s! Well it pretty much writes itself: func map<A, B, C>(_ f: @escaping (B) -> C) -> (F2<A, B>) -> F2<A, C> { return { f2 in return F2 { a in f(f2.apply(a)) } } }

— 22:33

We can even shorten this by using one of our favorite operators: func map<A, B, C>(_ f: @escaping (B) -> C) -> (F2<A, B>) -> F2<A, C> { return { f2 in F2(apply: f2.apply >>> f) } } And again we can see that map(id) == id when we replace f with id . return { f2 in F2(apply: f2.apply >>> id) } We know that composing into id leaves the other function fixed. return { f2 in F2(apply: f2.apply) } And now we’re looking at equivalent types. return { f2 in f2 } And the identity function all over again. return { $0 }

— 23:24

So this is our uniquely defined map on F2 .

— 23:28

Now you may wonder if we can define a map on the A generic parameter of F2 , and it seems reasonable. However, there’s a small problem with doing that. We don’t want to give it away just yet, so we are saving it for an exercise in the episode and we will cover it in a future episode!

— 23:49

How about one more? struct F3<A> { let run: (@escaping (A) -> Void) -> Void } Wow, this is a strange one! It’s a wrapper around a function that takes a function as an argument and returns nothing. This shape should be reminiscent of callback APIs you’ve dealt with, even in UIKit and Cocoa. For example, in UIKit you often present view controllers, and in that signature you will find this shape: URLSession.shared.dataTask( with: <#URL#>, completionHandler: <#(Data?, URLResponse?, Error?) -> Void#> ) -> Void

— 24:19

So, can we define map on this weird thing?! Let’s see! func map<A, B>(_ f: @escaping (A) -> B) -> (F3<A>) -> F3 { return { f3 in return F3 { callback in } } }

— 24:55

Jeez, what the heck can we do here?! Well, lets look at some types and see how they match up: func map<A, B>(_ f: @escaping (A) -> B) -> (F3<A>) -> F3 { return { f3 in return F3 { callback in f3.run // ((A) -> Void) -> Void callback // (B) -> Void f // (A) -> B } } }

— 25:24

How do these plug together? Well, the only thing that seems to fit together is that the output of f matches the input of callback , so we could start there: func map<A, B>(_ f: @escaping (A) -> B) -> (F3<A>) -> F3 { return { f3 in return F3 { callback in f3.run // ((A) -> Void) -> Void callback // (B) -> Void f // (A) -> B f >>> callback // (A) -> Void } } }

— 25:34

Well dang, now that last line is precisely what we need to feed into f3.run ! func map<A, B>(_ f: @escaping (A) -> B) -> (F3<A>) -> F3 { return { f3 in return F3 { callback in f3.run(f >>> callback) } } }

— 25:45

And yet again we can easily verify that map(id) == id if we swap f out for id . return { f3 in return F3 { callback in f3.run(id >>> callback) } } Composition leaves our callback fixed. return { f3 in return F3 { callback in f3.run(callback) } } Now F3 is passing its callback directly to the block, we could even have made this point-free: return { f3 in return F3(run: f3.run) } And everything one again collapses neatly into the identity function! return { f3 in f3 } Our map is indeed the universal map for this type. return { $0 }

— 26:48

Now, we used very abstract names for these types in order to not concentrate on any particular qualities of them, because none of that mattered for defining map . You may even know the proper names for some or all of these types, and if not you will soon in future Point-Free episodes.

— 27:04

It’s also fun to see all the signatures of map we just defined all together: // func map <A, B>(_ f: (A) -> B) -> (F1 <A>) -> F1 // func map<R, A, B>(_ f: (A) -> B) -> (F2<R, A>) -> F2<R, B> // func map <A, B>(_ f: (A) -> B) -> (F3 <A>) -> F3 But how amazing was it that we could define map on all of these types, and that we arrived at the one, unique map that there can ever be. Universal law of nature, it’s the only map that exists! Wow! The F word Now that we’ve seen that map is such a universal idea, you would think there’s got to be a name for it. And indeed there is. Now, on Point-Free we have gone through great lengths to introduce concepts with lots of motivation without getting bogged down in terminology. However, we still want to our viewers to know these terms so that they can continue learning about these topics. So, I think we are ready to define our first functional programming term that has the reputation of being a little scary. We’re going to say the F-word: “functor”.

— 28:03

Yes, the concept here that we are grasping at is that of a functor . A functor is a type that carries with it a map -like function. Array is a functor because it has map . Optional is a functor because it has map . Result is a functor because it has map . All of these strange types F1 through F3 are functors because they have map !

— 28:25

All of these seemingly disparate types are united by the concept of a functor in that they carry with them a map function which allows one to lift functions into their world.

— 28:31

Now, one of the great things about having such an abstract name as “functor” is that it carries with it no baggage of how one chooses to understand this concept. Each of the types we just explored, whether it be Result , Array , Optional , or F1 through F3 , has its own domain-specific way to get intuition for what they represent. For example an optional is kinda like a container for a single value that might be absent. An array is like a container that can hold many values. There is no one single intuition for all of these things.

— 29:01

So, we think it’s helpful to eschew any overly intuitive description of functor and instead rely only on it’s most basic property: the fact that it has a map function, and that the map function must satisfy the property that map(id) == id . And then from that we get to derive the wonderful property that map preserves function composition, i.e. map(f >>> g) == map(f) >>> map(g) . What’s the point?

— 29:40

We’ve gone deep into the abstract here. How is this knowledge of map applicable to everyday code?

— 29:59

Understanding the universal properties of map is important to realizing where it comes from and how we can define it for our own types! We’re comfortable using map on Array and Optional because these functions ship with Swift, and we’ve begun to see that we can work with both of these types with the same level of expressiveness as a result. We can and should be defining it on types we own so that we can work with our types in the same, expressive fashion.

— 31:02

While parametricity and “theorems for free” may seem academic, they help us realize how powerful Swift’s type system is, and how it can push us to think of the code we write as discovery, not invention! References Theorems for Free Philip Wadler • Jul 1, 1989 This famous paper describes “theorems for free”, in which if you write down a generic function signature, you can derive theorems that the function satisfies. This works in any language that has parametric polymorphism, as Swift does. https://people.mpi-sws.org/~dreyer/tor/papers/wadler.pdf Downloads Sample code 0013-the-many-faces-of-map Point-Free A hub for advanced Swift programming. Brought to you by Brandon Williams and Stephen Celis . Content Become a member The Point-Free Way Beta previews Gifts Videos Collections Free clips Blog More About Us Community Slack Mastodon Twitter BlueSky GitHub Contact Us Privacy Policy © 2026 Point-Free, Inc. All rights are reserved for the videos and transcripts on this site. All other content is licensed under CC BY-NC-SA 4.0 , and the underlying source code to run this site is licensed under the MIT License .