Map

Map is one of the most powerful tools in a functional programmer's toolbox. Besides list comprehensions and filters, they are great ways to act on individual items in a list as a whole.

\(map\) is a higher order function such that given a function \(f\)

\[map \left (f, \left [ a_1, a_2, \cdots a_n \right ] \right ) = \left [ f(a_1), f(a_2), \cdots f(a_n) \right ] \]

This section contains topics from Category Theory. If you are not familiar with haskell or category theory, you are advised to read the rest of the article and come back here later.

Note that the key property of map is that it looks at the second argument at a deeper level, i.e, it looks inside the \( [ \) and the \( ] \) brackets.

The type signature of \( map \) in haskell would be map :: (a -> b) -> [a] -> [b].

To generalise, we would want to \(map\) over data types constructed by functors other than just the list constructor, like a tree, just to state an example. We call this generalisation of \(map\) as \(fmap\)

The haskell type signature of the generalised \(fmap\) is fmap :: Functor f => (a -> b) -> f a -> f b.

It should be obvious that \(map\) is just a special case of \(fmap\) defined as instance Functor [] where fmap = map.

Suppose we define a binary tree recursively by stating that a tree is just a leaf or a fork to two other trees.

1	data Tree a = Leaf a | Fork (Tree a) (Tree a)

What if we already have a tree and decide to increment all its nodes by 1?

That's right we'd have to \(fmap\) the increment function over the tree.

First, we start by defining what the \(fmap\) over a tree actually does

1 2 3

instance Functor Tree where fmap f (Leaf x) = Leaf (f x) fmap f (Fork l r) = Fork (fmap f l) (fmap f r)

Now, we are ready!

1	fmap (1+) (Fork(Fork(Leaf 0)(Leaf 1))(Fork(Leaf 2)(Leaf 3)))

would evaluate to

1	Fork (Fork(Leaf 1)(Leaf 2))(Fork(Leaf 3)(Leaf 4))

As discussed haskell not only has a simple map for lists but also encourages you generalise it for every functor. We will be discussing just map here, though.

When we are ready with the function, say f and the list, say l, it is pretty straightforward that map f l does the job.

Evaluate the first 10 perfect squares

---

The following code does the job:

1	map (^2) [1..10]

How sweet and compact!

Or we could create the list of all perfect squares and take the first 10, this way:

1	take 10 $ map (^2) [1..]

map in python is pretty much the same thing, barring for the syntax.

The following code would evaluate the cube of the first 10 natural numbers

1	map(lambda x: x**3, xrange(1,11))

The \(map\) function is represented by Map (case sensitive) in Mathematica.

The cool thing about Mathematica is that Mathematica developers have realised that Map is so important that they have some syntactic sugar for it, which is /@ could be used as a short-cut for the same. Hence, Map[f, l] could better be written as f /@ l. Note that both forms are valid.

Check how many primes are there between 1 to 100 inclusive

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

In[1]:= PrimeQ /@ Range[1, 100] Out[1]= {False, True, True, False, True, False, True, False, False, \ False, True, False, True, False, False, False, True, False, True, \ False, False, False, True, False, False, False, False, False, True, \ False, True, False, False, False, False, False, True, False, False, \ False, True, False, True, False, False, False, True, False, False, \ False, False, False, True, False, False, False, False, False, True, \ False, True, False, False, False, False, False, True, False, False, \ False, True, False, True, False, False, False, False, False, True, \ False, False, False, True, False, False, False, False, False, True, \ False, False, False, False, False, False, False, True, False, False, \ False} In[2]:= Tally[%1] Out[2]= {{False, 75}, {True, 25}}

Hence, there are 25 primes.