Re-implement map

This brings us to the question of how we would implement the function map itself.

This is a basic building block that takes a function and a list and returns a list created by applying the given function to each of the elements of the given list. To map f onto a sequence, apply f to the first element and join the result onto whatever you get my mapping f onto the rest of the sequence.  So the obvious implementation looks like this:-

(defn mymap [f x]
  (if (seq x)
    (cons (f (first x)) (mymap f (rest x)))
    '()))

For example, increment a list of numbers:

user=> (mymap inc '(1 2 3 4))
(2 3 4 5)

However, the built-in function map is lazy. That is to say, I can apply it to an unlimited list provided I don't try to take the whole result. For example, recall that the function range without any parameters returns a lazy sequence of integers starting from 0 and going on forever:

user=> (take 10 (range))
(0 1 2 3 4 5 6 7 8 9)

I can still use this as a parameter in map:

user=> (take 10 (map inc (range)))
(1 2 3 4 5 6 7 8 9 10)

But if I do this with my reimplementation we get this:

user=> (take 10 (mymap inc (range)))
StackOverflowError clojure.lang.ChunkedCons.first (ChunkedCons.java:37)

Because the recursion in the function mymap starts work on its input list whether it needs it or not and just keeps going. To avoid this we want to write a lazy version of the map. In Clojure this is easier to do than to understand. I'm guided here by Fogus & Hauser, p 166. We add the macro lazy-seq to our map definition:

(defn mymap2 [f x]
  (lazy-seq
    (if (seq x)
      (cons (f (first x)) (mymap2 f (rest x)))
      '())))

Now this works for limited sequences:

user=> (take 3 (mymap2 inc '(1 2 3 4 5 6)))
(2 3 4)

But it also works for infinite ones:

user=> (take 3 (mymap2 inc (range)))
(1 2 3)

hmm. Pretty neat.

For the purposes of the 4Clojure exercise  we need to code this as an anonymous function that has an internally visible name so that it can call itself - you can add a name into the function definition form that will do this, as so:

(fn my-map [f x]
  (lazy-seq
    (if (seq x)
      (cons (f (first x)) (my-map f (rest x)))
      '())))

Here the name my-map is visible just inside the body of the definition.