What is Map?
The notion of Map has become so prevalent in all programming languages that almost everyone has some kind of exposure to it. Generically speaking, Map
means applying a function to values which are inside some kind of structure.
We usually use it a lot to apply a function to a list of values e.g mapping over the values of an Array or List
to be more specific.
In this post we will first see some examples of mapping in different languages and then we dive deep into it’s internals in terms of Haskell
and maybe finish with a better understanding of how everything fits together. Saying that lets start.
Some examples of Mapping in some popular langauges
JS and JQuery
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
Ruby
1 2 |
|
PHP
1 2 3 4 5 6 7 8 |
|
Map internals with Haskell
So lets see how an implementation of a Map
function in Haskell looks like
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
You see how partially applied functions ( (+1)
above ) comes in handy.
It’s pretty simple right. But why contrain this great idea to only a list of values. Haskell takes it a step further
and generalizes it with an Abstraction named Functor
. I will not get into details of Functors
but will just use that to demonstrate the generic notion of mapping over a structure. So what is this structure thing I am talking about.
In the application above the list is the structure, it’s characteristic is to hold a list of values. Tree
is another structure which has leafs
and branches
. They are ways of organizing data.
The notion of map
in generic sense is to apply a function over a strucure. Think of it like you want to throw a function over some kind of structure and apply it to the values inside. This can be any kind of strucure defined by you or in haskell Types
. Haskell has a TypeClass
named Functor
which any custom type can implement and thereby define how map should work for that type.
Lets see how this works for a Tree
type.
1 2 3 4 5 |
|
Now how should map works for this structure. In case of list we only had a list of values. In case of our Tree
its a bit different but we still have values in the leaves which we may want to transform, as the owner of the Data Type
we know best how to apply the function and on which data inside our structure to apply it to.
Let’s see how we can define a map
function for our tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
Oh I forgot to say map
is a way of transforming data as thats the only way you can chagne data in Pure functinal programming
as you can’t mutate them in place. But we are lazy programmers, why define a new method or force others to define new map functions for our data types. Haskell abstracts this with Functor
as I mentioned above. So lets define an instance of Functor
for our tree data type.
1 2 3 4 |
|
Once we have our Functor
instance for Tree
we can use the generic fmap
function now to do the same thing we did above
1 2 3 4 |
|
So the generic notion is Map
is not just for array or list of values, rather it’s a very powerful idea to apply any function over any kind of structures no matter how complex they are.
Hope you enjoyed it. We may talk more about Functors
later and see how haskell takes this idea of mapping to a whole new level and make it a lot more useful.