I wanted to take some time to talk about the humble map function. If you have ever used libraries like underscore, lodash, or ramda, you are sure to encounter more than a few curious functions. The unassuming map function is a good starting point on our journey to functional nirvana.
Taking a step back, what is map? Just like normal maps (the paper kind!), map is a guide to get from one place to another.
For example, in your notebook you have a list of numbers: 1 2 3. Next to that list you write 2 3 4. How did this happen? Simply enough, we went over each number in the list and added one to it. In other words, we mapped over the list of numbers and added one to them.
Let's take those numbers from our notebook and put them in an array. We are going to implement map and use it to transform our array from [1, 2, 3] to [2, 3, 4].
Again, we are going to visit each element in our array and guide the value to its next value. Normally we would just use a for loop.
var numbers = [1, 2, 3];
var result = [];
for (var i = 0; i < numbers.length; i++) {
result.push(numbers[i] + 1);
}Simple enough! We are visiting each element in the array, adding one to it, and then adding it to a new result array. Now, what happens if we want to add three instead of one? What if we want to multiply? Do you see the pattern forming? There are two things going on here which we can abstract:
- We iterate over our list
- We apply a transformation to each item in the list
Let's re-write this first to get our transformation out of the for loop.
function addOne(x) {
return x + 1;
}
var numbers = [1, 2, 3];
var result = [];
for (var i = 0; i < numbers.length; i++) {
result.push(addOne(numbers[i]));
}Things are starting to look cleaner! We simply moved the transformation of the loop into a function. Now how can we save ourselves from writing for loops all over our code? We can abstract the for loop into our shiny new map function!
function map(transformation, list) {
var result = [];
for (var i = 0; i < list.length; i++) {
result.push(transformation(list[x]));
}
return result;
}Simple right? We can now pass any function and any array into map. For example.
map(function(x) {
return x + 1;
}, [1, 2, 3]);
// [2, 3, 4]
function multiplyTwo(x) {
return x * 2;
}
map(multiplyTwo, [1, 2, 3]);
// [2, 4, 6]As it turns out, javascript arrays already have this method. Pretty handy right?
[1, 2, 3].map(function(x) {
return x + 1;
});Now forget about arrays and remember that map is just a means to get from one place to another. We do this by giving map a transformation function and some data to work on. How could we implement this on other data types?
Keeping things array like, we will start by using linked lists.
function listNode(value, next) {
return {
value: value,
next: next
};
}
var node3 = listNode(3);
var node2 = listNode(2, node3);
var node1 = listNode(1, node2);
// Or more concisely
var one = listNode(1, listNode(2, listNode(3)));How do we iterate over this list, our for loop wont work! Simple enough, we can call our transformation on the value property of the listNode and then repeat the process recursively for the next value in the sequence. Instead of doing this as a function, we are going to make it a method on our list.
function listNode(value, next) {
return {
value: value,
next: next,
map: function(transformation) {
// value and next comes from the parameters of listNode. We have
// simply created a closure around these two properties.
var nextValue = transformation(value);
var nextLink;
if (next) {
// Since our next element is a listNode, we know it will
// have a map method. To continue the sequence, we just call
// map on the next node in the chain
nextLink = next.map(transformation);
}
// Create a new listNode which contains the updated list
return listNode(nextValue, nextLink);
}
};
}Well now that is mind bending! What is going on in that map function? We accept one parameter which is our transformation function.
Just like with our array version, we supply the current value to the transformation and move along to the next element. We know how to get to the next element in the list by just following the next reference. Maps all the way down!.
Ok, next why do we return a listNode? We want to return the same type of thing from map. For arrays we return an array and from a list we return a list. This makes map much more predictable. Every time we call map we are guaranteed to have the same shape of object coming back. The result? We can map over our linked list! Using it is as simple as can be.
var linkedList = listNode(1, listNode(2, listNode(3)));
linkedList.map(function(x) {
return x + 1;
});
// listNode(2, listNode(3, listNode( 4)));Are you starting to see the beauty of map? One more example perhaps! Thus far we have worked with array like structures, what about non arrays, like trees? The principle behind map stays the same, we have a function that takes some data on a journey from one value to another. It does this by running a transformation over its internals. In a tree's case, we want to go over each node in the tree and apply our transformation to it.
function treeNode(value, left, right) {
return {
value: value,
left: left,
right: right
};
}
var myTree = treeNode(1, treeNode(2), treeNode(3));How can we implement map for this binary tree?
function treeNode(value, left, right) {
return {
value: value,
left: left,
right: right,
map: function(transformation) {
var nextValue = transformation(nextValue);
var nextLeft;
if (left) {
nextLeft = left.map(transformation);
}
var nextRight;
if (right) {
nextRight = right.map(transformation);
}
return treeNode(nextValue, nextLeft, nextRight);
}
};
}Does this look similar? It is just like a linked list with another pointer value. Its use should also feel old hat.
var tree = treeNode(1, treeNode(2), treeNode(3));
tree.map(function(x) {
return x + 1;
});
// treeNode(2, treeNode(3), treeNode(4))One of the simple pleasures of programming is finding patterns and making them into reusable snippets. What patterns have we found with map?
Transforming data from one state to another state is very common. Typically it requires some form of iteration. map is a generic way to accomplish this.
How we have defined map gives us a great deal of predictability. When we map over something we get the same type back. Take for example a function we will call identity.
function identity(x) { return x; }Quite a simple function, it returns any input you give it. What happens when we use this identity function with one of our examples?
[1, 2, 3].map(identity);
// [1, 2, 3]
listNode(1, listNode(2, listNode(3))).map(identity);
// listNode(1, listNode(2, listNode(3)))
treeNode(1, treeNode(2), treeNode(3)).map(identity);
// treeNode(1, treeNode(2), treeNode(3))Nothing extraordinary, we just get our original value back. Hold the phone tho, this tells us several things! Two, our type didn't change. We went from array to array, listNode to listNode, and treeNode to treeNode. This means we can continue mapping over our object. What does this look like?
function addOne(x) { return x + 1; }
function multiplyTwo(x) { return x * 2; }
[1, 2, 3].map(addOne)
.map(multiplyTwo)
// [4, 6, 8]
listNode(1, listNode(2, listNode(3))).map(addOne)
.map(multiplyTwo)
// listNode(4, listNode(6, listNode(8)))
treeNode(1, treeNode(2), treeNode(3)).map(addOne)
.map(multiplyTwo)
// treeNode(4, treeNode(6), treeNode(8))Another interesting recurrence we can find in this is that these maps can flatten down together. What am I talking about? Notice how in the above examples we iterate over each structure twice? Not terribly efficient. Instead we can combine the two functions (addOne and multiplyTwo) and then iterate only once!
function addOneAndMultiplyTwo(x) { return multiplyTwo(addOne(x)); }
[1, 2, 3].map(addOneAndMultiplyTwo)
listNode(1, listNode(2, listNode(3))).map(addOneAndMultiplyTwo)
treeNode(1, treeNode(2), treeNode(3)).map(addOneAndMultiplyTwo)One last generalization. Let's re-visit our initial implementation of the function (not method) map. Before we used arrays. Now our map will accept a transformation and any type that has a method called map.
function map(transformation, data) {
return data.map(transformation);
}
map(addOne, [1, 2, 3]);
map(addOne, listNode(1, listNode(2, listNode(3))));
map(addOne, treeNode(1, treeNode(2), treeNode(3)));How cool is that? Our map function is now type agnostic.
Now you may ask "Kevin, you promised me Functors and you never once mentioned them!" In response, I simply raise my eyebrows and exclaim "We have been talking about Functors all along!"
A Functor is nothing more than something that implements a map method which takes in a transformation. This map method also adheres to the two rules from above. Again those two rules were:
SomeType.map(identity) == SomeTypeor in other words Identity.mapdoesn't change the type of our object.SomeType.map(f1(x)).map(f2(x)) == SomeType.map(f2(f1(x)))or in other words Composition. We can flatten multiplemapcalls by chaining their transformations together and vice versa.
When first learning this, I scratched my head and pondered "How in the world are Functors usefull?"
The answer is quite simple. We now have a pattern that applies to any data type. If you you hand me some object and say "This is a Functor!" I can immediately modify it with map. I don't need to worry about how any internals of the object work. I know that if I want to modify it, I just map over it. We have taken a simple function, added two laws to it, and applied it to anything we can throw at it. It could be a simple object, a model from our database, a recursive data structure, whatever. All we need to remember is map means modify, who cares about anything else.
When getting into functional programming, we are bombarded by intimidating words and principles. Functors, Monoids, Monads, Comonads, Endofunctors, the list goes on. At the core of it, the principles are quite simple; we just need to get beyond the names and see their use cases.
Now, go forth! Whenever you see something which is a Functor (or just implements map), smile and rest easy. Functors are our map to success :D