Putting the map on the map
Disclaimer:
Most if not all of the things explained in this article are considered very “basic” by many. I don’t think they are basic and even if they are, the importance of the concepts described for developing a strong programmer’s intuition compensates for their “basic” nature. The word ‘I’ implies that everything you’re about to read is my personal opinion.
The given examples are very simple unlike the steps we’re going to take to get from one concept to another. Examples use JavaScript but the concepts are applicable to any language with first-class functions (even better if it has lambdas).
Whenever I rant about the JavaScript learning resources that are out there Kyle’s ‘You Don’t Know JavaScript’ is excluded.
I use arrow syntax to reduce the syntactic noise as much as possible. Within the article these are equivalent
const add = (x) => x + 1
const add = x => x + 1
const add = x => { return x + 1 }
const add = function(x) { return x + 1 }So here we go…
Abstraction and application
There is one ‘operation’ every programmer is supposed to have an intuition about when dealing with functions — function application. This operation is well described in maths and has some rules applied to it. Surprisingly this operation is not given the attention it deserves in most of the ‘beginner’ resources out there. Moreover, the word ‘call’ crawled into a programmers lingo like an eternal ‘hello’ from those who ‘can’ to those who ‘don’t need’.
We’re going to go with maths for now and ‘apply’ our functions rather then ‘call’ them. So how do we do it? I mean, seriously, what does it mean ‘to apply a function’? Let’s take this one:
const add1 = (x) => x + 1const three = add1(2) // three will be... 3
What is happening here? Do we even care? We got our ‘3’, what else do we need? I don’t want to be that guy, but I want to know how it works. Every time I use a function I want to know exactly how I can reason about what’s going on.
It turns out one brilliant mind whose name was Alonzo Church came up with this answer in 1930. Even before people started ‘calling’ functions in their programs. But first we need to get one thing out of the way.
I mentioned in the disclaimer that we’re going to use a language feature that goes by the name of ‘first-class functions’. It’s an epic way to say that functions can be used as values. I’ll repeat — functions can be used as values. Not the results of applying this function like ‘add1(2)’ but the function itself.
const add1 = x => x + 1
const fn = add1 // fn is `(x) => x + 1` now
// you can use both of them and they will give you the same result
add1(2)
fn(2)
// Most importantly we could just write it like this
(x => x + 1)(2) This is very important. It seems simple but it’s crucial to understand. If you’re still unsure about ‘first-class functions’ and what it means please read the first book from ‘You Don’t Know JavaScript’ series. Without the intuition about this concept you’re pretty much grounded.
Now back to our ‘add1’ function. What’s happening when you apply your function? Or rather how can you reason about the application process? It is something Alonzo called ‘β-reduction’ (not important to know the term but now you won’t freak out if you hear it from somebody).
// given
const three = add1(2)// step 0
const three = (x => x + 1)(2)/*
step 1
let's apply our function.
first we drop the `x =>`
it served its purpose, now x is just the number 2
*/
const three = x + 1 // remember x is 2/*
step 2
then we replace all occurrences of `x` with 2
*/
const three = 2 + 1
Wasn’t that hard, was it? It’s nothing special but it gives us one thing for free — we can now do the opposite operation called abstraction (hey Alonzo!) following similar intuition.
// given
const three = 3/*
Step 0
first we're going to replace our value 3 with a variable
we'll keep in mind that the value of this variable is still 3
*/
const three = x // remember x is 3/*
Step 1
now we're going to abstract over x which is a fancy way of saying
put `x =>` to make it a function with x as our argument
*/
const three = x => x/*
Step 2
Now we have a bit of a problem... our x is no longer 3
just check out our application steps. We're now on our step 0
Ah yes... here is our three
*/
const three = (x => x)(3)
In fact we got ourself the infamous `identity` function.
const id = x => x
const three = id(3)I know…I know… basic stuff. However it gives me an algorithm for creating abstractions (or functions because that’s what they are) in my programs. We all do refactoring. This gives us something more than just the knowledge that you can cut a chunk of your code and drop it into a function. In fact let’s try something out.
// given
2 + 1x + 1 // remember x is 2
(x => x + 1)(2)// Are you with me? Let's crank it up
(x => x + 1)(2)(x => x + y)(2) //rememeber y is 1(x => (y => x + y)(1))(2)(x => y => x + y)(2)(1)/*
Wait, what? It's tempting to describe the concepts
you can see in action here (currying, closure)
but we're going to leave them for another time.
The previous line is equivalent (for our purposes) to...
*/
((x, y) => x + y)(2, 1)//so
2 + 1 === ((x, y) => x + y)(2, 1)
The same intuition can be applied to a function of any arity. There is one more thing though…Remember ‘first-class functions’? Well we could take another route with our ‘add’ abstraction.
// given
2 + 1(x => x + 1)(2)/*
We already know that
x + 1 === (z => z + 1)(x)
so...
*/
(x => (z => z + 1)(x))(2)/*
Remember — function is just a value.
Well, then we can abstract over it like
we can over any value
*/
(x => y(x))(2) // remember y = z => z + 1(x => (y => y(x))(z => z + 1))(2)// and following the same path(x => y => y(x))(2)(z => z + 1)2 + 1 === ((x, y) => y(x))(2, z => z + 1)
Are you still with me? I hope so. Because I think not only is this crucial to understand it also has an almost mathematical elegance to it.
Now to the map…
Caught in a loop of writing loops
Let’s say we have an array of numbers
const numbers = [ 1, 2, 3, 4, 5 ]and our task is to write a function that adds 1 (surprise, surprise) to every element of the array. I reckon it won’t take long for us to write something along these lines:
function add1s(xs) {
let idx = 0
let result = []
while (idx < xs.length) {
result[idx] = xs[idx] + 1
idx = idx + 1
}
return result
}It looks decent and does the job. Now we’re given a task to convert each element to a string. Well, no problem:
function toStrings(xs) {
let idx = 0
let result = []
while (idx < xs.length) {
result[idx] = xs[idx].toString()
idx = idx + 1
}
return result
}And then another task is to convert each element to hex representation. If we were to start writing this loop again I’m sure it would be painful. It’s the third time! So what do we do? By now we realised that there might be more tasks to do with this array and you’re definitely done with writing the same thing all over again.
I won’t introduce anything new at this point. We have seen everything already. The key here is to locate what is different in every function that we have written so far to work with our array of numbers. And it will be
result[idx] = xs[idx] + 1
result[idx] = xs[idx].toString()
// if we were to go for writing the third one
result[idx] = xs[idx].toString(16) The only thing that is different is what we do with a single element. Everything else is exactly the same. So can we just…
result[idx] = (x => x + 1)(xs[idx])
result[idx] = (x => x.toString())(xs[idx])
// if we were to go for writing the third one
result[idx] = (x => x.toString(16))(xs[idx])Yes we can, we proved it. Wait… but then we can go further and abstract over our function…
result[idx] = (f => f(xs[idx]))(x => x + 1)
result[idx] = (f => f(xs[idx]))(x => x.toString())
// if we were to go for writing the third one
result[idx] = (f => f(xs[idx]))(x => x.toString(16))You should recognise this…we did it with our little ‘add’ function. And you know what comes next.
function add1s(f, xs) {
let idx = 0
let result = []
while (idx < xs.length) {
result[idx] = f(xs[idx])
idx = idx + 1
}
return result
}const newNumbers = add1s(x => x + 1, numbers)
const strings = add1s(x => x.toString(), numbers)
const hexes = add1s(x => x.toString(16), numbers)
Now ‘add1s’ is a rather inappropriate name for such a function. And I’m not the first person who noticed this fact. That’s why they renamed it.
function map(f, xs) {
let idx = 0
let result = []
while (idx < xs.length) {
result[idx] = f(xs[idx])
idx = idx + 1
}
return result
}Things to keep in mind
Map function has certain laws that are very useful when you’re reasoning about your program as well as when you trying to find a tool for a specific task and contemplating using map
numbers.length === map(x => x + 1, numbers).length
add1(numbers[1]) === map(add1, numbers)[1]I don’t want to get into types just yet but it’s nice to start thinking in types straight from the beginning so in layman’s terms the rule is if ‘people’ is an array of objects and the mapping function returns a string then the result of map will be an array of strings. Or the way I explained it to my junior developers:
You give it a ‘cat to dog’ converter and a bag of cats and it will give you a bag of dogs in return
Here is a ‘people’ example to illustrate:
// people is an array of objects (or Array<Object>)
const people = [
{ name: 'John', surname: 'Garry' },
{ name: 'Bambi', surname: 'Pinkman' },
{ name: 'Gina', surname: 'JustGina' },
]
/*
our function gets an Object and returns a string ((z: Object) => string)
so names is an array of strings (Array<string>)
*/
const names = map(z => z.name, people)Here you go — your bag of people to a bag of names converter.
Thank you for your patience
I hope you’ll get something from my examples and they will help you not only understand how map function works but also how you can abstract things away and reason about your code in a more logical way.
Thank you very much for your patience. I’m glad we managed to get through it together. Next time I want to talk about the reduce function (or fold as it’s sometimes referred to as).
Thank you Paul, Sergey, Ben, Sam and my wife Anna for reviewing.
