# Implementing Map in Clojure

2014.10.26

Of all the problems on 4Clojure, I continue to revisit the challenge of implementing `map`. It’s such a basic function, yet writing it from scratch has some subtle problems. Let’s look at the process in detail.

To begin, here are the assertions that our custom `map` function needs to handle:

``````;; assertion 1
(= [3 4 5 6 7]
(my-map inc [2 3 4 5 6]))

;; assertion 2
(= (repeat 10 nil)
(my-map (fn [_] nil) (range 10)))

;; assertion 3
(= [1000000 1000001]
(->> (my-map inc (range))
(drop (dec 1000000))
(take 2))``````

For now, we will focus on the first assertion. A naive solution might make use of `for`.

``````(defn my-map [f col]
(for [x col]
(f x)))``````

In fact, the implementation above passes all three assertions. To make the problem more interesting, though, 4Clojure disallows the use of `for` in a solution. So the question is, how do we implement map without using `for`?

Again, let’s concern ourselves with just the first assertion. For anyone who has worked through The Little Schemer, the following recursive solution might come to mind:

``````(defn my-map [f col]
(loop [acc []
c coll]
(if (empty? c)
acc
(recur (conj acc (f (first c)))
(rest c)))))``````

Using an accumulator (i.e., `acc`), we recursively work our way through a collection, accumulating the values which have been calculated using the mapping function (i.e., `f`). This solves the constraint of avoiding `for`, but when we run this implementation as part of the third assertion, we have a performance disaster.

Our implementation of `map` will never finish incrementing an infinite range, and so, the only way to remove the performance problem is to start being lazy.

``````(defn my-map [f col]
(if (seq col)
(lazy-seq
(cons (f (first col))
(my-map f (rest col))))))``````

By wrapping our recursive call to the map function with a `lazy-seq`, we ensure that only the necessary values will be calculated and nothing else. And with the solution here, we have a working implementation of `map` which accepts a mapping function and a single collection as an argument.