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.
Making a map
Taking a step back, what is map? Just like a paper map, the function map is a guide to get from one place to another.
For example, in your notebook you have a list of numbers: 1, 2, and 3. Next to that list you write 2, 3, and 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.
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.
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!
Simple right? We can now pass any function and any array into map. For example.
Other Data Types
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.
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.
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.
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.
How can we implement map for this binary tree?
Does this look similar? It is just like a linked list with another pointer value. Its use should also feel old hat.
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, 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.
Quite a simple function, it returns any input you give it. What happens when we use this identity function with one of our examples?
Nothing extraordinary, we just get our original value and type back. Nothing changed. Hold the phone though, this is cool! Our type didn’t change which means we can continue mapping over our object. What does this look like?
Another interesting thing we notice is that these maps can flatten 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 map only once!
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.
How cool is that? Our map function is now type agnostic.
And What About Functors?
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) == SomeType, or in other words Identity. map doesn’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 multiple map calls by chaining their transformations together and vice versa.
When first learning this, I scratched my head and pondered “How in the world are Functors useful?”
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