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:

	fun mapUsingListFunctions(f, ls) =
	if null ls
	then []
	else f(hd ls)::mapUsingListFunctions(f, tl ls)
	val test = mapUsingListFunctions(
	(fn x => x * x),
	[1, 2, 3])
	(* val test = [1,4,9] : int list *)

view raw myMapUsingListFunctions.sml hosted with ❤ by GitHub

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:

	#lang racket
	(define (map-using-list-functions f ls)
	(if (empty? ls)
	'()
	(cons (f (first ls))
	(map-using-list-functions f (rest ls)))))
	(map-using-list-functions
	(lambda (x) (* x x))
	'(1 2 3))
	; '(1 4 9)

view raw myMapUsingListFunctions.rkt hosted with ❤ by GitHub

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:

	fun mapUsingPatternMatching(f, ls) =
	case ls of
	[] => []
	| head::tail => f(head)::mapUsingPatternMatching(f, tail)
	val test = mapUsingPatternMatching(
	(fn x => x * x),
	[1, 2, 3])
	(* val test = [1,4,9] : int list *)

view raw myMapUsingPatternMatching.sml hosted with ❤ by GitHub

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:

	fun append(xs, ys) =
	case xs of
	[] => ys
	| head::tail => head::append(tail, ys)
	val testAppend1 = append([1, 2, 3, 4], [5, 6, 7])
	(* val testAppend1 = [1,2,3,4,5,6,7] : int list *)
	val testAppend2 = append([], [5, 6, 7])
	(* val testAppend2 = [5,6,7] : int list *)
	val testAppend3 = append([1, 2, 3, 4], [])
	(* val testAppend3 = [1,2,3,4] : int list *)

view raw myAppendUsingPatternMatching.sml hosted with ❤ by GitHub

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.