Collection
Next Up
Unlock This Episode
Our Free plan includes 1 subscriber-only episode of your choice, plus weekly updates from our newsletter.
Introduction
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.
Subscribe to Point-Free
Access this episode, plus all past and future episodes when you become a subscriber.
Already a subscriber? Log in
Exercises
Implement a
map
function on dictionary values, i.e.map: ((V) -> W) -> ([K: V]) -> [K: W]
Does it satisfy
map(id) == id
?Implement the following function:
transformSet: ((A) -> B) -> (Set<A>) -> Set<B>
We do not call this
map
because it turns out to not satisfy the properties ofmap
that we saw in this episode. What is it about theSet
type that makes it subtly different fromArray
, and how does that affect the genericity of themap
function?Recall that one of the most useful properties of
map
is the fact that it distributes over compositions, i.e.map(f >>> g) == map(f) >>> map(g)
for any functionsf
andg
. Using thetransformSet
function you defined in a previous example, find an example of functionsf
andg
such thattransformSet(f >>> g) != transformSet(f) >>> transformSet(g)
This is why we do not call this function
map
.There is another way of modeling sets that is different from
Set<A>
in the Swift standard library. It can also be defined as function(A) -> Bool
that answers the question “isa: A
contained in the set.” Define a typestruct PredicateSet<A>
that wraps this function. Can you define the following?map: ((A) -> B) -> (PredicateSet<A>) -> PredicateSet<B>
What goes wrong?
Try flipping the direction of the arrow in the previous exercise. Can you define the following function?
fakeMap: ((B) -> A) -> (PredicateSet<A>) -> PredicateSet<B>
What kind of laws do you think
fakeMap
should satisfy?Sometimes we deal with types that have multiple type parameters, like
Either
andResult
. For those types you can have multiplemap
s, one for each generic, and no one version is “more” correct than the other. Instead, you can define abimap
function that takes care of transforming both type parameters at once. Do this forResult
andEither
.Write a few implementations of the following function:
func r<A>(_ xs: [A]) -> A? { }
Continuing the previous exercise, can you generalize your implementations of
r
to a function[A] -> B?
if you had a functionf: (A) -> B
?func s<A, B>(_ f: (A) -> B, _ xs: [A]) -> B? { }
What features of arrays and optionals do you need to implement this?
Derive a relationship between
r
, any functionf: (A) -> B
, and themap
on arrays and optionals.This relationship is the “free theorem” for
r
’s signature.
References
Theorems for Free
Philip Wadler • Saturday Jul 1, 1989This 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.