How to implement map using reduce in Clojure

Question

In the book Clojure for the Brave and True at the end of the section covering reduce there's a challenge:

If you want an exercise that will really blow your hair back, try implementing map using reduce

It turns out that this was a lot harder (at least for me, a Clojure beginner) than I thought it would be. After quite a few hours I came up with this:

(defn map-as-reduce
  [f coll]
  (reduce #(cons (f %2) %1) '() (reverse coll)))

Is a better way to do this? I'm particularly frustrated by the fact that I have to reverse the input collection in order for this to work correctly. It seems somehow inelegant!

Answer 1

just for fun: map really accepts more than one collection as an argument. Here is an extended implementation:

(defn map-with-reduce
  ([f coll] (seq (reduce #(conj %1 (f %2)) [] coll)))
  ([f coll & colls]
    (let [colls (cons coll colls)]
      (map-with-reduce (partial apply f)
                       (partition (count colls) 
                                  (apply interleave colls))))))

in repl:

user> (map-with-reduce inc [1 2 3])
(2 3 4)

user> (map-with-reduce + [1 2 3] [4 5] [6 7 8])
(11 14)

Answer 2

Remember that you can efficiently insert at the end of a vector:

(defn map' [f coll]
  (reduce #(conj %1 (f %2)) [] coll))

Example:

(map' inc [1 2 3])
;=> [2 3 4]

One difference between this map' and the original map is that the original map returns an ISeq instead of just a Seqable:

(seq? (map inc [1 2 3]))
;=> true

(seq? (map' inc [1 2 3]))
;=> false

You could remedy this by composing the above implementation of map' with seq:

(defn map' [f coll]
  (seq (reduce #(conj %1 (f %2)) [] coll)))

The most important difference now is that, while the original map is lazy, this map' is eager, because reduce is eager.