How to Write A map Function

In the previous lesson I showed how to write higher-order functions (HOFs). In this lesson you’ll use that knowledge to write a map function that can work with a List.

Imagine a world in which you know of the concept of “mapping,” but sadly a map method isn’t built into Scala’s List class. Further imagine that you’re not worried about all lists, you just want a map function for a List[Int].

Knowing that life is better with map, you sit down to write your own map method.

As I got better at FP, I came to learn that my first actions in writing most functions are:

1. Accurately state the problem as a sentence

2. Sketch the function signature

I’ll follow that approach to solve this problem.

For the first step, I’ll state the problem like this:

I want to write a map function that can be used to apply other functions to each element in a List[Int] that it’s given.

My second step is to sketch a function signature that matches that statement. A blank canvas is always hard to look at, so I start with the obvious; I want a map function:

def map

Looking back at the problem statement, what do I know? Well, first, I know that map is going to take a function as an input parameter, and it’s also going to take a List[Int]. Without thinking too much about the input parameters just yet, I can now sketch this:

def map(f: (?) => ?, list: List[Int]): ???

Knowing how map works, I know that it should return a List that contains the same number of elements that are in the input List. For the moment, the important part about this is that this means that map will return a List of some sort:

def map(f: (?) => ?, list: List[Int]): List...
                                       ----

Given how map works — it applies a function to every element in the input list — the type of the output List can be anything: a List[Double], List[Float], List[Foo], etc. This tells me that the List that map returns needs to be a generic type, so I add that at the end of the function declaration:

def map(f: (?) => ?, list: List[Int]): List[A]
                                       -------

Because of Scala’s syntax, I need to add the generic type before the function signature as well:

def map[A](f: (?) => ?, list: List[Int]): List[A]
       ---

Going through that thought process tells me everything I need to know about the signature for the function input parameter f:

• Because f’s input parameter will come from the List[Int], the parameter type must be Int

• Because the overall map function returns a List of the generic type A, f must also return the generic type A

The first statement lets me make this change to the definition of f:

def map[A](f: (Int) => ?, list: List[Int]): List[A]
               ---

and the second statement lets me make this change:

def map[A](f: (Int) => A, list: List[Int]): List[A]
                       -

When I define a FIP that has only one input parameter I can leave the parentheses off, so if you prefer that syntax, the finished function signature looks like this:

def map[A](f: Int => A, list: List[Int]): List[A]

Cool. That seems right. Now let’s work on the function body.

A map function works on every element in a list, and because I haven’t covered recursion yet, this means that we’re going to need a for loop to loop over every element in the input list.

Because I know that map returns a list that has one element for each element in the input list, I further know that this loop is going to be a for/yield loop without any filters:

def map[A](f: (Int) => A, list: List[Int]): List[A] = {
    for {
        x <- list
    } yield ???
}

The only question now is, what exactly should the loop yield?

(I’ll pause for a moment here to let you think about that.)

The answer is that the for loop should yield the result of applying the input function f to the current element in the loop. Therefore, I can finish the yield expression like this:

def map[A](f: (Int) => A, list: List[Int]): List[A] = {
    for {
        x <- list
    } yield f(x)   //<-- apply 'f' to each element 'x'
}

And that is the solution for the problem that was stated.

You can use the REPL to confirm that this solution works as desired. First, paste the map function into the REPL. Then create a list of integers:

scala> val nums = List(1,2,3)
nums: List[Int] = List(1, 2, 3)

Then write a function that matches the signature map expects:

scala> def double(i: Int): Int = i * 2
double: (i: Int)Int

Then you can use map to apply double to each element in nums:

scala> map(double, nums)
res0: List[Int] = List(2, 4, 6)

The map function works.

I started off by making map work only for a List[Int], but at this point it’s easy to make it work for any List. This is because there’s nothing inside the map function body that depends on the given List being a List[Int]:

for {
    x <- list
} yield f(x)

That’s as “generic” as code gets; there are no Int references in there. Therefore, you can make map work with generic types by replacing each Int reference in the function signature with a generic type. Because this type appears before the other generic type in the function signature, I’ll first convert the old A’s to B’s:

def map[B](f: (Int) => B, list: List[Int]): List[B] = ...
        _              _                         _

Then I replace the Int references with A, and put an A in the opening brackets, resulting in this signature:

def map[A,B](f: (A) => B, list: List[A]): List[B] = {
        _        _                   _

If you want to take this even further, there’s also nothing in this code that depends on the input “list” being a List. Because map works its way from the first element in the list to the last element, it doesn’t matter if the Seq is an IndexedSeq or a LinearSeq, so you can use the parent Seq class here instead of List:

def map[A,B](f: (A) => B, list: Seq[A]): Seq[B] = {
                                ---      ---

With this new signature, the complete, generic map function looks like this:

def map[A,B](f: (A) => B, list: Seq[A]): Seq[B] = {
    for {
        x <- list
    } yield f(x)
}

I hope you enjoyed that process. It’s a good example of how I design functions these days, starting with the signature first, and then implementing the function body.

Now that you’ve seen how to write a map function, I encourage you to take the time to write a filter function. Because filter doesn’t return a sequence that’s the same size as the input sequence, its algorithm will be a little different, but it still needs to return a sequence in the end.

While this lesson provided a detailed example of how to write a function that takes other functions as an input parameter, the next lesson will show how to write functions that take “blocks of code” as input parameters. That technique and syntax is similar to what I just showed, but the “use case” for this other technique — known as “by-name parameters” — is a little different.

After that lesson, I’ll demonstrate how to combine these techniques with a Scala feature that lets a function have multiple input parameter groups.