15

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!

Improve this question
0

6 Answers 6

Reset to default
13

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

13

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)
Improve this answer

Comments

7

The real map calls seq on its collection argument(s) and returns a lazy seq, so maybe this to get it a little closer to the real map?

(defn my-map
  [f coll]
  (lazy-seq (reduce #(conj %1 (f %2)) [] (seq coll))))

I would have added that as a comment, but I don't have the reputation. :)

Improve this answer

Comments

2

You can use conj to append to a vector instead of prepending to a list:

(defn my-map [f coll]
  (reduce (fn [result item]
              (conj result (f item)))
          [] coll))

(my-map inc [1 2 3]) => [2 3 4]
Improve this answer

Comments

2

It is more common to reverse the result, not the input. This is a common idiom when handling singly-linked lists in a recursive fashion. It preserves linear complexity with this data structure.

You might want to offer different implementations for other seqs, e. g., vectors, maybe based on conj instead of cons.

I would not worry too much about elegance with this kind of exercise.

Improve this answer

4 Comments

I don't see why it makes a difference to reverse the result instead of the input; the complexity is linear either way.
@SamEstep: Yeah, OK. It is just much more usual to reverse the result.
I don't really understand your comment about "offering other implementations for other seqs"; all the implementations of map on this page work for all Seqable inputs. If you mean to produce different types of sequences as a result, I don't see much of a point to doing that (except perhaps for performance) when one could easily just compose map with vec or something.
@SamEstep: performance was exactly my point. You do not need to reverse vectors.
1

As it was already pointed out. You do not have to reverse the input. cons add an item to the beginning of a sequence (even on vectors) whereas conj will always add in the most natural way, it always add an item in the fastest way possible for the collection. it will add from left to right for list, and from left to right for vectors.

I noticed that most suggested answers use 'reduce' so allow me to suggest this one using mainly recursion:

(defn my-map [f coll]
 (loop [f f coll coll acc []]
   (if (empty? coll)
     acc
     (recur f (rest coll) (conj acc (f (first coll)))))))
Improve this answer

2 Comments

The question specifically mentions using reduce so, whilst interesting, this answer in no way answers the question.
@mluisbrown that is true. I must have missed that it specifically stated to use 'reduce'

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.