Some home-made implementations of map

This post originated in a conversation we had during the last Barcelona Software Craftsmanship event.

We talked about a technique to recursively processing list elements once at a time in which you have to focus on two things:

1. How to process an empty list (the base case of the recursion)
2. How to process a non empty list in terms of the result of processing the tail of the list (the list except the first element)

To illustrate it, let's see a possible implementation of map in SML:


It uses the following list functions:

• hd to extract the head of the list (its first element)
• tl to extract the tail of the list (the list except the first element)
• null that returns true if the list is empty and false otherwise

The :: operator adds an element at the beginning of a list.

We can use a similar approach to write map in Racket:


Here the name of the functions are a bit more expressive: first, rest and empty?.
The cons function adds an element at the beginning of a list.

A more idiomatic way to write map in SML would be using pattern matching:


This version is using the same approach but pattern matching makes the code more concise and expressive.

As a bonus here is a beautiful way to append two lists in SML using the same technique and pattern matching:


This is very well explained in the first unit of of the Programming Languages course from Washington University at Coursera that I completed last year.

There is going to be a new edition starting up Oct 2. I cannot recommend it highly enough.