The MAP Function
Ok, so what point have we now reached?
We're at the point now where we can construct a singly linked list into which we can add items. We can retrieve the first item from the list using a
HEAD function and access the remainder of the list using a
TAIL function. We can also determine whether we've reached the end of the list using the
When you're lost, use a MAP
Now that we can access all the items of a list in sequential order, we have the foundation upon which to build a mechanism for applying a function to each item in that list.
In other words, we want to work our way sequentially down the list, passing each item to some function. The result of this process is the creation of a new list in which every item has been modified by that function.
This implies two things about the new list:
- It contains the same number of items as are in the old list
- The modified items in the new list appear in the same order as the items from which they have been derived in the old list.
The process by which a function is applied to every item in a list is known as mapping, and is one of the most fundamental tools in the functional programmer's toolbox.
Remember that in functional programming we are far less concerned with what a function does, and much more concerned with how a function is used.
I mention this to pre-empt a question that often arises here. When we say we want to apply a function to every item in a list, programmers from an imperative background will usually understand the situation by focussing what the function does.
This is a perfectly natural question for someone with an imperative mindset because they are strongly focussed on defining the exact sequence of instructions a computer should perform. However, within certain broad parameters, functional programming doesn't actually care what a function does. All we really care about how is a function should be applied - I.E. in this case, understanding the function's interface is more important than knowing what the function does.
In the case of mapping a function across the items in a list, all we are concerned about is ensuring that the function to be applied takes a single parameter and returns a single value.
So let's say we have a list that holds the first four positive integers
If we want to double each item in this list, then the first thing we need to do (after creating the list itself) is to create a function capable of performing the required task:
Building the MAP function
MAP function needs to take two parameters: firstly, the function to be applied to each item in the list, and secondly, the list to be processed. It then returns a new list leaving the original list unmodified.
The new list is generated by successively applying the following steps to each item in the list:
- Take the current list item and pass it to the function as a parameter
- Store the value returned by the function as a new item in the return list
- Recursively repeat steps one and two using the following three values as parameters:
TAILof the old list
- The function being applied
- The return list
If you've been following the blog series up to this point, you'll know that in order to repeat the same action an unknown number of times, we must use recursion (I.E. The Y-Combinator). Further to this, in order to successfully implement any recursive process, we need some way to detect when the recursion should finish - otherwise we'll disappear down the rabbit hole of infinite recursion.
So we'll need both an
IS_EMPTY and an
IS_LAST function that can detect whether the current item in the list is the last one.
The implementation of the MAP function is shown below. I trust that if you've read the previous blogs in this series, then the comments should be all you need to understand its structure.
Ok, let's see how we get on with this...
Hmmmm... We've got a problem here. We have the right numbers in the list, but in the reverse order.
Reversing out of a problem
Thinking about the way our
MAP function builds up its results in the
list_accumulator variable; we can see that it would be more accurate to call this data structure a stack or a LIFO list. Each time we pass the
HEAD of the old list to our
doubler function, the result is pushed into the
list_accumulator, and this inadvertently results in the order of items becoming reversed.
This is actually a common problem in list handling; very often, tasks performed on a list cause the item order to be reversed. However, rather than altering the way the current
MAP function works, the simplest solution is to write a function that reverses the order of items in a list, and then pass the
list_accumulator to this function as the return value from
REVERSE function is implemented as follows:
All we need to do now is make a small change to the
Ok, let's try this again...
The Generic Power of the MAP function
Together with the
REDUCE function, the
MAP function is arguably the most widely used tool in functional programming - to the point that many people perceive functional programming to be nothing more than using
REDUCE on their dataset. To quote President George Bush, they have greatly overmisunderestimated the situation; that said, this perception does illustrate the central position occupied by these two functional concepts.
So let's create a variety of functions that can all be used by the
MAP function. Remember that the most basic requirement here is that whatever function is passed to
MAP must take a single parameter as input, and produce a single value as output. Beyond that, the
MAP function doesn't care what your function actually does.
In the next blog, we'll look at how the
REDUCE function can be implemented.
All source code from the Mindshift blog series can be found on GitHub